A. We Need the Zero
题意：给出一个数组，对任意1<=i<=n，令bi=aix，问是否存在x，使得b<sub>1</sub>b2...bn=0
Solution
如果n为奇数，那么x一定存在，因为偶数个x异或得到的是0，直接令x=0(a<sub>1</sub>a2...an)即可
如果n为偶数，那么x取任何值都不会影响结果，所以只用看a1a<sub>2</sub>...^an是否为0即可
void solve()
{
int n;cin>>n;
int sum;
for(int i=1;i<=n;i++)
{
int x;cin>>x;
if(i==1)sum=x;
else sum^=x;
}
if(n&1)cout<<(0^sum)<<"\n";
else
{
if(sum==0)cout<<"1\n";
else cout<<"-1\n";
}
}
B. The String Has a Target
题意：给出一个字符串，要求进行一次且仅进行一次操作，使得操作后的字符串字典序最小
操作：选择一个字符，将其移到字符串首
Solution
对直接从头到尾遍历最小的字符的位置即可
void solve()
{
int n;cin>>n;
string s;cin>>s;
char f=s[0];
int pos=0;
for(int i=1;i<n;i++)
{
if(s[i]<=s[pos])
{
pos=i;
}
}
cout<<s[pos];
for(int i=0;i<n;i++)
{
if(i!=pos)cout<<s[i];
}
cout<<"\n";
}
C. Place for a Selfie
题意：给出n条解析式为y=kx的直线的k，和m条解析式为y=ax2+bx+c的抛物线的a,b,c，对每一条抛物线进行询问：是否存在一条直线与该抛物线不相交也不相切，并给出任意一条直线的k值
Solution
令ax2+bx+c=kx，于是我们可以得到ax2+(b-k)x+c=0
根据判别式可得，当满足题意的直线存在时，满足不等式(b-k)2<4ac
于是我们需要找到离b最近的k值，对k由小到大排序，进行二分查找即可
void solve()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)cin>>k[i];
sort(k+1,k+1+n);
for(int i=1;i<=m;i++)
{
int a,b,c;cin>>a>>b>>c;
if(c<0)cout<<"NO\n";
else
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(k[mid]<b)l=mid+1;
else r=mid;
}
int x=b-k[l];
int flag=0;
if(x*x<4*a*c)flag=1;
if(l>1)
{
int y=b-k[l-1];
if(y*y<4*a*c)
{
flag=1;
l--;
}
}
if(flag)
{
cout<<"YES\n";
cout<<k[l]<<"\n";
}else cout<<"NO\n";
}
}
cout<<"\n";
}
D. A Wide, Wide Graph
题意：给出一棵树，令图Gk上的结点与树相同，在树的任意两个点<u,v>，当<u,v>的距离大于等于k时，将<u,v>的边加入到图Gk中，询问对于k=1,2,...,n，Gk有多少个连通分量
Solution
对于一个结点，如果他所能到达的最远的距离小于k，它才会被独立成一个连通分量
于是问题就转变为了如何求所有结点所能到达的最大距离
不难发现结点i能到达的最大距离d[i]=max(f[i],g[pre])，其中f[i]表示从i向下的子树走所能到达的最大距离，g[pre]表示从父节点pre能走的最长距离，这个距离可以向i的兄弟结点走，也可以向pre的父节点继续走直到走到头
对于前一种向子树走，我们可以用树形dp来求
void dfs(int x,int pre)
{
dp[x]=0;
for(auto it:e[x])
{
if(it!=pre)
{
dfs1(it,x);
if(dp[it]+1>dp[x])dp[x]=dp[it]+1;
}
}
}
但是对于第二种就有点麻烦了，首先我们需要预处理出从i开始向子树走所能到达的第二大的距离，第一大和第二大的距离分别设为为dp[i] [0]和dp[i] [1]，因为要如果从兄弟结点开始走，就需要判断dp[pre] [0]对应的子结点是不是i，如果是i则距离最长为dp[pre] [1]加上到pre的距离，如果不是i，那么就是dp[pre] [0]加上到pre的距离，最后再与g[pre]作比较，从而得到g[i]
这里直接把g[i]设为dp[i] [2]
void dfs1(int x,int pre) //预处理从x向子树走的最大距离和第二大距离以及最大距离对应的子结点
{
dp[x][0]=dp[x][1]=dp[x][2]=0;
for(auto it:e[x])
{
if(it!=pre)
{
dfs1(it,x);
if(dp[it][0]+1>dp[x][0])
{
to[x]=it;
dp[x][1]=dp[x][0];
dp[x][0]=dp[it][0]+1;
}else if(dp[it][0]+1>dp[x][1])
{
dp[x][1]=dp[it][0]+1;
}
}
}
}
void dfs2(int x,int pre) //处理从x向兄弟结点或者向父节点的父节点走的最大距离
{
for(auto it:e[x])
{
if(it!=pre)
{
//这里注意因为是从上往下修改的，所以是先修改再进行遍历，而不是一般树形dp的先看子结点再看父节点
dp[it][2]=max(dp[x][2],to[x]==it?dp[x][1]:dp[x][0])+1;
dfs2(it,x);
}
}
}
预处理跑完后，剩下的就是把最大距离小于k的点都去掉，去掉的点数+1就是连通分量个数了
void dfs1(int x,int pre)
{
dp[x][0]=dp[x][1]=dp[x][2]=0;
for(auto it:e[x])
{
if(it!=pre)
{
dfs1(it,x);
if(dp[it][0]+1>dp[x][0])
{
to[x]=it;
dp[x][1]=dp[x][0];
dp[x][0]=dp[it][0]+1;
}else if(dp[it][0]+1>dp[x][1])
{
dp[x][1]=dp[it][0]+1;
}
}
}
}
void dfs2(int x,int pre)
{
for(auto it:e[x])
{
if(it!=pre)
{
dp[it][2]=max(dp[x][2],to[x]==it?dp[x][1]:dp[x][0])+1;
dfs2(it,x);
}
}
}
void solve()
{
int n;cin>>n;
for(int i=1;i<n;i++)
{
dp[i][0]=dp[i][1]=dp[i][2]=0;
int u,v;cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs1(1,0);
dfs2(1,0);
for(int i=1;i<=n;i++)
{
a[i]=max(dp[i][0],dp[i][2]);
//cout<<a[i]<<" ";
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{
int l=1,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(a[mid]<i)l=mid+1;
else r=mid;
}
if(a[l]>=i)cout<<l<<" ";
else if(a[l]<i)cout<<n<<" ";
}
cout<<"\n";
}