B. 大意就是尽量弄成单个字母那种，这一定是最优的。我们首先扫一遍当前序列，找出当前情况下出现次数最多的子串（字母），然后如果除了这个字母以外，剩下的字母个数比n大的话，答案就是出现次数+n。 否则，如果替换剩下所有字母后n还剩偶数次，那么我们随便找一个字母消磨掉次数即可。否则的话，最后一个字母被替换掉我们不做替换，这样剩下偶数次，头两次内我们把那个没换的字母换成我们想要的字母，然后消磨掉剩下的次数即可。但是注意，n=1时要特判。
#include<cstdio> #include<iostream> #include<string> #include<map> #include<cstring> using namespace std; int main() { string s[3];int n,i,maxn[3]={0}; cin>>n;getchar(); for(i=0;i<3;i++) getline(cin,s[i]); int cnt=0; map<char,int>ys[3]; for(i=0;i<3;i++){ cnt=0; for(auto a:s[i]){ cnt=max(cnt,++ys[i][a]); } int len=s[i].size();maxn[i]=cnt; if(len==cnt){ if(n==1)maxn[i]--;//这种情况下n是需要特判的 //else maxn[i]=len; } else{ if(len-cnt<=n)maxn[i]=len; else maxn[i]=cnt+n; } } if(maxn[0]>maxn[1]&&maxn[0]>maxn[2]){ puts("Kuro"); } else if(maxn[1]>maxn[0]&&maxn[1]>maxn[2]){ puts("Shiro"); } else if(maxn[2]>maxn[0]&&maxn[2]>maxn[1]){ puts("Katie"); } else {//注意平局的情况是除了有人胜出之外的所有情况 puts("Draw"); } return 0; }C. 首先，这幅图是一棵树。与其计算有多少路是可以选的，我们不如计算有多少路是不可以选的。我们会发现，如果我们以y为整棵树的根节点，那么不可选的路，就是以x为根节点的子树的节点数，乘上以y为根节点的树的节点数-（以y为直接祖先并且以x为子节点的点为根的子树的节点数）。 dfs一遍即可，dfs的时候返回两个值，一个是这个节点是否是x的祖先，其次是这个节点的子节点（包括自己）个数。
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; typedef long long ll; vector<int>G[300005];int n,x,y,cntx=0,cnty=0,cntz=0;bool vis[300005]; typedef pair<int,bool>f; f dfs(int i,int pre) { vis[i]=true; bool isx=false;int cnt=1; for(auto a:G[i]){ if(!vis[a]){ f f1=dfs(a,i); if(f1.second)isx=true; cnt+=f1.first; } } if(i==x)cntx=cnt,isx=true; if(pre==y&&isx)cntz=cnt; if(i==y)cnty=cnt; return f(cnt,isx); } int main() { cin>>n>>x>>y; int i,j; for(i=1;i<n;i++){ int a,b;scanf("%d%d",&a,&b); G[a].push_back(b);G[b].push_back(a); } dfs(y,-1); cout<<(ll)n*(n-1)-(ll)cntx*(ll)(cnty-cntz)<<endl; return 0; }