A - Strong Word
直接判。
#include<bits/stdc++.h>
using namespace std;
string s;
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>s;if(s[0]==s[s.size()-1]) cout<<"Yes";else cout<<"No";return 0;
}
B - Center Alignment
直接模拟。
#include<bits/stdc++.h>
using namespace std;
int n,l;
string s[110];
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>s[i];int t=s[i].size();l=max(l,t);}for(int i=1;i<=n;i++){int t=s[i].size();for(int j=1;j<=(l-t)/2;j++) cout<<'.';cout<<s[i];for(int j=1;j<=(l-t)/2;j++) cout<<'.';cout<<'\n';}return 0;
}
C - Sugoroku Destination
对每个格子建有向图。该格连向该格的数字。
题目中给出 \(i\le A_i \le N\)，也就是说除自环外没有环。
那么只需要对整张图跑一遍 DFS，看每个点最终会停在哪个点即可。
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n;
int a[N];
int h[N],tot;
int p[N];
bool vis[N];
struct Node{int to,nxt;
}e[N];
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
int dfs(int u){vis[u]=1;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==u) p[u]=u;else p[u]=dfs(v);}return p[u];
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++){cin>>a[i];Add(i,a[i]);}for(int i=1;i<=n;i++){if(!vis[i]) dfs(i);}for(int i=1;i<=n;i++) cout<<p[i]<<' ';return 0;
}
D - Reconstruct Chocolate
重要条件：每次掰巧克力都是沿着矩形边界掰的。也就是说对于每个子矩形总有一块顶天立地的（独占整个矩形的长或宽）。
那么我们按照这个思路模拟，每次找一个长等于 \(H\) 或宽等于 \(W\) 的巧克力，拼到剩余部分的右下角。然后给 \(H,W\) 减掉这一块，直到其中一个减到 \(0\)。
由于每次枚举所有巧克力会超时，所以我们分别按照长宽从大到小排序，遇到选过的就跳过。每次选第一个比较即可。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int H,W,n;
int ansx[N],ansy[N];
bool vis[N];
struct Node{int h,w,p;
}c1[N],c2[N];
bool cmp1(Node x,Node y){return x.h>y.h;
}
bool cmp2(Node x,Node y){return x.w>y.w;
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>H>>W>>n;for(int i=1;i<=n;i++){cin>>c1[i].h>>c1[i].w;c1[i].p=i;c2[i]=c1[i];}sort(c1+1,c1+1+n,cmp1);sort(c2+1,c2+1+n,cmp2);int i,j;i=j=1;while(H&&W){while(vis[c1[i].p]) i++;while(vis[c2[j].p]) j++;if(c1[i].h==H){vis[c1[i].p]=1;ansx[c1[i].p]=H-c1[i].h+1,ansy[c1[i].p]=W-c1[i].w+1;W-=c1[i].w;}else if(c2[j].w==W){vis[c2[j].p]=1;ansx[c2[j].p]=H-c2[j].h+1,ansy[c2[j].p]=W-c2[j].w+1;H-=c2[j].h;}}for(int i=1;i<=n;i++) cout<<ansx[i]<<' '<<ansy[i]<<'\n';return 0;
}
F - Exactly K Steps 2
原题 Luogu P2886 [USACO07NOV] Cow Relays G。
对于邻结矩阵 \(C\) 跑 \(K\) 次的 Floyd 快速幂，最后输出所有 \(C_{i,i}\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=110;
const int INF=1e18;
int n,s,t,k;
int g[N][N];
struct Matrix{int mx[110][110];
}a,b,c;
Matrix operator *(const Matrix &a,const Matrix &b){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) c.mx[i][j]=INF;}for(int d=1;d<=n;d++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){c.mx[i][j]=min(c.mx[i][j],a.mx[i][d]+b.mx[d][j]);}}}return c;
}
void fstpow(){int q=k-1;b=a;while(q){if(q&1) b=b*a;a=a*a;q>>=1;}
}
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++) cin>>a.mx[i][j];}fstpow();for(int i=1;i<=n;i++) cout<<b.mx[i][i]<<'\n';return 0;
}