A - The Fair Nut and Elevator
#include<bits/stdc++.h> using namespace std; #define freread freopen("input.txt","r",stdin); #define frewrite freopen("output.txt","w",stdout); typedef long long ll; const int dell[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; const int maxn=2e6+7; const ll mod=998244353; const int inf=(1LL<<31)-1; int n,m,k,ar[maxn]; int main() { ll mx=1e9; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",ar+i); for(int i=1;i<=n;i++){ ll mid=0; for(int j=1;j<=n;j++){ mid += (abs(i-j)+abs(j-1)+abs(i-1))*2LL*ar[j]; } mx=min(mx,mid); } printf("%lld ",mx); return 0; }
B - Kvass and the Fair Nut
#include<bits/stdc++.h> using namespace std; #define freread freopen("input.txt","r",stdin); #define frewrite freopen("output.txt","w",stdout); typedef long long ll; const int dell[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; const int maxn=2e6+7; const ll mod=998244353; const int inf=(1LL<<31)-1; int n,m,k,ar[maxn]; int main() { ll s,mx=1e9+1,al=0; scanf("%d%lld",&n,&s); for(int i=1;i<=n;i++){ scanf("%d",ar+i); mx=min(mx,1LL*ar[i]); al+=ar[i]; } if(al<s){ printf("-1 "); } else{ ll last=s-(al-mx*n); if(last>0){ mx=mx - (last-1)/n - 1; } printf("%d ",mx); } return 0; }
C - The Fair Nut and String
考虑abaaaba类似的区间，连续的b序列等同于一个b，对每一个a,可以考虑之前一共有多少中状态（s）可以让以此a结尾，对于之前的每一段两个b之间的a 的数量ins，s*=(ins+1)，即此连续的a中，可以选任意一个a或者全都不选，共ins+1种情况
#include<bits/stdc++.h> using namespace std; #define freread freopen("input.txt","r",stdin); #define frewrite freopen("output.txt","w",stdout); typedef long long ll; const ll mod=1e9+7; const int dell[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; const int maxn=2e6+7; const int inf=(1LL<<31)-1; int n,m,k,ar[maxn]; char ch[maxn]; int main() { scanf("%s",ch); n=strlen(ch); char pre='b'; int ins=1; ll ans=0,s=1; for(int i=0;i<n;i++){ if(ch[i]=='a'){ if(pre=='a'){ ins++; ans = (ans + s)%mod; } else{ pre='a'; ins=1; ans = (ans + s)%mod; } } else if(ch[i]=='b'){ if(pre=='a'){ s = s*(ins+1)%mod; pre='b'; ins=1; } } } printf("%lld ",ans); return 0; }
D - The Fair Nut and the Best Path
对树中任意一颗子树的根节点，考虑他的每一颗子树，求出所有子树中对该点的最大贡献值和次大贡献值，则如果任意两颗子树连接的序列作为目标序列的话，权值和一定为mx1+mx2-ar[u]（当前点的权值）
#include<bits/stdc++.h> using namespace std; #define freread freopen("input.txt","r",stdin); #define frewrite freopen("output.txt","w",stdout); typedef long long ll; const ll mod=1e9+7; const int dell[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; const int maxn=2e6+7; const int inf=(1LL<<31)-1; int n,m,k,ar[maxn]; vector<pair<int,int> > ve[maxn]; ll ans=0; ll dfs(int u,int fa){ ll mx1=ar[u],mx2=ar[u]; for(int i=0;i<ve[u].size();i++){ int v=ve[u][i].first,c=ve[u][i].second; if(v==fa)continue; ll mid=dfs(v,u); mid = mid+ar[u]-c; if(mid>mx1){ mx2=mx1; mx1=mid; } else if(mid>mx2){ mx2=mid; } } //cout<<u<<' '<<mx1<<" "<<mx2<<endl; ans=max(ans, mx1+mx2-ar[u]); //ans=max(ans, mx1+pre); return mx1; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",ar+i); } for(int i=1;i<n;i++){ int a,b,c;scanf("%d%d%d",&a,&b,&c); ve[a].push_back(make_pair(b,c)); ve[b].push_back(make_pair(a,c)); } ans=0; dfs(1,0); printf("%lld ",ans); return 0; }
E - The Fair Nut and Strings
此题等同于，在深度为n，字典序在s，t之间的所有字符串形成的不完全二叉树中，对每一个深度存在的节点数目num，ans+=min(num,k);即此深度中对答案的贡献值，为k和num的最小值；
此问题变为求每一个深度的节点数
如果在当前深度，二叉树未发生分叉，则ans++
否则，开始考虑不在s,t上的节点，数量记为pre，深度每+1，pre*=2（每一个当前不在s,t上的节点会产生两个不在s,t上的节点）;如果s,t在当前深度的字符分别为(a,b)，则会另外产生2个不在s,t上的节点，如果为(a,a)或者(b,b)，会产生一个不在s,t上的节点，如果为(b,a)不产生额外的不在s,t上的节点，每次ans更新时，需要另加上s,t上的两个节点，遍历维护pre并更新ans即可；
#include<bits/stdc++.h> using namespace std; #define freread freopen("input.txt","r",stdin); #define frewrite freopen("output.txt","w",stdout); typedef long long ll; const ll mod=1e9+7; const int dell[8][2]={{1,2},{1,-2},{2,1},{2,-1},{-1,2},{-1,-2},{-2,1},{-2,-1}}; const int maxn=2e6+7; const int inf=(1LL<<31)-1; int n,m,k,ar[maxn]; char c1[maxn],c2[maxn]; int main() { scanf("%d%d",&n,&k); scanf("%s",c1); scanf("%s",c2); ll ans=0,pre=0; bool fond=0; for(int i=0;i<n;i++){ ll now=0; if(c1[i]=='a'){ if(c2[i]=='b'){ now=2; } else now=1; } else{ if(c2[i]=='a')now=0; else now=1; } if(!fond){ if(now==2)fond=1; ans += min(now,k*1LL); continue; } pre=min(k*1LL,pre*2+now); ans += min(k*1LL,pre+2); //cout<<i<<" "<<min(k*1LL,pre+2)<<endl; } printf("%lld ",ans); return 0; }