AtCoder Beginner Contest 375 (A-G)
比赛链接
A - Seats
#include<bits/stdc++.h>using namespace std;using i64=long long;void Showball(){int n;string s;cin>>n>>s;int cnt=0;for(int i=0;i<n-2;i++){if(s[i]==s[i+2]&&s[i]=='#'&&s[i+1]=='.') cnt++;} cout<<cnt<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
B - Traveling Takahashi Problem
#include<bits/stdc++.h>using namespace std;using i64=long long;struct Point{int x,y;
};double dis(Point a,Point b){return hypot(a.x-b.x,a.y-b.y);
}void Showball(){int n;cin>>n;vector<Point> a(n+2);double ans=0;for(int i=1;i<n+1;i++){cin>>a[i].x>>a[i].y;} for(int i=0;i<n+1;i++){ans+=dis(a[i],a[i+1]);}cout<<fixed<<setprecision(9)<<ans<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
C - Spiral Rotation
直接模拟时间复杂度为 \(O(n^3)\)，手推发现，每次操作就是一层顺时针旋转 \(90\) 度。第 \(k\) 层就旋转 \(k\) 次即可。
#include<bits/stdc++.h>using namespace std;using i64=long long;void Showball(){int n;cin>>n;vector<vector<char>> a(n+1,vector<char>(n+1));for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cin>>a[i][j];}} for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){int k=min(min(i,n-i+1),min(j,n-j+1))%4;if(k==0) cout<<a[i][j];else if(k==1) cout<<a[n-j+1][i];else if(k==2) cout<<a[n-i+1][n-j+1];else cout<<a[j][n-i+1];}cout<<"\n";}}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
D - ABA
思路：
枚举中间位置，以及两边的字母即可，直接前缀和维护每个字母出现次数，然后乘法原理简单处理即可。
#include<bits/stdc++.h>using namespace std;using i64=long long;void Showball(){string s;cin>>s;int n=s.size();s="?"+s;vector<array<int,26>> pre(n+1);for(int i=1;i<=n;i++){for(int j=0;j<26;j++) pre[i][j]=pre[i-1][j];pre[i][s[i]-'A']++;}i64 ans=0;for(int i=1;i<=n;i++){for(int j=0;j<26;j++){ans+=1LL*pre[i-1][j]*(pre[n][j]-pre[i][j]);}}cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
E - 3 Team Division DP
思路：
考虑 \(dp\), 令 \(f_{i,j,k}\) 表示考虑前 \(i\) 个人，并且第一组强度之和为 \(j\), 第二组强度之和为 \(k\) 时所需的最少换队人数。
状态转移考虑第 \(i\) 个人的三种选择即可。具体看代码实现。
#include<bits/stdc++.h>using namespace std;using i64=long long;int f[510][510][510];
void Showball(){int n;cin>>n;vector<int> a(n+1),b(n+1);int sum=0;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];sum+=b[i];}if(sum%3) return cout<<"-1\n",void();memset(f,0x3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=500;j++){for(int k=0;k<=500;k++){if(j>=b[i]){f[i][j][k]=min(f[i][j][k],f[i-1][j-b[i]][k]+(a[i]!=1));}if(k>=b[i]){f[i][j][k]=min(f[i][j][k],f[i-1][j][k-b[i]]+(a[i]!=2));}f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(a[i]!=3));}}}sum/=3;int ans=f[n][sum][sum];if(ans>0x3f3f3f3f/2) ans=-1;cout<<ans<<"\n";
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
F - Road Blocked 最短路
考虑到删除边不好操作，并且最多只会删除 \(300\) 条边。我们可以考虑离线处理。把所有的操作存起来，倒着进行加边处理即可。每次加边，就考虑新加的边来做端点的情况来更新最短路即可。多源最短路用 \(Floyd\) 即可。
#include<bits/stdc++.h>using namespace std;using i64=long long;const i64 inf = 0x3f3f3f3f3f3f3f3f;
void Showball(){int n,m,q;cin>>n>>m>>q;vector<vector<i64>> f(n+1,vector<i64>(n+1,inf));vector<array<i64,3>> e(m),Q(q);for(int i=1;i<=n;i++) f[i][i]=0;for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;e[i]={u,v,w};}vector<int> st(m);for(int i=0;i<q;i++){int op,x,y=0;cin>>op>>x;if(op==1){st[x-1]=1;}else{cin>>y;}Q[i]={op,x,y};}for(int i=0;i<m;i++){if(!st[i]){auto [u,v,w]=e[i];f[u][v]=min(f[u][v],w); f[v][u]=min(f[v][u],w); }}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}}}vector<i64> ans(q);for(int i=q-1;i>=0;i--){auto [op,x,y]=Q[i];if(op==1){auto [u,v,w]=e[x-1];f[u][v]=min(f[u][v],w); f[v][u]=min(f[v][u],w);for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){f[i][j]=min({f[i][j],f[i][u]+f[v][j]+w,f[i][v]+f[u][j]+w});}} }else{ans[i]=f[x][y];}}for(int i=0;i<q;i++){if(Q[i][0]==2) cout<<(ans[i]>=inf?-1:ans[i])<<"\n";}
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
G - Road Blocked 2 Dijkstra+Tarjan
首先判断这条边是否出现在 \(1-n\) 的最短路上，如果没有出现，那就没有影响。
判断方法，我们只需要用 \(Dijkstra\) 分别维护出 \(1\) 到所有点最短路 $d_1 $和 $n $ 到所有点的最短路 \(d_2\) 。
令该条边为 \(u-v\)。权值为 \(w\) ，\(1-n\) 之间的最短路为 \(dis\) 。那么如果 \(d1_u+d2_v+w = dis || d1_v+d2_u+w = dis\)
说明改变在最短路上。
接下来考虑在最短路上的边。很明显只有该边是割边的时候，删到该边才会产生影响。
因此，我们将所有在最短路上的边存下来，重新建图，跑一遍 \(tarjan\) 求一下割边即可。
思路比较简单，就是模板组合题。很适合练手。
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
void Showball(){int n,m;cin>>n>>m;vector<vector<array<int,2>>> e(n);vector<array<int,3>> edge(m);for(int i=0;i<m;i++){int u,v,w;cin>>u>>v>>w;u--;v--;edge[i]={u,v,w};e[u].push_back({v,w});e[v].push_back({u,w});} vector<i64> d1(n),d2(n);auto dijkstra=[&](int s){vector<i64> d(n,1e18);vector<int> st(n);d[s]=0;priority_queue<pair<i64,int>,vector<pair<i64,int>>,greater<pair<i64,int>>> pq;pq.push({0,s});while(!pq.empty()){auto [dis,u]=pq.top();pq.pop();if(st[u]) continue;st[u]=1;for(auto [v,w]:e[u]){if(d[v]>dis+w){d[v]=dis+w;pq.push({d[v],v});}}}return d;};d1=dijkstra(0);i64 dis=d1[n-1];d2=dijkstra(n-1);vector<int> ans(m);vector<array<int,3>> vec;vector<vector<array<int,2>>> e2(n);for(int i=0;i<m;i++){auto [u,v,w]=edge[i];if(d1[u]+d2[v]+w==dis||d1[v]+d2[u]+w==dis){e2[u].push_back({v,1});e2[v].push_back({u,1});vec.push_back({u,v,i});}}vector<int> dfn(n),low(n);int tot=0;map<pair<int,int>,int> mp;function<void(int,int)> tarjan=[&](int u,int fa){dfn[u]=low[u]=++tot;for (auto [v,w]:e2[u]){if(!dfn[v]){tarjan(v, u);low[u]=min(low[u],low[v]);if (low[v]>dfn[u])mp[{u,v}]=1,mp[{v,u}]=1;}else if(v!=fa){low[u]=min(low[u],dfn[v]);}}};for(int i=0;i<n;i++){if(!dfn[i]) tarjan(i,-1);}for(auto [u,v,id]:vec){if(mp[{u,v}]) ans[id]=1;}for(auto x:ans) cout<<(x?"Yes\n":"No\n");
}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int t=1;//cin>>t;while(t--){Showball();}return 0;
}
