2024/07/08(#56)：请保佑我能直面镜中诞生的扭曲

拯救我自己。

110 PA2024 Żarówki

对每一个连通块分别考虑。

考虑将连通块内的情况。考虑一个连通块内的边充分多的情况下会发生什么？观察不难发现其答案为 $2^{n-1}$，而且不能再多了。

什么时候答案能够是这个？发现只要这个连通块不是一个二分图就可以了。

题解解释原因是这样的：奇环上的边可以任意吞掉两个棋子，或是任意产生两个棋子，所以只要棋子个数的个数是的奇偶性相同的状态都是可达的。

于是只要考虑二分图怎么做。答案是一个组合数，将颜色本身异或上是否是右部点，统计 $1$ 的个数。接下来我们的操作就是同时翻转两个点，仅当它们不同，相当于异或出来为 $1$ 的点上有个棋子，你可以将它移动到没有棋子的点上。

111 AGC004F Namori

怎么计数呢？对于树染成二分图后就是黑白点计算权值，对子树内的权值和考虑即可。不难发现这样很容易贪心。

对于奇环基环树，只要有偶数个点就可以随便跑了。对于答案，发现其并不能将本来有解的东西的答案变小，只能将本来无解的变成有解。因此先操作这条边 $\frac sum 2$ 次即可。

偶环奇环树，相当于有一条边是没有用的。把环拉出来，分成两半重新定义权值，发现其是找一个 $x$，使得环上的 $x+\sum |a_i-x|$ 最大（并不准确，一部分是加一部分是减，讨论一下，预先操作 $x$ 次），排序即可。

112 CF1083F The Fair Nut and Amusing Xor

直接差分掉，那么可以 $O(n)$ 贪心解决。

对于每一个 $\mod k$ 不同的位置分别考虑，然后问题转化为区间异或，区间查询不为 $0$ 的个数，直接做即可。

113 CF718E Matvey’s Birthday

考虑一个点是怎么走到另一个点的，要么是 $|i-j|$ 的贡献直接走，要么定义 $f_{i,c}$ 代表 $i$ 走到一个区域为 $c$ 的点的最小代价（可以直接使用 01 BFS 进行预处理），答案是 $f_{i,c}+f_{j,c}+1$。由于答案不会超过 $2k$，因此前者不难再最后取 $\min$ 处理，我们只需要计算出答案为 $i$ 的点对个数 $ans_i$。很难不考虑对从区域 $i$ 走到区域 $j$ 的贡献进行统计。这里只考虑 $i<j$，$i=j$ 的贡献就是 $1$。

令 $g_{i,j}=\min\{f_{x,j}\}$，那么区域 $i$ 走到区域 $j$ 的贡献一定是 $[\min_{c}\{g_{i,c}+g_{j,c}\}+1,\min_{c}\{g_{i,c}+g_{j,c}\}+3]$，只需要考虑何时能够取到最值。预处理出 $cnt_{i,s}$ 表示 $i$ 区域走到 $s$ 内的区域是最小的点的点的个数（严格是 $s$）以及其前缀和，随便容斥。

于是最终做到了 $O(nk+k^22^k)$。

114 NOI2022 移除石子

首先需要会判定是否合法。我们发现直接将恰好改为至多基本上不会错，因为可以将多的扔到一个位置然后用 $1$ 操作处理。事实发现也只需要特判很少的情况。

设 $f_{i,j,k}$ 代表考虑前 $i$ 个石子，统计第 $i$ 个位置出发和结束的 $2$ 操作，第 $i$ 个位置至少被 $j$ 个连续消除覆盖，第 $i+1$ 个位置至少被 $k$ 个覆盖的时候，至少需要添加多少个石子。

由于至少 $2$ 枚石子的时候就可以使用操作 $1$，因此猜测 $j,k\le 2$，事实也确实如此。

写一下需要特判的情况，$k=1$ 时会在全零和 ${1,1,1}$ 矛盾，$k>1$ 都可以通过移除至多一个二操作，然后剩下的用一操作消除的方式解决。

然后把 $f$ 的自动机建立出来，发现 $a_i\ge 8$ 的时候本质相同，直接转移即可。

115 IOI2019 矩形区域

预处理一行的连续段，然后枚举左右边界直接扫即可。