B题打错调了半天，C题想出来来不及打，还好没有挂题
AC:AB Rank:96 Rating:2125+66->2191
A.Berzerk
题目大意：有一个东东在长度为n的环上（环上点编号0~n-1），两个玩家，玩家1有a种操作可选，玩家2有b种操作可选，每种操作可以让这个东东向前走若干步，两个玩家轮流操作，谁先让东东走到0谁胜，求出双方都选最优操作的情况下，东东开始在1~n-1各位置时玩家1先手和玩家2先手会必胜，必败还是无限循环。（a,b<n<=7000）
思路：类似DFS或者BFS的乱找，每次确定一个必败状态时，能到该状态的所有状态都为必胜态，一个状态能到的所有状态都确定为必胜时，该状态必败，用数组记下每个状态还有几个能到的状态未被确定即可，最后无法确定的状态即为循环，总复杂度O((a+b)n)。
#include<cstdio> char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 7000 int n,s[2],t[2][MN+5],u[MN*2+5],q[MN*2+5],l[MN*2+5],qn; int d(int x,int y){return x*n+(y+n)%n;} void lose(int); void win(int p) { int x=p/n,y=p%n,i,v; x^=1;u[p]=2; for(i=1;i<=s[x];++i) { v=d(x,y-t[x][i]); if(!u[v]&&++l[v]==s[x])lose(v); } } void lose(int p) { int x=p/n,y=p%n,i,v; x^=u[p]=1; for(i=1;i<=s[x];++i) { v=d(x,y-t[x][i]); if(!u[v])win(v); } } int main() { fread(B,1,1<<26,stdin); int i,x,y; for(n=read(),x=0;x<2;++x)for(s[x]=read(),i=1;i<=s[x];++i)t[x][i]=read(); u[n]=1;lose(0);lose(n); for(i=1;i<n;++i)printf("%s ",u[i]?u[i]>1?"Win":"Lose":"Loop");puts(""); for(i=1;i<n;++i)printf("%s ",u[i+n]?u[i+n]>1?"Win":"Lose":"Loop"); }
B.Legacy
题目大意：n个点，一个人一开始位于s，有q个走法供他选择，走法有3种种类：1.从v到u，花费w；2.从v到l~r中的一个点，花费w；3.从l~r中的一个点到v，花费w，求到各个点的最短路。（n,q<=100,000）
思路：线段树优化建图。第一类边直接连；第二类我们建一棵线段树，所有父亲向儿子连长度为0的边，表示到了该区间也能到达该区间中的点，每次我们让v连向表示[l,r]的O(log)个线段树节点即可；第三类我们再建一棵线段树，所有儿子向父亲连长度为0的边，这样每个点就能到达所有表示包含它的区间的线段树节点，每次我们让表示[l,r]的线段树上节点连向v即可。跑Dijkstra，总复杂度O((n+q)logn^2)。
#include<cstdio> #include<cstring> #include<queue> using namespace std; #define ll long long char B[1<<26],*S=B,C;int X; inline int read() { while((C=*S++)<'0'||C>'9'); for(X=C-'0';(C=*S++)>='0'&&C<='9';)X=(X<<3)+(X<<1)+C-'0'; return X; } #define MN 100000 #define N 131072 #define MV 524288 #define ME 5000000 #define d(x,y) make_pair(x,y) struct edge{int nx,t,w;}e[ME+5]; int h[MV+5],en;ll ds[MV+5]; typedef pair<ll,int> data; priority_queue<data,vector<data>,greater<data> >pq; inline void ins(int x,int y,int w){e[++en]=(edge){h[x],y,w};h[x]=en;} void ins1(int l,int r,int f,int w) { for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1)ins(f+N,l+1,w); if( r&1)ins(f+N,r-1,w); } } void ins2(int l,int r,int t,int w) { for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1)ins(l+1+(N<<1),t+N,w); if( r&1)ins(r-1+(N<<1),t+N,w); } } int main() { fread(B,1,1<<26,stdin); int n,m,i,s,a,b,c,d;ll x; n=read();m=read();s=read(); for(i=1;i<N;++i) { ins(i,i<<1,0);ins(i,i<<1|1,0); ins(i+N<<1,i+(N<<1),0);ins(i+N<<1|1,i+(N<<1),0); ins(i+N,i+N*3,0);ins(i+N*3,i+N,0); } while(m--) { a=read();b=read();c=read();d=read(); if(a==1)ins(b+N,c+N,d); if(a==2)ins1(c,d,b,read()); if(a==3)ins2(c,d,b,read()); } memset(ds,127,sizeof(ds));ds[s+N]=1;pq.push(d(0,s+N)); while(pq.size()) { a=pq.top().second;x=pq.top().first;pq.pop(); for(i=h[a];i;i=e[i].nx)if(x+e[i].w<ds[e[i].t]) { ds[e[i].t]=x+e[i].w; pq.push(d(ds[e[i].t],e[i].t)); } while(pq.size()&&pq.top().first>ds[pq.top().second])pq.pop(); } for(i=1;i<=n;++i)printf("%I64d ",ds[i+N]<ds[0]?ds[i+N]:-1); }
C.Till I Collapse
题目大意：给定n个数，对于每个1<=k<=n，求把数列分成若干段，每段数字种数不超过k，至少分几段。（n<=100,000）
思路：对于k<=n^0.5，我们每次O(n)暴力统计答案，对于k>n^0.5，我们先预处理出k=n^0.5时分成的至多n^0.5段，每段的右端点和各种数字的出现次数，每次把所有右端点向右推即可知道k+1时的信息，右端点每向右推一位我们都只要O(1)，总复杂度O(n^1.5)。
#include<cstdio> inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 100000 #define MK 320 int a[MN+5],f[MK+5][MN+5],cnt[MK+5],r[MK+5],ans; int main() { int n=read(),i,j,k; for(i=1;i<=n;++i)a[i]=read(); for(i=1;i<=n&&i<=MK;++i) { for(ans=j=0;j++<=n;) if(j>n||(!f[0][a[j]]++&&++cnt[0]>i)) { for(k=j>n?n:j;cnt[0];--k)if(!--f[0][a[k]])--cnt[0]; if(j<=n)f[0][a[j]]=cnt[0]=1;++ans; } printf("%d ",ans); } if(i<=n) { for(ans=j=1;j<=n;r[ans]=++j) if(!f[ans][a[j]]++&&++cnt[ans]>i) { --f[ans][a[j]];--cnt[ans]; ++f[++ans][a[j]];++cnt[ans]; } printf("%d ",ans); } for(++i;i<=n;++i) { for(j=1;j<=ans;++j) { for(k=r[j];k<=n;r[j]=++k) { if(!--f[j+1][a[k]])--cnt[j+1]; if(!f[j][a[k]]++&&++cnt[j]>i) { if(!--f[j][a[k]])--cnt[j]; if(!f[j+1][a[k]]++)++cnt[j+1]; break; } } if(k>n)ans=j; } printf("%d ",ans); } }