第五场太抽象了，失去补题欲望
6
A Cake (A)
首先假设字符串已经确定，对Oscar而言，由于一份蛋糕可以为空，在两人都尽可能取最大值的情况下，相当于忽略所有空的部分、只根据字符串的某个前缀 \(s'\) 划分蛋糕，按照字符串中0占比最大的前缀平均划分一定是最优的。回到游戏第一步，已知Oscar的目标，Grammy移动时应当让最优 \(s'\) 中0占比尽可能小，而Oscar应使之尽可能大，可用类似树上dp的思路求解。
学习了xht赛时的dfs函数，比我那坨代码好多了······
double dfs(int f, int i, int it, int cnt1, int cnt2, double mx) {
if(v[i].size() == 1 && v[i][0].t == f) return mx;
double ans = it;
for(int j = 0; j < v[i].size(); j++) {
int t = v[i][j].t, k = v[i][j].k;
if(t == f) continue;
int x1 = cnt1 + (1 ^ k), x2 = cnt2 + 1;
if(it) {
ans = min(ans, dfs(i, t, it ^ 1, x1, x2, max(mx, x1 * 1.0 / x2)));
} else {
ans = max(ans, dfs(i, t, it ^ 1, x1, x2, max(mx, x1 * 1.0 / x2)));
}
}
return max(ans, mx);
}
B.Cake 2 (B)
找规律题，似乎xcpc的签到偏爱找规律（）画图观察每块蛋糕的分布位置可得，\(k \leq n/2\) 时，\(ans=n*k+1\)，其中特判 \(k*2=n\) 时 \(ans=n\)；\(k > n / 2\) 时同理考虑 \(n-k\) 即可。
D.Puzzle: Wagiri (D)
(说起来Wagiri是什么意思呢，好奇)
由无向边的环结构想到边双连通分量，被保留的轮边必须位于某个分量内部；再用类似缩点的思想，将每个边双连通分量当作一个点考虑，被保留的切边恰好将所有点连成一棵树。先对所有轮边计算边双连通分量、再对所有切边计算生成树，最后并查集检验连通性即可。注意边双的代码比缩点多一个对边的特判。
核心代码如下，将不合法边的类型记作-1，便于输出：
for(int i = 1; i <= n; i++) {
if(!dfn[i]) tarjan(i, 0);
}
for(int i = 1; i <= n; i++) {
if(r[col[i]]) f[find(i)] = find(r[col[i]]);
else r[col[i]] = i;
}
int cntm = 0;
for(int i = 1; i <= m; i++) {
int x = e[i].f, y = e[i].t;
if(e[i].id) {
if(find(x) != find(y)) {
f[find(x)] = find(y);
cntm++;
} else {
e[i].id = -1;
}
} else {
if(col[x] != col[y]) {
e[i].id = -1;
} else cntm++;
}
}
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(f[i] == i) cnt++;
}
if(cnt > 1) {
printf("NO");
return 0;
}
printf("YES\n");
printf("%d\n", cntm);
for(int i = 1; i <= m; i++) {
if(e[i].id >= 0) {
printf("%d %d\n", e[i].f, e[i].t);
}
}