【杂题】AT

401rk8 · 2021-12-17 08:00:50 · 个人记录

显然若 |x|+|y| 奇偶性不同则无解。

这种问题的常见套路是二进制分解（m\approx\log(|x|+|y|) 也提示这一点），如果不要求每个步长都走可以简单构造，然后从小到大考虑没有选的步长 2^i，把 2^{i-1} 反向，2^i 向原 2^{i-1} 方向走即可。

实现上因为一定有解，那么从大到小枚举步长，选择离终点近的方向走即可

以重心（D_i 最小的结点）为根时任一子树大小 \le\frac{n}{2}，由 D_{u}=D_{fa}+n-2siz[u] 得 D_{u}\ge D_{fa}，则 D_i 最大的结点为叶子，且通过该式能反推出父亲的 D，那么把该点挂在父亲下面并删除即可，可以使用 set 实现

注意上述过程只保证了父子的 D,siz 关系合法，但如果对 D 集体加一个值并不影响合法性，因此需要建出树后判断任意结点的 D 是否正确

还是不够敏感

选 i 就必须选 i 的倍数，显然是闭合子图。通过所有和 - 被打碎的和可以转化为最小权闭合子图

每次操作影响的边数是 O(n) 级别的，考虑转化一下：记 b_i 为点 i 周围一圈边的权值异或，这样每次操作转化为任选两个点使其异或上一个值

对于权值相同的点显然两两配对消掉，然后最多剩下 16 个互不相同的值，状压 DP 即可

根据冒泡排序，每种颜色内部的交换次数为逆序对数，接下来只需考虑颜色间的

最终状态两种颜色都递增，考虑从前往后放球，设 f[i,j] 为放了 i 个白球，j 个黑球的最小值，以第 i+j 个放白球为例，需要与前面比 j 大的黑球交换，即

f[i,j]=f[i-1,j]+\sum_{k=1}^{pos_{w}[j]}[col_{k}=b][a_{k}>j]

前缀和优化即可做到 O(n^{2})

半年前 hkh 讲的题，现在才看懂题解。。。

启示我们对于联通性相关问题，一个连通块中的点是等价的，以及注意观察性质来减少边数

一个套路是把黑色的叶子删掉，之后必须遍历每个叶子，即整棵树

手模样例/想象一下，发现路径大概是回路删掉一条链

先考虑回路，每条边要走两次，那么每个点颜色被改变次数即为度数，遍历结束后的白色点（称为标记点）需要在走到它时手动改变一次

然后考虑删掉一条链，讨论一下：

那么将标记点的点权记为 2 求直径即可

细节：对于从 u 到 v 的路径，u 其实不受影响，不能算在直径中。不过树上点权都非负，因此可以将直径的端点延长到叶子，而叶子的点权一定为 0，将叶子当成 u 即可

首先有一个性质：a\oplus b\le a+b，因此只要 v\le N 即可，考虑按位 DP v

对于当前 DP 出的 v，在其对应 a,b 的后面分别添加一个二进制位可以转移到的 v' 为：

实现上采用记搜逆推即可

显然每层独立，可以分开 DP

枚举每层深度，设 f[u] 为点 u 有一个石子的概率（之所以设为概率是因为最后乘 2^{n+1} 即可，而方案数需要在 DP 过程中乘，比较麻烦），则有 f[u]=\sum_{v\in son(u)}f[v]\prod_{w\in son(u),w\ne v}(1-f[w])

最后的问题是如果每层 DP 一次是 O(n^{2}) 的，可以使用长剖或虚树优化