形象理解这一场的 C
A.Seats \(\text{diff }20\)
对给定序列 \(S\) 找出 \(i\) 的个数,使得 \(S_{i}=0,S_{i+1}=1,S_{i+2}=0\)
#define int long long
string x;signed main(){int n;cin>>n;cin>>x;int ans=0;for(int i=0;i<=(int)x.length()-3;++i){if(x[i]=='#' and x[i+2]=='#' and x[i+1]=='.'){ans++;}}cout<<ans;
}
B.Traveling Takahashi Problem \(\text{diff }65\)
给定平面上 \(N\) 个点，求从原点出发按编号顺序走完 \(N\) 个点并走回原点的直线距离之和
#include<bits/stdc++.h>
using namespace std;
#define int long long
long double dist(int x1,int y1,int x2,int y2){return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int n;
int nx=0,ny=0;
long double ans=0;
signed main(){cin>>n;for(int i=1;i<=n;++i){int x,y;cin>>x>>y;ans+=dist(nx,ny,x,y);nx=x;ny=y;}ans+=dist(nx,ny,0,0);printf("%.20Lf",ans);
}
C.Spiral Rotation \(\text{diff }972\)
给定一个 \(N\times N\) 的 \(01\) 矩阵，\(N\) 为偶数，对每个 \(i\in[1,\frac{N}{2}]\) 执行如下操作
- 选择所有 \(i\le x,y\le N-i+1\)，将 \((y,N-x+1)\) 上的值替换为 \((x,y)\) 上的值
对于每一个 \(i\)，对所有 \((x,y)\) 的替换同时发生，也即在每一个 \(i\) 内不存在覆盖的情况
输出最终的矩阵\(N\le 10^3\)
通过手摸可以发现，对单独的一个 \(i\) 来说，相当于四个一组发生旋转
点击查看
但是这里有一个 \(i\in[1,\frac{N}{2}]\)，这其实相当于是分层的，先整体转，再转第二层和以内的，再转第三层和以内的，相当于第一层转一圈，第二层转两圈，以此类推
可以发现转四圈不会影响结果，因此第 \(k\) 层转 \(k\mod 4\) 圈就行了
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
char mp[3001][3001];
bool vis[3001][3001];
signed main(){cin>>n;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){cin>>mp[i][j];}}for(int k=1;k<=n/2;++k){for(int i=k;i<=n-k+1;++i){if(!vis[i][k]){if(k%4==1){int x1=i,y1=k;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}else if(k%4==2){int x1=i,y1=k;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}else if(k%4==3){int x1=i,y1=k;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}}}for(int j=k+1;j<=n-k;++j){if(!vis[k][j]){if(k%4==1){int x1=k,y1=j;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}else if(k%4==2){int x1=k,y1=j;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}else if(k%4==3){int x1=k,y1=j;int x2=y1,y2=n-x1+1;int x3=y2,y3=n-x2+1;int x4=y3,y4=n-x3+1;char tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;tmp=mp[x4][y4];mp[x4][y4]=mp[x3][y3];mp[x3][y3]=mp[x2][y2];mp[x2][y2]=mp[x1][y1];mp[x1][y1]=tmp;vis[x1][y1]=true;vis[x2][y2]=true;vis[x3][y3]=true;vis[x4][y4]=true;}}}}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){cout<<mp[i][j];}cout<<'\n';}
}
D.ABA \(\text{diff }658\)
给定一个字符串 \(S\)，求满足下列条件的 \((i,j,k)\) 对数
- \(i\lt j\lt k\)
- \(S_i,S_j,S_k\) 能构成回文
\(|S| \le 2\times 10^5\)
其实也就是找 \(S_i=S_k\) 的对数，然后中间填什么都行
注意到两个相等的数，如果位置分别为 \(i,j\)，那么它们中间夹着的任何一个数都能造成贡献，也即贡献为 \(j-i-1\)
如果枚举到一个数 \(S_i\) 时，有 \(k\) 个数（\(S_{j1},S_{j2}\cdots\)）与其相等，则对答案的贡献应该是 \((S_i-S_{j1}-1)+(S_i-S_{j2}-1)\cdots=k(S_i-1)-\sum S_{j}\)
因此维护前缀和即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
int possum[27];
int poscnt[27];
string x;
int ans=0;
signed main(){cin>>x;for(int i=0;i<=(int)x.length()-1;++i){ans+=max(0ll,(i-1)*poscnt[x[i]-'A']-possum[x[i]-'A']);poscnt[x[i]-'A']++;possum[x[i]-'A']+=i;}cout<<ans;
}
E.3 Team Division \(\text{diff }1424\)
有三支队伍和 \(N\) 个人，每支队伍初始有一定人数，每个人有权值 \(B_i\)，可以移动任意队伍中的人，问三支队伍的权值和相等所需的最小移动次数
\(N\le 100,\sum B_i\le 1500\)
首先注意到
- \(\sum B_i \not \equiv 0\pmod 3\) 无解
考虑换种思路做，清空所有队里的人，然后一个一个往里填，如果当前填的人本来就在这个队里，则对移动次数无贡献，否则有 \(1\) 的贡献
然后，注意到最终每个队的总和不超过 \(\frac{\sum B_i}{3}=500\)，因此设计 \(f_{i,j,k}\) 表示放到第 \(i\) 个人，第一队有 \(j\) 的权值和，第二队有 \(k\) 的权值和的最少交换次数（第三队可以用 \(\sum B_i-j-k\) 算出来）
直接枚举每个人填数即可
最后从 \(f_{n,\frac{\sum}{3},\frac{\sum}{3},\frac{\sum}{3}}\) 统计答案
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[101],b[101];
int f[101][501][501];
int sum[5];
int tot;
signed main(){cin>>n;for(int i=1;i<=n;++i){cin>>a[i]>>b[i];sum[a[i]]+=b[i];tot+=b[i];}if(tot%3!=0){cout<<-1;return 0;}memset(f,0x3f,sizeof f);f[0][0][0]=0;for(int i=1;i<=n;++i){for(int j=0;j<=tot/3;++j){for(int k=0;k<=tot/3;++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));if(tot-j-k>=b[i]) f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+(a[i]!=3));}}}if(f[n][tot/3][tot/3]>=0x3f3f3f3f3f3f3f3f){cout<<-1;return 0;}cout<<f[n][tot/3][tot/3]<<endl;
}
F.Road Blocked \(\text{diff }1546\)
无向图中实现如下操作
1 i删除第 \(i\) 条边2 x y查询 \(x,y\) 两点的最短路径长度\(N\le 300,Q\le 2\times 10^5\)
有删边，应该倒过来处理询问
然后考虑加边怎么处理变化
用 DP 的思路，加了边之后，只有经过这条边两个端点的路径才能有可能改变，因为 \(N\) 比较小，因此考虑将这条新加的边的两个端点当中转点，枚举所有点对的路径来更新
类似弗洛伊德（其实就是弗洛伊德）
#include<bits/stdc++.h>
using namespace std;
#define int long long
int f[301][301];
int n,m,q;
struct edge{int l,r,w;
}e[300*300+1];
struct opera{int op;int id;int x,y;
}op[200001];
bool vis[300*300+1];
vector<int>ans;
signed main(){ios::sync_with_stdio(false);cin>>n>>m>>q;for(int i=1;i<=m;++i){int x,y,z;cin>>x>>y>>z;e[i]={x,y,z};}for(int i=1;i<=q;++i){cin>>op[i].op;if(op[i].op==1){cin>>op[i].id;vis[op[i].id]=true;}else{cin>>op[i].x>>op[i].y;}}memset(f,0x3f,sizeof f);for(int i=1;i<=m;++i){if(!vis[i]){f[e[i].l][e[i].r]=min(f[e[i].l][e[i].r],e[i].w);f[e[i].r][e[i].l]=min(f[e[i].r][e[i].l],e[i].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]);}}}for(int t=q;t>=1;--t){if(op[t].op==1){f[e[op[t].id].l][e[op[t].id].r]=min(f[e[op[t].id].l][e[op[t].id].r],e[op[t].id].w);f[e[op[t].id].r][e[op[t].id].l]=min(f[e[op[t].id].r][e[op[t].id].l],e[op[t].id].w);// cout<<"add "<<e[op[t].id].l<<" "<<e[op[t].id].r<<endl;for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){f[i][j]=min(f[i][j],f[i][e[op[t].id].l]+f[e[op[t].id].l][j]);}}for(int i=1;i<=n;++i){for(int j=1;j<=n;++j){f[i][j]=min(f[i][j],f[i][e[op[t].id].r]+f[e[op[t].id].r][j]);}}}if(op[t].op==2){if(f[op[t].x][op[t].y]>=0x3f3f3f3f3f3f3f3f){ans.push_back(-1);}else ans.push_back(f[op[t].x][op[t].y]);}}std::reverse(ans.begin(),ans.end());for(int i:ans){cout<<i<<"\n";}
}
G.Road Blocked 2 \(\text{diff }2014\)
对给定无向图判断：
- 对所有 \(i\in[1,m]\)，如果将第 \(i\) 条边删去，\(1\) 至 \(N\) 的最短路径是否发生变化
\(N,M\le 2\times 10^5\)
看的第二篇题解
判断这个其实就是判断一条边是不是会被所有 \(1\) 到 \(N\) 的最短路经过
我们可以根据 \(dis\) 判一下边 \((x,y)\) 是否在最短路上：
\[dis_{1,x}+w_{x,y}+dis_{y,N}=dis_{1,N}
\]
或者反着来也行，但是这样我们就能判断其是否在最短路上
然后我们需要判断一条边是否为所有最短路的必经边，判断一条边被几条最短路径经过是不容易的，但是判断 \(1\) 到一个节点有几条最短路径是容易的
因此我们可以这样判断：
- 如果 \(1\) 到 \(x\) 有 \(c_x\) 条最短路径，到 \(N\) 有 \(c_N\) 条最短路径，\(N\) 到 \(y\) 有 \(c_y\) 条最短路径，则如果 \(c_x\times c_y=c_N\)，那么就说明边 \((x,y)\) 是最短路必经边
这么做有一个好处就是分别拿 \(1,N\) 跑两边最短路就能统计答案
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int p=1e9+7;
struct __edge{int to,w;
};
vector<__edge>e[200001];
struct ___edge{int from,to,w;
};
___edge edge[200001];
int dis[2][200001];
bool vis[2][200001];
int cnt[2][200001];
struct node{int id,dis;bool operator <(const node &A)const{return dis>A.dis;}
};
priority_queue<node>q;
void dij(int s,int id){memset(dis[id],0x3f,sizeof dis[id]);memset(vis[id],0,sizeof vis[id]);memset(cnt[id],0,sizeof cnt[id]);dis[id][s]=0;cnt[id][s]=1;q.push({s,dis[id][s]});while(!q.empty()){node u=q.top();q.pop();if(dis[id][u.id]<u.dis) continue;if(vis[id][u.id]) continue;vis[id][u.id]=true;for(__edge i:e[u.id]){if(dis[id][i.to]>dis[id][u.id]+i.w){dis[id][i.to]=dis[id][u.id]+i.w;q.push({i.to,dis[id][i.to]});cnt[id][i.to]=cnt[id][u.id];}else if(dis[id][i.to]==dis[id][u.id]+i.w){cnt[id][i.to]=(cnt[id][i.to]+cnt[id][u.id])%p;}}}
}
signed main(){cin>>n>>m;for (int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});e[v].push_back({u,w});edge[i]={u,v,w};}dij(1,0);dij(n,1);for(int i=1;i<=m;++i){int u=edge[i].from,v=edge[i].to,w=edge[i].w;if((dis[0][u]+w+dis[1][v]==dis[0][n] and cnt[0][u]*cnt[1][v]%p==cnt[0][n])or (dis[0][v]+w+dis[1][u]==dis[0][n] and cnt[0][v]*cnt[1][u]%p==cnt[0][n])){cout<<"Yes\n";}else{cout<<"No\n";}}
}林妹妹，赢！
哥们图床现在比较富有
