签到题，算一下b+=a和d+=c，然后卡一下次数就可以了。
只要一组出现一对相反数就是安全的。
题意：【1，n】，两个人轮流走，谁能走到1谁就赢，求每个人先手在【2，n】时的胜负情况。
一直没怎么写过博弈论的题，但其实这种题也只是一个bfs。
必胜态：有一条边走到必败态
必败态：连出去的所有边都是必胜态。
方法：倒着bfs，把1作为必败态进队，如果当前是必败态，能到达都是必胜态，如果当前是必胜态，能到达的所有的点入度-1，如果入度减到说明一定是必败态。
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define rep(i,l,r) for(int i=l;i<=r;i++) #define dow(i,l,r) for(int i=r;i>=l;i--) #define maxn 10000 #include<vector> #include<queue> using namespace std; typedef struct { int x,op,v; }node; queue<node> pp; int n,tot[2],num[2][maxn],f[maxn][2],c[maxn][2]; int main() { scanf("%d",&n); rep(i,0,1) { scanf("%d",&tot[i]); rep(j,0,tot[i]-1) scanf("%d",&num[i][j]); } pp.push((node){0,1,-1}); pp.push((node){0,0,-1}); f[0][1]=-1; f[0][0]=-1; while (!pp.empty()) { node now=pp.front();pp.pop(); if (now.v==1) { rep(i,0,tot[!now.op]-1) { int x=(now.x-num[!now.op][i]+n)%n; if (!f[x][!now.op]&& ++c[x][!now.op]==tot[!now.op]) { f[x][!now.op]=-1; pp.push((node){x,!now.op,-1}); } } } else { rep(i,0,tot[!now.op]-1) { int x=(now.x-num[!now.op][i]+n)%n; if (!f[x][!now.op]) { f[x][!now.op]=1; pp.push((node){x,!now.op,1}); } } } } rep(i,1,n-1) { if (f[i][0]) printf("%s",f[i][0]==1?"Win":"Lose"); else printf("Loop"); printf("%s",i<n-1?" ":" "); } rep(i,1,n-1) { if (f[i][1]) printf("%s",f[i][1]==1?"Win":"Lose"); else printf("Loop"); printf("%s",i<n-1?" ":" "); } return 0; }
图论题加入虚拟节点的思想，对于这道题可以对于2，3操作都建一个线段树，这样保证最后节点数<4n*2，对于2树就是父节点向子节点连边，对于3树就是子节点向父节点连边，然后再跑最短路。
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #define rep(i,l,r) for(int i=l;i<=r;i++) #define repedge(i,x) for(int i=fi[x];i;i=e[i].next) #define dow(i,l,r) for(int i=r;i>=l;i--) #define maxn 1004000 #define maxm 3004000 #define LL long long #define inf 10000000000000 #include<vector> #include<queue> using namespace std; typedef struct { int toward,next; LL cost; }E; E e[maxm]; int lson[maxn],rson[maxn],fi[maxn],n,tot,total,root[2],m,s,cho[maxn]; LL d[maxn]; queue<int> pp; void addedge(int j,int k,LL l) { ++total; e[total].toward=k; e[total].next=fi[j]; e[total].cost=l; fi[j]=total; } void build0(int &x,int l,int r) { if (l==r) { x=l; return; } x=++tot; int mid=(l+r)>>1; build0(lson[x],l,mid); build0(rson[x],mid+1,r); addedge(x,lson[x],0); addedge(x,rson[x],0); } void build1(int &x,int l,int r) { if (l==r) { x=l; return; } x=++tot; int mid=(l+r)>>1; build1(lson[x],l,mid); build1(rson[x],mid+1,r); addedge(lson[x],x,0); addedge(rson[x],x,0); } void add(int x,int l,int r,int ll,int rr,int y,LL z,int op) { if (ll<=l && r<=rr) { if (op==2) addedge(y,x,z); else addedge(x,y,z); return; } int mid=(l+r)>>1; if (ll<=mid) add(lson[x],l,mid,ll,rr,y,z,op); if (rr>mid) add(rson[x],mid+1,r,ll,rr,y,z,op); } int main() { scanf("%d %d %d",&n,&m,&s); memset(fi,0,sizeof(fi)); total=0; tot=n; build0(root[0],1,n); build1(root[1],1,n); while (m--) { int j,k,l,r; LL v; scanf("%d",&j); if (j==1) { scanf("%d %d %I64d",&j,&k,&v); addedge(j,k,v); } else { scanf("%d %d %d %I64d",&k,&l,&r,&v); add(root[j-2],1,n,l,r,k,v,j); } } rep(i,1,tot) d[i]=inf; memset(cho,0,sizeof(cho)); d[s]=0; pp.push(s); cho[s]=1; while (!pp.empty()) { int x=pp.front();pp.pop(); cho[x]=0; repedge(i,x) { int too=e[i].toward; LL v=e[i].cost; if (d[x]+v<d[too] && x!=too) { d[too]=d[x]+v; if (!cho[too]) { cho[too]=1; pp.push(too); } } } } rep(i,1,n) printf("%I64d%s",d[i]<inf?d[i]:-1,i<n?" ":" "); return 0; }
这次cf里面比较难的题，但其实还是一个经典问题。
首先对于一个固定的k，用贪心的方法就可以求出答案，即从左端点开始每次尽可能去最长的区间，对于这个问题其实就是给一个左端点l和k求最大的r使[l,r]中不重复的个数不超过k，显然用不重复区间的统计方法在线段树上2分就可以得到r。对于区间不重复个数询问只能是l递增，但是这道题要多次询问，所以就用主席树保存一下结果。
#include<cstring> #include<cstdio> #include<cmath> #include<algorithm> #define maxn 300000 #define maxm 8000008 #define rep(i,l,r) for(int i=l;i<=r;i++) #define dow(i,l,r) for(int i=r;i>=l;i--) #define LL long long using namespace std; int total,root[maxn],lson[maxm],rson[maxm],size[maxm],n,m,num[maxn],suc[maxn]; void add(int &x,int old,int l,int r,int y,int z) { x=++total; lson[x]=lson[old]; rson[x]=rson[old]; size[x]=size[old]+z; // printf("%d %d %d %d %d %d ",x,old,l,r,y,z); if (l==r) return; int mid=(l+r)>>1; if (y<=mid) add(lson[x],lson[old],l,mid,y,z); else add(rson[x],rson[old],mid+1,r,y,z); } int ask(int x,int l,int r,int y) { // printf("%d %d %d %d %d %d %d ",x,l,r,y,size[x],size[lson[x]],size[rson[x]]); if (l==r) { if (size[x]<=y) return r; return -1; } int mid=(l+r)>>1; if (size[lson[x]]<=y) return max(mid,ask(rson[x],mid+1,r,y-size[lson[x]])); return ask(lson[x],l,mid,y); } int main() { scanf("%d",&n); rep(i,1,n) scanf("%d",num+i); dow(i,1,n) { // printf("!! "); add(root[i],root[i+1],1,n,i,1); if (suc[num[i]]) { // printf("!! "); add(root[i],root[i],1,n,suc[num[i]],-1); } suc[num[i]]=i; // printf("%d: ",i); // rep(j,1,n) printf("%d %d %d ",i,root[i],size[root[i]]); // printf("!!! "); } // rep(i,1,n) printf("%d %d %d ",i,root[i],size[root[i]]); rep(i,1,n) { int ans=0,l=1; while (l<=n) { ++ans; int r=ask(root[l],1,n,i); // printf(" %d ",r); l=r+1; } printf("%d%s",ans,i<n?" ":" "); } return 0; }