唉，昨天晚上迷迷糊糊地去打cf，结果fst两题，掉回蓝了...
A.Andryusha and Colored Balloons
题意：给定一棵树，任意两个距离小等于二的点不能染相同的颜色，求最小颜色数和染色方案。 n<=2*10^5
题解：求一个度数最大的点，度数+1即是颜色数，然后暴力染色。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#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;
} struct edge{
int to,next;
}e[];
int head[];
int n,rt,cnt=;
bool b[];
int ans=;
int num[];
int col[];
int beg[]; void ins(int f,int t)
{
e[++cnt].next=head[f];head[f]=cnt;
e[cnt].to=t;
} void dfs(int x,int fa)
{
num[x]=;
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=fa)
{
dfs(e[i].to,x);
num[x]++;
}
if(fa!=)num[x]++;
} void solve(int x,int fa)
{
// cout<<"solve"<<x<<" "<<fa<<" "<<col[x]<<" "<<col[fa]<<endl;
int c=;
for(int i=head[x];i;i=e[i].next,c=c+)
if(!col[e[i].to])
{
while(c==col[x]||c==col[fa])c=c+;
col[e[i].to]=c;
solve(e[i].to,x);
}
else c--;
} int main()
{
n=read();
for(int i=;i<n;i++)
{int u=read(),v=read();ins(u,v);ins(v,u);}
dfs(,);for(int i=;i<=n;i++)if(num[i]>ans){ans=num[i];rt=i;}
col[rt]=;solve(rt,);printf("%d\n",ans);
for(int i=;i<=n;i++)printf("%d ",col[i]);
return ;
}
B.Innokenty and a Football League
题意：有n个足球队，每个队有两个选名字的方案，也就是直接给定了两个名字。所有球队不能有相同的名字。
特殊的，如果有两个球队第一个名字相同，一个球队选了第二个名字，另一个球队不能选第一个名字。n<=1000
题解：2-sat
据说有个学长188行大暴力过了，真的佩服。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#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 n,dn=;
char ch[][];
char s[];
int h1[],h2[],q[];
bool inq[];
struct edge{
int to,next;
}e[];
int head[],dfn[],low[],bel[],col[],in[];
int cnt=,cc,top=,cft[];
queue<int> qu; void ins(int f,int t)
{
e[++cnt].next=head[f];head[f]=cnt;
e[cnt].to=t;
} void hashh(int k)
{
// cout<<k<<" "<<ch[k][1]<<" "<<ch[k][2]<<" "<<ch[k][3]<<" "<<ch[k][4]<<endl;
int hash1,hash2;
hash1=hash2=(ch[k][]-'A')*+ch[k][]-'A';
hash1=hash1*+(ch[k][]-'A');
hash2=hash2*+(ch[k][]-'A');
h1[k]=hash1;h2[k]=hash2;
} void tj(int x)
{
//cout<<"tj"<<x<<endl;
dfn[x]=low[x]=++dn;inq[x]=;q[++top]=x;
for(int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!dfn[v]){tj(v);low[x]=min(low[x],low[v]);}
else {if(inq[v])low[x]=min(low[x],dfn[v]);}
}
if(dfn[x]==low[x])
for(++cc;q[top+]!=x;bel[q[top]]=cc,inq[q[top]]=,top--);
} void rebuild()
{
for(int i=;i<=n<<;i++)
for(int j=head[i];j;j=e[j].next)
if(bel[i]!=bel[e[j].to])
ins(bel[i],bel[e[j].to]),in[e[j].to]++;
} void topsort()
{
for(int i=n*+;i<=cc;i++)
if(in[i]==) qu.push(i);
while(!qu.empty())
{
int u=qu.front();qu.pop();
if(!col[u])
for(int j=;j<=n<<;j++)
if(bel[j]==u)
col[bel[j>n?j-n:j+n]]=;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
--in[v];
if(!in[v]) qu.push(v);
}
}
} int main()
{
n=read();cc=n<<;
for(int i=;i<=n;i++)
{
scanf("%s",s+);
ch[i][]=s[];ch[i][]=s[];ch[i][]=s[];
scanf("%s",s+);ch[i][]=s[];
hashh(i);
}
for(int i=;i<n;i++)
for(int j=i+;j<=n;j++)
{
if(h1[i]==h1[j]&&h2[i]==h2[j]) return *puts("NO");
if(h1[i]==h1[j]){ins(i,j+n);ins(j,i+n);ins(i+n,j+n);ins(j+n,i+n);}
if(h1[i]==h2[j]){ins(i,j);ins(j+n,i+n);}
if(h2[i]==h1[j]){ins(i+n,j+n);ins(j,i);}
if(h2[i]==h2[j]){ins(i+n,j);ins(j+n,i);}
}
for(int i=;i<=n*;i++)if(!dfn[i])tj(i);
//for(int i=1;i<=n;i++)cout<<bel[i]<<" "<<bel[i+n]<<endl;
for(int i=;i<=n;i++)if(bel[i]==bel[i+n])return *puts("NO");
rebuild();
topsort();
puts("YES");
for(int i=;i<=n;i++)if(col[bel[i]]==)printf("%c%c%c\n",ch[i][],ch[i][],ch[i][]);
else printf("%c%c%c\n",ch[i][],ch[i][],ch[i][]);
return ;
}
C.Underground Lab
题意：给定一个n个点m条边的连通图，然后你要用k条路径覆盖所有的点，每条路径最多2*n/k向上取整个点，求一个方案。n<=2*10^5
题解：假装它是一棵树，然后求一个欧拉序列，只有2*n-1个点，然后分段输出就行了。
注意处理输出之后不足k组的情况，乱填充一下就行。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#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 ans[];
bool b[];
struct edge{
int to,next;
}e[];
int head[];
int n,m,k,cnt=,top=,q[]; void ins(int f,int t)
{
e[++cnt].next=head[f];head[f]=cnt;
e[cnt].to=t;
} void dfs(int x,int fa)
{
b[x]=;q[++top]=x;
for(int i=head[x];i;i=e[i].next)
if(!b[e[i].to])
{
dfs(e[i].to,x);
q[++top]=x;
}
} int main()
{
n=read();m=read();k=read();
for(int i=;i<=m;i++)
{int u=read(),v=read();ins(u,v);ins(v,u);}
dfs(,);
int l=(top+k-)/k;
int i=;
for(int pre=;i<=k&&pre<top;i++,pre+=l)
{
int l2=min(l,top-pre);
printf("%d ",l2);
for(int j=;j<=l2;j++)
printf("%d ",q[pre+j]);
puts("");
}
while(i<=k){i++;printf("1 1\n");}
return ;
}
D.Axel and Marston in Bitland
给丁一个n点m边的图，然后每条边有一个类别1或者0。
你要按照给定的顺序走边：一条0的，然后把刚走的取反接起来，然后一直做。比如P代表0，B代表1，那么你要这么走：
P, PB, PBBP, PBBPBPPB, PBBPBPPBBPPBPBBP, and so on.
求最多能走多少条。如果答案>10^18，输出-1 n<=500
题解：倍增，用bitset来求出长度为k，开头是0或者1，所有点对的连通性，然后dp
用f[k][i][0/1]表示开头是0/1，第i个点，最后一次走的长度是2^k的最大距离。
复杂度：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#include<bitset>
#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;
}
bitset<> s[][][];
ll f[][][];
int n,m;
int main()
{
n=read();m=read();
for(int i=;i<=m;i++)
{
int u=read(),v=read(),w=read();
s[w][u][][v]=;
}
for(int k=;k<;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
{
if(s[][i][k][j])s[][i][k+]|=s[][j][k];
if(s[][i][k][j])s[][i][k+]|=s[][j][k];
}
memset(f,,sizeof(f));f[][][]=;
for(int k=;k>=;k--)
{
for(int i=;i<=n;i++)
{
f[][i][k]=f[][i][k+];
f[][i][k]=f[][i][k+];
}
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
if(s[][i][k][j]) f[][j][k]=max(f[][j][k],f[][i][k+]+(1LL<<k));
if(s[][i][k][j]) f[][j][k]=max(f[][j][k],f[][i][k+]+(1LL<<k));
}
}
}
ll mx=;
for(int i=;i<=n;i++)mx=max(mx,max(f[][i][],f[][i][]));
if(mx>=1000000000000000000LL)puts("-1");
else printf("%I64d\n",mx);
return ;
}