CF786
我不会告诉你链接在图片里
CF786A
CF786A题意
给出一个大小为 \(n\) 的环，点顺时针从 \(1\to n\) 编号，两个人（设为 \(0,1\)）轮流移动其中的一个棋子。
对于第 \(opt\) 人，他能够将这个棋子顺时针移动 \(x\in S_{opt}\)（\(S_{opt}\) 是提前给出的）个步数，当某个人将棋子挪到 \(1\) 时这个人获胜。
问对于每一个位置和先手，要求你判断先手必胜，后手必胜还是死循环。
\(n\le 7000\)
CF786A题解
首先我们知道，博弈论有一个性质，就是对于一种状态 \(sta\)，如果它所有能到达的状态都是必胜，那么这个状态必败，否则必胜。
首先我们知道 \(1\) 位置必败，于是就可以尝试倒着推情况。
记搜即可。
CF786A代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 7100;
bool ans[maxn][2], vis[maxn][2];
int cnt[maxn][2];
int n;
vector<int> s[2];
void dfs(int u,int opt){
// printf("%d %d\n",u,opt);
if(vis[u][opt])return; vis[u][opt] = 1;
for(int i : s[opt ^ 1]){
int to = (u - i + n - 1) % n + 1;
// printf("%d %d %d\n",u,to,i);
if(to != 1){
if(!ans[u][opt]){
ans[to][opt ^ 1] = 1;
dfs(to,opt ^ 1);
}
else if((++cnt[to][opt ^ 1]) == s[opt ^ 1].size()){
ans[to][opt ^ 1] = 0;
dfs(to,opt ^ 1);
}
}
}
}
signed main(){
n = read();
for(int j = 0;j <= 1;j++)for(int i = read();i;i--)s[j].push_back(read());
dfs(1, 0);dfs(1, 1);
for(int i = 0;i <= 1;i++){
for(int j = 2;j <= n;j++){
printf(vis[j][i] ? (ans[j][i] ? "Win" : "Lose") : "Loop");
putchar(' ');
}
puts("");
}
return 0;
}
CF786B
CF786B题意
有 \(n\) 个点，现在有三种连边（开传送门）方式：
- \(1\space u\space v\space w\)：将 \(u\to v\)，这条边边权是 \(w\)。
- \(2\space u\space l\space r\space w\)：对 \(i\in[l,r]\)，将 \(u\to i\)，边权是 \(w\)。
- \(3\space u\space l\space r\space w\)：对 \(i\in[l,r]\)，将 \(i\to u\)，边权是 \(w\)。
求从 \(S\) 出发的单源最短路。
CF786B题解
线段树优化建边。
建两棵树，一棵自上而下的连边，一棵自下而上建边（分别设为 \(0,1\)）。
然后对于 \(1,2\)（\(1\space u\space v\space w\) 可以看做 \(2\space u\space v\space v\space w\)），将 \(1\) 树的 \([u,u]\) 连向 \(0\) 树的 \([l,r]\) 节点。
而对于 \(3\)，将 \(0\) 树的 \([l,r]\) 连向 \(1\) 树的 \([u,u]\)。
发现这样连边数量不会超过 \(\log n\) 条。
然后跑Dijsktra就好了。
注意空间开大点。
CF786B代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, S;
int head[maxn << 2], tot;
struct edge{
int to, nexte;ll wei;
edge(int to = 0,int ne = 0,ll we = 0):to(to),nexte(ne),wei(we){}
}e[maxn << 5];
void add(int u,int v,ll w){e[++tot] = edge(v,head[u],w);head[u] = tot;}
int id[maxn << 2][2],cntpoint;
int rev[maxn];
struct Segment_Tree{
void build(int l,int r,int p,bool opt){
id[p][opt] = ++cntpoint; if(l == r){rev[l] = p;return;}
int mid = l + r >> 1;
build(l,mid,p << 1,opt);build(mid + 1,r,p << 1 | 1,opt);
if(opt == 0){add(id[p][opt],id[p << 1][opt],0);add(id[p][opt],id[p << 1 | 1][opt], 0);}
else{add(id[p << 1][opt],id[p][opt],0);add(id[p << 1 | 1][opt],id[p][opt],0);}
}
void query(int l,int r,int s,int t,int p,int u,ll wei,bool opt){
if(s <= l && r <= t){
if(opt == 0)add(id[rev[u]][opt ^ 1],id[p][opt],wei);
else add(id[p][opt],id[rev[u]][opt ^ 1],wei);
return;
}
int mid = l + r >> 1;
if(s <= mid)query(l,mid,s,t,p << 1,u,wei,opt);
if(mid < t)query(mid + 1,r,s,t,p << 1 | 1,u,wei,opt);
}
void query(int l,int r,int u,ll wei,bool opt){query(1,n,l,r,1,u,wei,opt);}
void DEBUG(bool opt = 0,int l = 1,int r = n,int p = 1){
printf("l = %d r = %d p = %d,opt = %d,id = %d\n",l,r,p,opt,id[p][opt]);
if(l == r)return;
int mid = l + r >> 1;
DEBUG(opt,l,mid,p << 1);DEBUG(opt,mid + 1,r,p << 1 | 1);
}
}tree[2];
typedef pair<ll,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > que;
ll dis[maxn << 2];bool book[maxn << 2];
signed main(){
n = read(); m = read(); S = read();int opt, l, r, u, w;
tree[0].build(1,n,1,0); tree[1].build(1,n,1,1);
// tree[0].DEBUG(0);tree[1].DEBUG(1);
for(int i = 1;i <= n;i++){
add(id[rev[i]][0],id[rev[i]][1],0);
add(id[rev[i]][1],id[rev[i]][0],0);
}
for(int i = 1;i <= m;i++){
opt = read();
if(opt == 1){
l = read(); r = read(); w = read();
tree[0].query(r,r,l,w,0);
}
else{
u = read(); l = read(); r = read();w = read();
tree[opt - 2].query(l, r, u, w, opt - 2);
}
}
// for(int u = 1;u <= cntpoint;u++){
// for(int i = head[u];i;i = e[i].nexte){
// printf("%d -> %d, w = %lld\n",u,e[i].to,e[i].wei);
// }
// }
memset(dis,0x3f,sizeof(dis));
dis[id[rev[S]][0]] = 0;que.push(make_pair(0,id[rev[S]][0]));
while(!que.empty()){
int u = que.top().second;que.pop();
if(book[u])continue;book[u] = 1;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to, w = e[i].wei;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
que.push(make_pair(dis[v],v));
}
}
}
for(int i = 1;i <= n;i++){
if(dis[id[rev[i]][0]] == INF)dis[id[rev[i]][0]] = -1;
printf("%lld ",dis[id[rev[i]][0]]);
}
return 0;
}
CF786C
CF786C题意
给出一个长度为 \(n\) 的数列 \(a\)，要你对每个 \(k\in[1,n]\)，给出最小的 \(m\)，使得存在一种方案，将数列 \(a\) 划分成 \(m\) 段，使得所有段不同的数字不超过 \(k\)。
\(n\le10^5\)
CF786C题解
这里给出一个非常暴力的做法。
首先我们可以 \(O(n)\) 的计算出对于一个数字 \(k\) 的答案 \(f(k)\)。
观察这个 \(f(k)\)，不难发现这个函数满足性质：
- \(f(k)\) 单调不增，且有连续的段。（显然）
- \(f(k)\) 的取值不超过 \(\sqrt{n}\) 个。（不妨取一种极端情况，即 \(a\) 是 \(n\) 的一个排列，手玩一下就会发现这个极端情况也只有最多 \(\sqrt{n}\) 个取值）
于是就可以快乐的根号分治：
- 当 \(1\le k\le\sqrt{n}\) 时，直接算即可。
- 当 \(\sqrt{n}<k\) 时，二分找到与这个答案相等的最右端，然后这一段的答案都是这个。
如果害怕一个 \(k\) 的答案被重复计算，那就类似记搜记录下答案。
最大的点跑了 \(1044ms\)，时限 \(2s\) 完全不慌。
时间复杂度也许是 \(O(n\sqrt{n}\log n)\) 的？但是完全跑不满。
CF786C代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 1e5 + 10;
int a[maxn], n;
int book[maxn];
int ans[maxn];
int solve(int k){
if(ans[k])return ans[k];
memset(book,0,sizeof(book));
int l = 0, cnt = 0, m = 0;
for(int i = 1;i <= n;i++){
cnt += !book[a[i]]++;
if(cnt > k){
for(int j = l + 1;j < i;j++)book[a[j]]--;
m++; cnt = 1; l = i - 1;
}
}
return ans[k] = m + (cnt ? 1 : 0);
}
signed main(){
n = read();for(int i = 1;i <= n;i++)a[i] = read();
for(int k = 1, len = sqrt(n);k <= n;k++){
if(k <= len){printf("%d ",solve(k));}
else{
int res = solve(k);
int l = k, r = n;
while(l <= r){
int mid = l + r >> 1;
if(solve(mid) == res){l = mid + 1;}
else r = mid - 1;
}
l--;
for(int j = k;j <= l;j++)printf("%d ",res);
k = l;
}
}
puts("");
return 0;
}
CF786D
*3400不会
CF786E
我真是受不了了一道题写两个半小时一坤时
CF786E题意
给你一棵有 \(n\) 个节点的树和 \(m\) 个居民，每条边上有一个守卫 \(i\) 守卫连接 \(u_i-v_i\) 的这条边，每个居民 \(j\) 会从节点 \(u_j\) 走到节点 \(v_j\)。
现在对每个居民做出要求，要不然这个居民经过的所有守卫都有一条狗，要不然给这个居民发一条狗。
问满足所有要求需要发多少条狗给居民，多少条狗给守卫？要求给出构造。
\(n\le2\times10^4,m\le10^4\)
CF786E题解
究极毒瘤码农题，5.63KB极致压行代码你值得拥有
老规矩，先想想在序列上怎么做？
不难想到网络流。
设源点 \(S\) 和汇点 \(T\)，设网络流中一条边形如 \((u,v,cap)\) 表示有一条 \(u\to v\)，容量为 \(cap\) 的边。
对于每个居民 \(i\) 和他的要求 \(u_i,v_i\)，连接 \(w\in [u_i,v_i],(u,w,INF)\)。
然后对于每个居民 \(i\)，连接 \((S,i,1)\)。
对于每个守卫 \(i\)，连接 \((i,T,1)\)。
然后跑最小割即可。
等等等等，你这么连边不就 \(O(n^2)\) 了吗，这不T飞了？
好好好，那就线段树优化建边（为啥这套题这么喜欢线段树优化建边啊）
那树上的怎么办？树链剖分就完了。
那怎么构造答案呐？
从源点 \(S\) 出发，每次走没满流的边，走到一个守卫点时就说明至少存在一个居民在没给狗狗的情况下包含了这个守卫，所以让这个守卫拿一只狗狗。
然后回头看没走到的居民点，说明这个居民被选择了拿一只狗狗，给一只即可。
然后就没了，只不过慢慢码吧，我不会告诉你我码了两个半小时的。
CF786E代码
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x = 0, f = 1;char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
return x * f;
}
const int maxn = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m;
vector<pair<int,int> > edg[maxn];
struct edge{
int to, nexte, cap, flow;
edge(int to = 0,int ne = 0,int ca = 0,int fl = 0):to(to),nexte(ne),cap(ca),flow(fl){}
}e[maxn << 3];
int head[maxn], tot = 1,S , T;
void add(int u,int v,int cap){e[++tot] = edge(v,head[u],cap);head[u] = tot;}
void addd(int u,int v,int cap){add(u, v, cap);add(v, u, 0);}
int fa[maxn], siz[maxn], son[maxn],dep[maxn];
int edgid[maxn];//对每条边，存储在dep大的点上
void dfs1(int u,int f){
fa[u] = f;dep[u] = dep[f] + 1;
siz[u] = 1;son[u] = 0;
for(auto i : edg[u]){
int v = i.first;
if(v != f){
dfs1(v, u); siz[u] += siz[v];
edgid[v] = i.second;
son[u] = siz[son[u]] > siz[v] ? son[u] : v;
}
}
}
int top[maxn], dfn[maxn], idx, rev[maxn];//top重链顶端,dfn编号,rev[dfn[u]] = u
void dfs2(int u,int t){
top[u] = t;dfn[u] = ++idx;rev[idx] = u;
if(!son[u])return; dfs2(son[u],t);
for(auto i : edg[u]){
int v = i.first;
if(v != son[u] && v != fa[u])
dfs2(v, v);
}
}
int id[maxn], cntpoint;
int rrev[maxn];//rrev[l]=p表示[l,r]在线段树上编号
struct Segment_Tree{
int d[maxn];
void build(int l,int r,int p){
id[p] = ++cntpoint;
if(l == r){addd(id[p],T,1);rrev[l] = p;return;}
int mid = l + r >> 1;
build(l,mid,p << 1);build(mid + 1,r,p << 1 | 1);
addd(id[p],id[p << 1],INF);addd(id[p],id[p << 1 | 1],INF);
}
void query(int l,int r,int s,int t,int p,int u){//opt=0 == u->[s,t],cap=INF;opt=1 == [s,t]->T,cap=t-s
if(s <= l && r <= t){addd(u,id[p],INF);return;}
int mid = l + r >> 1;
if(s <= mid)query(l,mid,s,t,p << 1,u);
if(mid < t)query(mid + 1,r,s,t,p << 1 | 1,u);
}
void query(int s,int t,int u){query(1,n,s,t,1,u);}
void build1(int l = 1,int r = n,int p = 1){
if(l == r){
for(int i = head[id[p]];i;i = e[i].nexte)
if(e[i].to == T){d[p] = e[i].flow;break;}
return;
}
int mid = l + r >> 1;
build1(l,mid,p << 1);build1(mid + 1,r,p << 1 | 1);
d[p] = d[p << 1] + d[p << 1 | 1];
}
void DEBUG(int l = 1,int r = n,int p = 1){
printf("[%d,%d], p = %d, id = %d\n",l,r,p,id[p]);
if(l == r)return; int mid = l + r >> 1;
DEBUG(l,mid,p << 1);DEBUG(mid + 1,r,p << 1 | 1);
}
}tree;
void query(int u,int v,int to){
while(top[u] != top[v]){
if(dep[top[u]] < dep[top[v]])swap(u, v);
tree.query(dfn[top[u]],dfn[u],to);
u = fa[top[u]];
}
if(dep[u] > dep[v])swap(u, v);
if(u == v)return;
tree.query(dfn[son[u]],dfn[v],to);
}
int dis[maxn],cur[maxn];bool book[maxn];
queue<int> que;
bool bfs(int S,int T){
while(!que.empty())que.pop();
for(int i = 0;i <= cntpoint;i++){dis[i] = INF;cur[i] = book[i] = 0;}
dis[S] = 0;que.push(S);cur[S] = head[S];book[S] = 1;
while(!que.empty()){
int u = que.front();que.pop();book[u] = 0;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to;
if(dis[v] == INF && e[i].cap > e[i].flow){
cur[v] = head[v];dis[v] = dis[u] + 1;
if(!book[v]){que.push(v);book[v] = 1;}
}
}
}
return dis[T] != INF;
}
int dfs(int u,int flow,int T){
if(!flow || u == T)return flow;
int res = 0;
for(int i = cur[u];i;i = e[i].nexte){
int v = e[i].to;cur[u] = i;
if(dis[v] == dis[u] + 1 && e[i].cap > e[i].flow){
int tmp = dfs(v, min(flow,e[i].cap - e[i].flow),T);
if(!tmp)dis[v] = INF;
e[i].flow += tmp;e[i ^ 1].flow -= tmp;
res += tmp;flow -= tmp;
}
}
return res;
}
int Dinic(int S,int T){
int mxflow = 0;
while(bfs(S,T))mxflow += dfs(S,INF,T);
return mxflow;
}
vector<int> citizen, guard;
bool vis[maxn];
void dfs3(int u,int f){
if(vis[u])return;vis[u] = 1;
for(int i = head[u];i;i = e[i].nexte){
int v = e[i].to;
if(e[i].cap > e[i].flow)
dfs3(v, u);
}
}
signed main(){
n = read(); m = read();int u, v;cntpoint = m;
for(int i = 1;i < n;i++){
u = read(); v = read();
edg[u].push_back(make_pair(v, i));
edg[v].push_back(make_pair(u, i));
}
S = ++cntpoint;T = ++cntpoint;
dfs1(1, 0);dfs2(1, 1);tree.build(1,n,1);
for(int i = 1;i <= m;i++){
u = read(); v = read();
addd(S, i, 1); query(u, v, i);
}
int ans = Dinic(S,T);dfs3(S,S);
for(int i = 1;i <= m;i++)
if(!vis[i])citizen.push_back(i);
for(int i = 2;i <= n;i++)
if(vis[id[rrev[dfn[i]]]])guard.push_back(i);
printf("%d\n",citizen.size() + guard.size());
printf("%d",citizen.size());for(int i : citizen)printf(" %d",i);puts("");
printf("%d",guard.size());for(int i : guard)printf(" %d",edgid[i]);puts("");
// tree.DEBUG(); printf("ans = %d\n",ans);
// for(int u = 1;u <= cntpoint;u++)
// for(int i = head[u];i;i = e[i].nexte)
// printf("%d -> %d, cap = %d, flow = %d\n",u,e[i].to,e[i].cap,e[i].flow);
// for(int i = 1;i <= n;i++)
// printf("i=%d,fa=%d,siz=%d,son=%d,dep=%d,top=%d,dfn=%d,edgid=%d\n",i,fa[i],siz[i],son[i],dep[i],top[i],dfn[i],edgid[i]);
return 0;
}
