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[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X;
}
#define MN 7000
int n,s[],t[][MN+],u[MN*+],q[MN*+],l[MN*+],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^=;u[p]=;
for(i=;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]=;
for(i=;i<=s[x];++i)
{
v=d(x,y-t[x][i]);
if(!u[v])win(v);
}
}
int main()
{
fread(B,,<<,stdin);
int i,x,y;
for(n=read(),x=;x<;++x)for(s[x]=read(),i=;i<=s[x];++i)t[x][i]=read();
u[n]=;lose();lose(n);
for(i=;i<n;++i)printf("%s ",u[i]?u[i]>?"Win":"Lose":"Loop");puts("");
for(i=;i<n;++i)printf("%s ",u[i+n]?u[i+n]>?"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[<<],*S=B,C;int X;
inline int read()
{
while((C=*S++)<''||C>'');
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
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+];
int h[MV+],en;ll ds[MV+];
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-,r+=N+;l^r^;l>>=,r>>=)
{
if(~l&)ins(f+N,l+,w);
if( r&)ins(f+N,r-,w);
}
}
void ins2(int l,int r,int t,int w)
{
for(l+=N-,r+=N+;l^r^;l>>=,r>>=)
{
if(~l&)ins(l++(N<<),t+N,w);
if( r&)ins(r-+(N<<),t+N,w);
}
}
int main()
{
fread(B,,<<,stdin);
int n,m,i,s,a,b,c,d;ll x;
n=read();m=read();s=read();
for(i=;i<N;++i)
{
ins(i,i<<,);ins(i,i<<|,);
ins(i+N<<,i+(N<<),);ins(i+N<<|,i+(N<<),);
ins(i+N,i+N*,);ins(i+N*,i+N,);
}
while(m--)
{
a=read();b=read();c=read();d=read();
if(a==)ins(b+N,c+N,d);
if(a==)ins1(c,d,b,read());
if(a==)ins2(c,d,b,read());
}
memset(ds,,sizeof(ds));ds[s+N]=;pq.push(d(,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=;i<=n;++i)printf("%I64d ",ds[i+N]<ds[]?ds[i+N]:-);
}
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())<''||c>'');
for(x=c-'';(c=getchar())>=''&&c<='';)x=(x<<)+(x<<)+c-'';
return x;
}
#define MN 100000
#define MK 320
int a[MN+],f[MK+][MN+],cnt[MK+],r[MK+],ans;
int main()
{
int n=read(),i,j,k;
for(i=;i<=n;++i)a[i]=read();
for(i=;i<=n&&i<=MK;++i)
{
for(ans=j=;j++<=n;)
if(j>n||(!f[][a[j]]++&&++cnt[]>i))
{
for(k=j>n?n:j;cnt[];--k)if(!--f[][a[k]])--cnt[];
if(j<=n)f[][a[j]]=cnt[]=;++ans;
}
printf("%d ",ans);
}
if(i<=n)
{
for(ans=j=;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=;j<=ans;++j)
{
for(k=r[j];k<=n;r[j]=++k)
{
if(!--f[j+][a[k]])--cnt[j+];
if(!f[j][a[k]]++&&++cnt[j]>i)
{
if(!--f[j][a[k]])--cnt[j];
if(!f[j+][a[k]]++)++cnt[j+];
break;
}
}
if(k>n)ans=j;
}
printf("%d ",ans);
}
}