AtCoder （ABC 416）于上周六晚上20:00进行，周日晚 19:00我们在B站进行了AtCoder Beginner Contest 416的题解直播讲解，以下为本次比赛真题直播解析报告。
AtCoder （ABC 417）将于本周六晚上20:00进行。本周日晚19:00我们将继续再在B站开始AtCoder Beginner Contest 417的题解直播讲解，同学们关注！
ABC416主讲老师：清华姚班 郑老师（NOI2022金牌）
欢迎加入ABC交流QQ群咨询、沟通、交流（群密码：AtCoder）
ABC416比赛真题讲解
题目列表：
题目地址：https://atcoder.jp/contests/abc416/tasks
ABC416题解及参考程序（文字版）
========================================
参考程序
A
#include
usingnamespacestd;
constint N= 105;
intn,L,R;
chars[N];
intmain{
scanf( "%d%d%d%s",&n,&L,&R,s);
for( inti=L -1;i<=R -1;++i)
if(s[i]!= 'o') {
puts( "No");
return0;
}
puts( "Yes");
return0;
}
B
#includeusingnamespacestd;constint N= 105; chars[N]; intmain{ scanf( "%s",s); intn= strlen(s); for( inti= 0;iif(s[i]== '.'&&(i== 0||s[i -1]== '#')) s[i]= 'o'; puts(s); return0;}C
#includeusingnamespacestd;constint N= 15; intn,k,x; strings[N]; vector< string> ans; voiddfs( intu, stringnow){ if(u==k+ 1) { ans.push_back(now);return; }for( inti= 1;i<=n;++i) dfs(u+ 1,now+s[i]); }intmain{cin>>n>>k>>x;for( inti= 1;i<=n;++i) cin>>s[i];dfs( 1, string( "")); sort(ans.begin,ans.end);cout<-1]<return0;}D
#includeusingnamespacestd;typedeflonglong ll;constint N= 3e5+ 5; intn,a[N],b[N],M; intmain{ ios:: sync_with_stdio( 0); intT; cin>>T; while(T--) { cin>>n>>M;for( inti= 1;i<=n;++i) cin>>a[i];for( inti= 1;i<=n;++i) cin>>b[i];sort(a+ 1,a+n+ 1); sort(b+ 1,b+n+ 1); ll ans= 0; for( inti= 1;i<=n;++i) ans+=a[i]+b[i];intpt=n+ 1,rest= 0; for( inti= 1;i<=n;++i) { while(pt> 1&&b[pt -1]+a[i]>=M) --pt,++rest;if(rest) --rest,ans-=M; }cout<}return0;}E
#includeusingnamespacestd;typedeflonglong ll;constint N= 505; constll INF= 1e18; intn,m,k,q,T; ll G[N][N],f[N][N];boolvis[N]; intmain{ ios:: sync_with_stdio( 0); cin>>n>>m;for( inti= 1;i<=n;++i) for( intj= 1;j<=n;++j) G[i][j]=INF;for( inti= 1;i<=n;++i) G[i][i]= 0; for( inti= 1;i<=m;++i) { intu,v,w; cin>>u>>v>>w;G[u][v]= min(G[u][v],w+ 0ll); G[v][u]= min(G[v][u],w+ 0ll); }cin>>k>>T;for( inti= 1;i<=k;++i) { intx; cin>>x,vis[x]= 1; }cin>>q;for( inti= 1;i<=n;++i) if(vis[i]) { for( intj=i+ 1;j<=n;++j) if(vis[j]) { G[i][j]= min(G[i][j],T+ 0ll); G[j][i]= min(G[j][i],T+ 0ll); }}for( inti= 1;i<=n;++i) for( intj= 1;j<=n;++j) f[i][j]=G[i][j];for( intk= 1;k<=n;++k) for( inti= 1;i<=n;++i) for( intj= 1;j<=n;++j) f[i][j]= min(f[i][j],f[i][k]+f[k][j]); //Floyd
while(q--) { intop,x,y,t; cin>>op;if(op== 3) { ll ans= 0; for( inti= 1;i<=n;++i) for( intj= 1;j<=n;++j) if(f[i][j]cout<continue; }cin>>x;if(op== 1) { cin>>y>>t;G[x][y]=G[y][x]= min(G[x][y],t+ 0ll); f[x][y]=f[y][x]= min(f[x][y],t+ 0ll); } else{ vis[x]= 1; for( inti= 1;i<=n;++i) if(vis[i]) { G[i][x]=G[x][i]= min(G[i][x],T+ 0ll); f[i][x]=f[x][i]= min(f[i][x],T+ 0ll); }} //update G and f
for( intk= 1;k<=n;++k) { for( inti= 1;i<=n;++i) f[i][x]= min(f[i][x],f[i][k]+f[k][x]); for( inti= 1;i<=n;++i) f[x][i]= min(f[x][i],f[x][k]+f[k][i]); }//simulate Floyd for k=1...n and (i=x or j=x)for( inti= 1;i<=n;++i) for( intj= 1;j<=n;++j) f[i][j]= min(f[i][j],f[i][x]+f[x][j]); //simulate Floyd for k=x (the last round)}return0;}
F
#includeusingnamespacestd;typedeflonglong ll;constint N= 2e5+ 5; constll INF= 1e18; intn,a[N],k; vector< int> G[N]; ll dp[N][ 10][ 3],tmp[ 10][ 3],f[N][ 10]; voiddfs( intu, intfa){ for( inti= 0;i<=k;++i) dp[u][i][ 0]=dp[u][i][ 1]=dp[u][i][ 2]=-INF; dp[u][ 0][ 0]= 0; dp[u][ 1][ 1]=a[u]; for( inti= 0;i<=k;++i) f[u][i]= max({dp[u][i][ 0],dp[u][i][ 1],dp[u][i][ 2]}); for( autov:G[u]) if(v!=fa) { dfs(v,u); for( inti= 0;i<=k;++i) tmp[i][ 0]=tmp[i][ 1]=tmp[i][ 2]=-INF; for( inti= 0;i<=k;++i) { for( intj= 0;j<=k;++j) { tmp[i+j][ 0]= max(tmp[i+j][ 0],dp[u][i][ 0]+f[v][j]); tmp[i+j][ 1]= max(tmp[i+j][ 1],dp[u][i][ 1]+f[v][j]); tmp[i+j][ 2]= max(tmp[i+j][ 2],dp[u][i][ 2]+f[v][j]); if(i+j<=k) tmp[i+j][ 1]= max(tmp[i+j][ 1], dp[u][i][ 0]+a[u]+dp[v][j][ 1]); if(i&&j&&i+j -1<=k) tmp[i+j -1][ 2]= max(tmp[i+j -1][ 2], dp[u][i][ 1]+dp[v][j][ 1]); }}memcpy(dp[u],tmp, sizeoftmp); for( inti= 0;i<=k;++i) f[u][i]= max({dp[u][i][ 0],dp[u][i][ 1],dp[u][i][ 2]}); }}intmain{ scanf( "%d%d",&n,&k); for( inti= 1;i<=n;++i) scanf( "%d",&a[i]); for( inti= 1;iintu,v; scanf( "%d%d",&u,&v); G[u]. push_back(v); G[v]. push_back(u); }dfs( 1, 0); ll ans= 0; for( inti= 0;i<=k;++i) ans= max({ans,dp[ 1][i][ 0],dp[ 1][i][ 1],dp[ 1][i][ 2]}); printf( "%lld\n",ans); return0;}
G
#includeusingnamespacestd;intn,k; string s[ 15]; intanscnt=- 1; string ans; vector tmp;stringqpow( intx,string a){ string z= ""; for( inti= 1;i<=x;++i) z+=a;returnz; } // a^xboolcmp( intcnt,string now){ if(anscnt==- 1) return1; if(cntreturnnow < qpow(anscnt-cnt,tmp[ 0]) + ans; } else{ returnqpow(cnt-anscnt,tmp[ 0]) + now < ans; }}// To express a string, we use an integer "cnt"anda string "now"// (cnt,now) represents (s[ 1])^cnt + now // cmp returns whether (cnt,now) < (anscnt,ans)voiddfs( intu, intsum,string now){ if( sum>k) { return; }if(u==tmp.size) { intcnt=k- sum; if(cmp(cnt,now)) { anscnt=cnt;ans=now;}return; }string res= ""; intmaxcnt=( 10+tmp[u].size- 1)/tmp[u].size; for( inti= 0;i<=maxcnt;++i) { dfs(u+ 1, sum+i,now+res); res+=tmp[u];}}intmain{ios::sync_with_stdio( 0); cin>>n>>k;for( inti= 1;i<=n;++i) { string str; cin>> str; intlen= str.size; if(s[ len].size) s[ len]= min(s[ len], str); elses[ len]= str; }sort(s+ 1,s+ 10+ 1,[](conststring &a,conststring &b) { if(a+b!=b+a) returna+breturna.size});intL= 11; for( inti= 1;i<= 10;++i) if(s[i]!= "") { if(s[i].sizeL=s[i].size;tmp.push_back(s[i]);}}dfs( 1, 0,string( "")); cout<0])+ans<return0;}题库地址：https://atcoder.jp
针对每周六20:00举办的ABC比赛，我们每周日都会对比赛直播。
