来自FallDream的博客。未经允许，请勿转载，谢谢。
----------------------------------------------------
和ditoly组队打vkcup，原来以为是正常div2难度，结果发现.....不说了 AB都被叉了一遍，又掉分 .......
-------------------------
A.给定n个人和m组朋友关系，判断这个图是否满足性质：如果x和y是朋友，y和z是朋友，那么x和z是朋友 n,m<=150000
题解：很容易发现满足关系的图是团，所以我们对每个联通块判一下就可以了。
n的范围很奇怪，我没注意，结果被hack了，发现150000*149999会爆int....
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int cnt=,n,m;
struct edge{
int to,next;
}e[];
int head[];
ll num,sum;
bool mark[]; inline void ins(int u,int v)
{
e[++cnt].next=head[u];head[u]=cnt;
e[cnt].to=v;
} void dfs(int x)
{
mark[x]=;num++;
for(int i=head[x];i;i=e[i].next,sum++)if(!mark[e[i].to])
dfs(e[i].to);
} int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{int a=read();int b=read();ins(a,b);ins(b,a);}
for(int i=;i<=n;i++)if(!mark[i])
{num=sum=;dfs(i);
if(num>&&sum!=(num-)*num)return *puts("NO");
// if(num==2&&sum!=2)return 0*puts("NO");
}
puts("YES");
return ;
}
B.给定n,k，表示有n个名字，然后给定n-k+1个条件，每个条件是YES/NO，表示从它开始的连续k个名字有没有相同的（YES表示没有），你要构造出满足题意的名字，保证有解。n<=50
题解：我们先把全部都赋成不同的名字，然后从后往前，如果第i个是NO，那么把它变成和i+k-1一样。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} int k,cnt=,n;
string name[],s;
char st[];
int res[]; string getnewname()
{
cnt++;s="A";
for(int i=cnt;i>;i-=)s=s+(char)((i-)%+'a');
return s;
} int pd(){scanf("%s",st+);return st[]=='Y'?:;} int main()
{
n=read();k=read();
for(int i=;i+k-<=n;i++) res[i]=pd();
for(int i=;i<=n;i++)name[i]=getnewname();
for(int i=n-k+;i;i--)if(res[i]) name[i]=getnewname();
else name[i]=name[i+k-];
for(int i=;i<=n;i++)cout<<name[i]<<" ";
return ;
}
C.有一棵树，每条边的权值是1，然后给定k,表示你一步可以走的距离为k。令Fst表示从s到t要走多少步，求Fij,1<=i<j<=n n<=200000 k<=5
题解：乱dp，一个表示走多少步，另一个表示没走满一步的个数。
#include<cstdio>
#include<iostream>
using namespace std;
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 200000
struct edge{int nx,t;}e[MN*+];
int k,h[MN+],en,f[MN+][];
long long ans,ff[MN+];
inline void ins(int x,int y)
{
e[++en]=(edge){h[x],y};h[x]=en;
e[++en]=(edge){h[y],x};h[y]=en;
}
void dfs(int x,int fa)
{
int i,j,l;
f[x][]=;
for(i=h[x];i;i=e[i].nx)if(e[i].t!=fa)
{
dfs(e[i].t,x);
for(j=;j<k;++j)
{
ans+=1LL*f[e[i].t][j]*ff[x]+1LL*f[x][j]*ff[e[i].t];
for(l=;l<k;++l)ans+=1LL*f[e[i].t][j]*f[x][l]*((j+l)/k+);
}
for(j=;j<k;++j)f[x][j]+=f[e[i].t][j-];
f[x][]+=f[e[i].t][k-];ff[x]+=ff[e[i].t]+f[e[i].t][k-];
}
}
int main()
{
fread(B,,<<,stdin);
int n=read(),i;k=read();
for(i=;i<n;++i)ins(read(),read());
dfs(,);
cout<<ans;
}
D.给定一个长度为n的字符串，每次你可以交换一对连续的字符，求最少的交换次数，使得字符串中没有连续的两个是"VK" n<=75
题解：我们把不是VK的字符看作一种，然后用f[i][j][k][0/1]表示前i个V，j个K，k个不是VK的字符，最后一位是／不是V的最小交换数。
我们枚举最后一位放什么，那么它需要额外的交换次数是前i个V,j个K，k个其他字符中在它之后的个数(因为那些要从后面移到前面)，然后就可以转移啦。
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-') f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-''; ch=getchar();}
return x*f;
} vector<int> v,k,o;
int n;
char st[];
ll f[][][][]; int main()
{
n=read();memset(f,,sizeof(f));
scanf("%s",st+);
for(int i=;i<=n;i++)
if(st[i]=='V') v.push_back(i);
else if(st[i]=='K')k.push_back(i);
else o.push_back(i);
f[][][][]=;
for(int i=;i<=v.size();i++)
for(int j=;j<=k.size();j++)
for(int l=;l<=o.size();l++)
for(int c=;c<=;c++)
{
if((!i)&&(!c))continue;
if((!j)&&c==)continue;
if((!l)&&c==)continue;
int pos,num=;
if(!c) pos=v[i-];
else if(c==) pos=k[j-];
else pos=o[l-];//cout<<pos<<endl;
for(int m=i;m<v.size()&&v[m]<pos;m++)num++;//cout<<num<<endl;
for(int m=j;m<k.size()&&k[m]<pos;m++)num++;//cout<<num<<endl;
for(int m=l;m<o.size()&&o[m]<pos;m++)num++;
// cout<<num<<endl;
if(c==)for(int m=;m<=;m++) f[i][j][l][]=min(f[i][j][l][],f[i-][j][l][m]+num);
if(c==)for(int m=;m<=;m++) f[i][j][l][]=min(f[i][j][l][],f[i][j-][l][m]+num);
if(c==)for(int m=;m<=;m++) f[i][j][l][]=min(f[i][j][l][],f[i][j][l-][m]+num);
// cout<<i<<" "<<j<<" "<<l<<" "<<f[i][j][l][0]<<" "<<f[i][j][l][1]<<endl;
}
int a=v.size(),b=k.size(),c=o.size();
cout<<min(f[a][b][c][],f[a][b][c][]);
return ;
}
E.给定一个2*n的矩阵，你要选出最多的和为0且不相交的矩阵，求出最多的数量。n<=300000
题解：记忆化搜索，每次选择比较靠后的往前跳，貌似是卡不掉的。
#include<cstdio>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
char B[<<],*S=B,C;ll X,F;
inline ll read()
{
for(F=;(C=*S++)<''||C>'';)if(C=='-')F=-;
for(X=C-'';(C=*S++)>=''&&C<='';)X=(X<<)+(X<<)+C-'';
return X*F;
}
#define MN 300000
#define d(x,y) make_pair(x,y)
ll s[MN+][];
int t[MN+][],f[MN+];
map<ll,int> mp;
map<pair<int,int>,int> u,ff;
int cal(int x,int y)
{
if(u[d(x,y)])return ff[d(x,y)];
return u[d(x,y)]=,ff[d(x,y)]=max(f[min(x,y)],t[x][]>t[y][]?cal(t[x][],y)+:cal(x,t[y][])+);
}
int main()
{
fread(B,,<<,stdin);
int n=read()+,i,j,k,l;
for(i=;i<=n;++i)s[i][]=s[i-][]+read();
for(i=;i<=n;++i)s[i][]=s[i-][]+read(),s[i][]=s[i][]+s[i][];
for(l=;l<;++l)for(mp.clear(),i=;i<=n;++i)t[i][l]=max(t[i-][l],mp[s[i][l]]),mp[s[i][l]]=i;
f[]=t[][]=t[][]=-;u[d(,)]=;ff[d(,)]=-;
for(i=;i<=n;++i)f[i]=max(f[t[i][]]+,cal(i,i)),ff[d(i,i)]=f[i];
printf("%d",f[n]);
}