AK 了。赶时间写得比较匆促，不搞题意翻译了。
A
开个数组记录每个小写字母是否出现，然后找到一个没出现的，输出。时间复杂度 O(\vert S\vert)。
代码
int main(){
scanf("%s",s + 1);
for(int i = 1;i <= strlen(s + 1);i ++) e[s[i]] = true;
for(int i = 'a';i <= 'z';i ++){
if(!e[i]){
printf("%c",i);
return 0;
}
}
return 0;
}
B
模拟旋转，四个方向都考虑一遍。时间复杂度 O(N^2)。
代码
int main(){
read(n);
for(int i = 1;i <= n;i ++) scanf("%s",s[i] + 1);
for(int i = 1;i <= n;i ++) scanf("%s",t[i] + 1);
for(int i = 0;i < 4;i ++){
cnt = 0;
for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) if(s[i][j] != t[i][j]) cnt ++;
ans = min(ans,cnt + i);
for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) tmp[j][n - i + 1] = s[i][j];
for(int i = 1;i <= n;i ++) for(int j = 1;j <= n;j ++) s[i][j] = tmp[i][j];
}
printf("%d",ans);
return 0;
}
C
一个简单无向图是环，当且仅当图连通，且所有点度数为 2。直接检验，时间复杂度 O(N\alpha (N))。
代码
int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
int main(){
read(n),read(m);
for(int i = 1;i <= n;i ++) f[i] = i;
if(n != m) fal = true;
for(int i = 1;i <= m;i ++){
read(u),read(v);
d[u] ++,d[v] ++,f[find(u)] = find(v);
}
for(int i = 1;i <= n;i ++) if(d[i] != 2) fal = true;
for(int i = 2;i <= n;i ++) if(find(1) != find(i)) fal = true;
if(fal) printf("No");
else printf("Yes");
return 0;
}
D
因为每种动物需要看两次，所以一个动物园至多去两遍。搜索每个动物园去多少遍（ 0 或 1 或 2 ），暴力检验是否每种动物都看了两遍及以上。时间复杂度 O(NM\times 3^N)。
代码
void sch(int w){
if(w > n){
for(int i = 1;i <= m;i ++) cnt[i] = 0;
for(int i = 1;i <= n;i ++) for(auto j : anm[i]) cnt[j] += vst[i];
for(int i = 1;i <= m;i ++) if(cnt[i] < 2) return;
ans = min(ans,now);
return;
}
vst[w] = 0,sch(w + 1);
now += c[w],vst[w] = 1,sch(w + 1);
now += c[w],vst[w] = 2,sch(w + 1);
now -= 2 * c[w];
}
int main(){
read(n),read(m);
for(int i = 1;i <= n;i ++) read(c[i]);
for(int i = 1;i <= m;i ++){
read(k[i]);
for(int j = 1;j <= k[i];j ++) read(a[i][j]),anm[a[i][j]].push_back(i);
}
sch(1);
printf("%lld",ans);
return 0;
}
E
考虑构成一个图，所有 A_i=1 的点连一条路径到 0，要路径并长度最短。
是有向无环图，从前往后每个 A_i=1 的点考虑走最短的路到一个已经连到 0 的点即可。时间复杂度 O(N^2)。
代码
int main(){
read(n),memset(d,0x3f,sizeof(d)),d[0] = 0;
for(int i = 1;i < n;i ++) read(c[i]);
for(int i = 1;i < n;i ++) read(a[i]);
for(int i = 1;i < n;i ++){
for(int j = i - c[i];j < i;j ++) d[i] = min(d[i],d[j] + 1);
if(a[i]) ans += d[i],d[i] = 0;
}
printf("%d",ans);
return 0;
}
F
看到这种期望就想 DP。考虑 f_{i,j} 表示还剩 i 轮，已经按了 j 次正确按钮，后续使用最佳决策的获胜几率。这个“最佳决策”由于所有按钮是随机的，按 M 次我们就钦定是按最左边的 M 个，并且这几个按钮按的次数单调不减。有多少种可能的方案呢？跑一下发现和为 30 的不减正整数序列有 5604 个。
搜索枚举所有方案，取最大的期望转移即可。
时间复杂度 O(TKp(M))，p(M) 表示所有长度为 M 的不减正整数数列长度之和。
代码
void sch(int rst){
if(cnt > n) return;
if(!rst){
now = 0;
for(int i = 1;i <= cnt;i ++) now += (long double)1.0 * f[rnd - 1][hm + a[i]] / n;
now += (long double)1.0 * (n - cnt) * f[rnd - 1][hm] / n,mx = max(mx,now);
return;
}
a[++ cnt] = rst,sch(0),cnt --;
for(int i = a[cnt];i <= min(rst / 2,k);i ++) a[++ cnt] = i,sch(rst - i),cnt --;
}
int main(){
read(n),read(t),read(m),read(k),a[0] = 1;
for(int i = 0;i <= t;i ++) for(int j = k;j <= 80;j ++) f[i][j] = 1;
for(int i = 1;i <= t;i ++){
rnd = i;
for(int j = 0;j < k;j ++) hm = j,mx = cnt = 0,sch(m),f[i][j] = mx;
}
printf("%.20LF",f[t][0]);
return 0;
}
G
差分约束。令 S 表示 A 的前缀和，因为是正整数数列，所以有
- \forall i\in [1,n],S_i-S_{i-1}\ge 1
根据约束 (L,R,X)，有
-S_R-S_{L-1}=X
即
- S_{R}-S_{L-1}\ge X,S_{R}-S_{L-1}\le X
转换成差分约束条件，跑 SPFA。时间复杂度 O(N(N+M))。
代码
void spfa(){
memset(ist,0,sizeof(ist)),memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt));
while(q.size()) q.pop();
q.push(n + 1),dis[n + 1] = 0,ist[n + 1] = true;
while(q.size()){
ist[u = q.front()] = false;
q.pop();
for(auto i : e[u]){
v = i.first,w = i.second;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
if(!ist[v]){
ist[v] = true,q.push(v);
if(++ cnt[v] == n + 2){fal = true;return;}
}
}
}
}
return;
}
int main(){
read(n),read(m);
for(int i = 1;i <= m;i ++){
read(x[i].l),read(x[i].r),read(x[i].s);
e[x[i].l - 1].push_back({x[i].r,x[i].s});
e[x[i].r].push_back({x[i].l - 1,-x[i].s});
}
for(int i = 0;i < n;i ++) e[i + 1].push_back({i,-1});
for(int i = 0;i <= n;i ++) e[n + 1].push_back({i,0});
spfa();
printf("%lld",fal ? -1ll : dis[n] - dis[0]);
return 0;
}