2023.7.10 杭州集训Day1 考试记录

2023暑杭州集训

SDOI2011套题

result

Process

各种原因，考试时间 3.5h -> 2.5h，无所谓，少罚会坐（

开题：

A 博弈论，大概率不会，但可做
B 树上问题，感觉很好做
C 数据范围很小，奇奇怪怪的题，感觉很不可做（

想约 10min $A$，只会 $30$，扔了

开 $B$，很快发现二分后是个我很熟悉的DP，稍微编一编细节，直接开冲。

开考约 $50$min，$B$ 切了，重新想 $A$

想了不知道多久，中间还看错了几遍题，还是不会，听到别人说有个啥结论，笑死根本不会博弈，写完 $30pts$ 直接扔

想 $C$，冲部分分，没冲出来，下班（

A. 黑白棋

题面

Solution

我们发现，如果相邻的黑白棋子两两撞在一起，那么此时为必输态。

并且显然所有必输态都可走到这个状态，则我们发现，胜负只与相邻的黑白棋之间的间隙有关，每次操作就是在减少间距。

题目可转化为一个 $NimK$ 游戏，将相邻的黑白棋看成一堆石子，石子数为其间距，每次可选 $1$ 至 $d$ 堆石子拿走任意多的石子，不能操作者负。

$NimK$ 游戏的结论：将所有石子转为二进制，将其每位二进制位求和，若存在某位的和 $Sum_i$ 模 $(d + 1)$ 不为 $0$，则必胜。

这让没看过的人怎么猜（，不会博弈论。

博弈部分解决，剩下数数部分。

显然必败态比较好求（每一位均为 $(d+1)$ 倍数），直接做数位DP，设 $f(i, j)$ 为已填完 $i$ 位，用了 $j$ 个石子。

枚举当前位填了 $x \times (d + 1)$ 个 $1$，则带来的贡献为 $\dbinom{\frac{k}{2}}{x \times (d + 1)}$

最后每个 $f(j)$ 贡献到答案里都要乘一个构造石子堆的组合 $\dbinom{n - j - \frac{k}{2}}{\frac{k}{2}}$

Summary

数数部分比较简单，发现自己根本不会博弈论！！！

B. 消防

Solution

好像做法跟大家不太一样。

先记没想到的直径做法。

可以发现枢纽一定在直径上, 那么在直径上枚举起点，找最远的点做终点即可。

不会直径！！！

但有个不需要观察性质的 navie 做法，我们考虑二分答案，那么问题转变为已知其他点到枢纽的最大值 $d$，要求最小的枢纽长度 $x$ check 其是否小于 $s$

那么是个十分典的树形DP。

考虑 $f[i][0/1]$ 表示 以 $i$ 为根的子树，$0$ 表示 $i$ 为枢纽的中转点（即枢纽完全在子树内）， $1$ 表示 $i$ 为枢纽的当前端点（即枢纽可往上延伸）。

我们预处理 $Dis(i)$ 表示子树内的点到 $i$ 的最远距离，$Up(i)$ 表示子树 $i$ 之外的点到 $i$ 的最远距离。

配合转移即可，比较容易，不赘述。

Summary

是不是点到路径的最长距离，或树上的最长距离，基本可以考虑直径，虽然结论可能抽象。

C 火星移民

插头DP，不会，咕（（（