A：ABB
题解：马拉车模板题。直接跑马拉车，然后输出 len-其可最大覆盖的回文串长 即可
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=4e5+5; char s[maxn]; char str[maxn<<1]; int p[maxn<<1],n; int init(){ int len=strlen(s); str[0]='@',str[1]='#'; int j=2; for(int i=0;i<len;i++) str[j++]=s[i],str[j++]='#'; str[j]=' '; return j; } void manacher(){ int ans=-1,len=init(),mx=0,id=0; for (int i=1;i<len;i++) { if(i<mx) p[i]=min(p[id*2-i],mx-i); else p[i]=1; while(str[i+p[i]]==str[i-p[i]]) p[i]++; if(p[i]+i>mx) mx=p[i]+i,id=i; } ll res=INF; for(int i=1;i<len;i++){ int cur=(p[i]-1); if(i+cur==len-1){ res=min(res,1LL*(len-2*cur-2)/2); } } cout<<res<<endl; } int main(){ scanf("%d",&n); cin>>s; manacher(); }
B:Bob in Wonderland
题解：我用的是dfs求直径确定最长链端点+长链剖分,对于长链剖分那块，如果该点有非长儿子的点即++ans。但是好像想复杂了，我看别人好像直接判断入度即可。
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=3e5+5; int tot,head[maxn]; struct E{ int to,next; }edge[maxn<<1]; void add(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } int n,d[maxn],f_num,ans; void dfs(int x,int fa){ if(ans<d[x]){ ans=d[x]; f_num=x; } for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa) continue; d[v]=d[x]+1; dfs(v,x); } } int pre[maxn],len[maxn],son[maxn]; void dfs2(int x,int fa){ int maxlen=-1; for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==fa) continue; pre[v]=x; dfs2(v,x); if(len[v]>len[son[x]]) son[x]=v; } len[x]=len[son[x]]+1; } ll res=0; void dfs3(int x,int fa){ for(int i=head[x];i!=-1;i=edge[i].next){ int v=edge[i].to; if(v==son[x]||v==fa) continue; ++res; dfs3(v,x); } if(son[x]) dfs3(son[x],x); } int main(){ scanf("%d",&n);mem(head,-1); rep(i,1,n-1){ int u,v;scanf("%d%d",&u,&v); add(u,v);add(v,u); } dfs(1,0); ans=0; dfs2(f_num,0); dfs3(f_num,0); cout<<res<<endl; } /* 11 11 10 10 1 1 2 2 3 3 4 4 5 5 6 2 7 7 8 7 9 */
E:Zeldain Garden
题解：找规律+整除分块。因为是solo+自己不是数论手所以自己并不会整除分块，就白给了。大概规律就是从1-n中，每个数i出现的次数是n/i，然后暴力做法就是直接加起来然后类前缀和处理一下。但是n，m是1e12所以需要整除分块优化一下。
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; ll f(ll x){ ll ans=0; ll t=sqrt(double(x)); rep(i,1,t){ ans+=x/i; } return ans*2-t*t; } int main(){ ll L,R;cin>>L>>R; ll t=f(R)-f(L-1); cout<<t<<endl; }
H:Ponk Warshall
题解：s串和t串找环来搞，如果环长度为2，那么ans+=1；如果环长度为3，ans+=2;如果环长度为4，ans+=3。
#include<bits/stdc++.h> #pragma GCC optimize(2) #define ll long long #define rep(i,a,n) for(int i=a;i<=n;i++) #define per(i,n,a) for(int i=n;i>=a;i--) #define endl ' ' #define eps 0.000000001 #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) #define IO ios::sync_with_stdio(false);cin.tie(0); using namespace std; const int INF=0x3f3f3f3f; const ll inf=0x3f3f3f3f3f3f3f3f; const int mod=1e9+7; const int maxn=1e5+5; int mp[20][20]; int id(char x){ if(x=='A') return 0; if(x=='C') return 1; if(x=='T') return 2; if(x=='G') return 3; } int main(){ string s,t;cin>>s>>t; for(int i=0;i<s.length();i++){ mp[id(s[i])][id(t[i])]++; } //situation 2 ll ans=0; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ if(i==j) continue; int t=min(mp[i][j],mp[j][i]); mp[i][j]-=t;mp[j][i]-=t; ans+=t; } } //situation 3 for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ for(int k=0;k<4;k++){ if(i==j||i==k||j==k) continue; int t=min({mp[i][j],mp[j][k],mp[k][i]}); ans+=2*t; mp[i][j]-=t; mp[j][k]-=t; mp[k][i]-=t; } } } //situation 4 for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ for(int k=0;k<4;k++){ for(int q=0;q<4;q++){ if(i==j||i==k||i==q||j==k||j==q||k==q) continue; int t=min({mp[i][j],mp[j][k],mp[k][q],mp[q][i]}); ans+=3*t; mp[i][j]-=t; mp[j][k]-=t; mp[k][q]-=t; mp[q][i]-=t; } } } } cout<<ans<<endl; }