做题笔记 2023.10
CF838C Future Failure
这个游戏性质非常好，因为两个操作其实是独立的，无论进行哪种操作都不会使游戏局面发生太大的变动。
首先若初始状态字母排列方案数为偶数则先手必胜，原因很简单，如果能够转移到必败态就直接转移，否则我们可以强迫后手转移到必胜态。
接下来我们考虑字母排列数为奇数的情况，此时重排操作没有意义，我们一定会删除一个字母。如果删除之后排列方案数为偶数一定就寄了，所以我们希望操作完后排列方案数依旧为奇数。设每个字母的出现次数为 $a_i$，根据 lucas 定理我们有一个经典结论，排列方案数
$$
\binom{n}{a_1 \ a_2\ \dots\ a_k} \bmod 2 = 1
$$
当且仅当二进制下 $a_1,a_2,\dots,a_k$ 是 $n$ 的一个划分。那么，只要找到 $\mathrm{lowbit}(n)$ 所在的 $a_i$ 并对其 $-1$ 就可以保证得到的新串排列方案数依旧为奇数。不难发现双方都会按照这个策略进行操作，每回合 $n\gets n-1$，所以若 $n$ 为奇数则先手必胜。
综合上面两种情况我们可以得到：先手必胜当且仅当字母排列方案数为偶数或 $n$ 为奇数。
统计方案数的时候先将上面的条件取反，然后运用上面的结论做快速幂+子集卷积即可。有一些实现细节。
LG7516 [省选联考 2021 A/B 卷] 图函数
我们考虑将原题目定义的贡献重新拆分进行计算。
容易发现，根据题目的定义，在原图中处在不同强连通分量内的点之间绝对不可能产生任何贡献，于是我们只在一个强连通分量内进行讨论。
我们考虑 $u$ 能对哪些 $f(v,G_i)$ 作贡献。如果我们此时考虑到了点 $u$，则所有 $w<u$ 都已经被考虑过了，不难发现，在此时的图中，$w$ 要么已经被删除，要么和 $u$ 不在同一个强连通分量内，后者实际上和 $w$ 已被删除等价。于是我们得到，$u$ 能对 $f(v,G_i)$ 作贡献当且仅当 $<u$ 的点全部删除后，$u,v$ 仍然强连通。
接下来我们考虑哪些图 $G_i$ 能满足这一条件。$u,v$ 强连通等价于存在两条路径 $u\rightsquigarrow v$ 和 $v\rightsquigarrow u$，而 $u,v$ 在 $G_i$ 中连通则等价于存在两条路径 $u\rightsquigarrow v$ 和 $v\rightsquigarrow u$ 且路径上编号最小的边 $> i$。
至此，我们要做的实际上是，从大到小向图中加点，同时维护两点间路径上编号最小的边的编号最大值。这和 Floyd 的过程很相似，那么直接用 Floyd 做就可以了，复杂度 $O(n^3)$。该做法卡常，朴素实现与暴力同分，不过将 std::max 和 std::min 改成三目在此处对速度提升极为明显。
另一种思路是，考虑 $\max$ 的最优性，我们可以从大到小向图中加边，然后维护两点何时被连通。注意本题中还有只能经过编号大于自己的点这一限制。我们可以对每个 $u$ 分别处理，动态加边，维护 $u$ 能否到达 $v$，以及 $v$ 是否能到达 $u$，后者可以被转化为 $u$ 在反图上能否到达 $v$。具体来说，加入一条边 $s\to t$ 时，如果 $t$ 可达，则该边可以被忽略；如果 $s$ 可达，则从 $t$ 开始做 bfs；否则，将边加入邻接表中，这条边会在以后的 bfs 中被使用。每个点至多只会在 bfs 中经过一次，枚举边的总复杂度为 $O(m)$，共会进行 $n$ 次处理，故总复杂度为 $O(nm)$。
这种做法可以进一步优化，事实上 bfs 中我们做了大量无用枚举，所有已经到达过的点都可以在枚举边时跳过。可以使用 bitset 维护未到达过的点以及邻接矩阵，将枚举边改为求邻接矩阵和未到达过的点的交，遍历用 _Find_first() 和 _Find_next() 实现。总复杂度为 $O(n^3/w)$。这种做法适用于很多稠密图的遍历。（ARC092F）
Why not dfs：$O(nm)$ 的做法用 dfs 应该也可以，但是 bitset 做法中，如果使用 dfs，实际上遍历一个点的出边时未到达过的点的集合是在动态变化的，那样也就失去了求交的意义。
LG7515 [省选联考 2021 A 卷] 矩阵游戏
难点在于如何满足 $0\le a_{i,j}\le 10^6$ 的限制。
不难发现如果确定了第一行第一列，整个矩阵都可以被确定。考虑设出 $a_{1,k}$ 和 $a_{k,1}$，则 $a_{i,j}$ 只与 $a_{1,1},a_{i,1},a_{1,j}$ 三个变量有关，可以通过换元变化为两个变量，然后跑差分约束即可。
一种更加直观的方法是，考虑先忽略值域限制构造任意可行矩阵，然后在这个可行矩阵上进行调整，每次对一行进行 $+r,-r,+r,\dots$ 或对一列进行 $+c,-c,+c,\dots$ 的修改。容易通过构造证明，这样能够到达任意一种可行矩阵的状态。那么我们设出对第 $i$ 行的操作值 $r_i$ 以及对第 $j$ 列的操作值 $c_j$，并对偶数行与奇数列的操作值取相反数，对每个元素的操作值都可以表示为 $(-1)^{i+j}(r_i-c_j)$。跑差分约束即可。
复杂度 $O(n^3)$，带一个相当大的常数。鉴于图的结构特殊，跑 spfa 效果比较好。
CF842E Nikita and game
如果随便画出一棵树所有直径的形态，我们会发现所有直径一定会共用中点或中间的边，大多数时候直径会分成两个部分，每一部分产生若干分支，对应若干可行的直径端点，从两个部分分别任取端点都能组成一条直径。
这启发我们用两个 std::vector 分别维护这两个部分的直径端点，每次新增点时：
- Case 1. 若接在某个直径端点上，则直径长度增加，所在部分的直径端点全部失效，替换为这个新增的点；
- Case 2. 若不接在直径端点上，分别从两个部分任选端点计算距离，检查这个点能否成为直径端点，如果能的话应该被分在哪个部分。
这样有一个问题，直径长度为奇数时，直径中点可能能将所有直径分成三个及以上的部分，直接维护极其复杂。
一个好的方法是，仍然将直径端点划分到两个集合，每次发生 Case 1 时检查当前集合的点能否加入另一集合。
这种做法正确性显然，但时间复杂度并不明晰。
我们将两个集合称为「左集合」和「右集合」。上面所说的「部分」，明确的定义是在所有直径端点构成的虚树上，直径中点的一棵子树，接下来我们为了方便称这个结构为「块」。显然，在块中的某个直径端点下接一个新点会导致这个块变成一条链，其余的端点都会被删去。
我们要求，右集合中有且仅有一个块，而左集合中可以有多个块。在代码实现时，只要每次新增点时都优先加入左集合即可。如果真的任意在左右集合中加点，复杂度会退化（link）。
这样，如果在左集合中加点，该点所在的块变为一条链，其余左集合中的块被删去或加入右集合，并且，由于直径中点的移动，所有块加入右集合后会合并为一个块。如果在右集合中加点，右集合直接变为一条链，不会发生直径端点在集合间的转移。
这样，每个直径端点至多只会被转移一次，总复杂度视求 lca、算距离的方式不同为 $O(m)$ 或 $O(m\log m)$。
ARC150D Removing Gacha
根据期望的线性性，考虑每个点期望会被选中多少次，答案直接加和即可。
对于某个点 $u$，我们考虑其到根的路径，根据题意，从根到 $u$ 最长的被染黑的前缀是不能被选取的，但是，由于我们只关心 $u$ 被选取的次数，认为该前缀上的点可选并不会影响结果。
问题转化为在 $k$ 个点中，初始全白，每次等概率随机一个染黑，直到全黑为止，求第 $k$ 个点期望被进行了多少次染色。显然每个点被染色的期望次数都相等，我们考虑这个随机过程期望多久能结束。这是经典问题，答案为 $\sum_{i=1}^k k/i$，于是第 $k$ 个点期望会被染色 $\sum_{i=1}^k 1/i$ 次。
然后就做完了。
Insights. 在概率问题中，我们不希望概率在随机过程中发生复杂的变化，如果题目设计了一个复杂的背景，可以试着寻找性质优美的子结构，通常会运用期望的线性性，只关注某个元素或某两个元素间的关系，使得题目设定的复杂的操作或限制对该子结构不产生影响。
CF1854C Expected Destruction
上一题让我想到了这个题。
题目给的这个结构也十分复杂，由于选中每个元素的概率在不断变化，直接做显然是困难的。
两个元素相遇就会合并，如果没有这个限制，期望时间就是 $\sum m + 1 - S_i$。
这里我们考虑在相邻两个元素间运用期望的线性性，两个元素在 $x$ 处相遇，则期望时间会减少 $m + 1 - x$。于是我们对每相邻两个元素考虑期望的相遇位置即可。在考虑相邻两个元素时，我们不考虑与其他元素的合并问题，因为这并不会影响我们正在考虑的子结构的答案。
对于相邻两个元素，它们被选取的概率永远是相等的，我们设 $f_{i,j}\ (i<j)$ 表示两个元素分别为 $(i,j)$ 时期望的相遇位置，$O(n^2)$ dp 即可，然后这题就做完了。
CF103E Buying Sets
很神奇的一道题。
转化为最大权闭合子图模型，选了集合就必须选集合中的元素。
题目保证任意 $k$ 个集合的并中元素个数 $\ge k$，而我们希望这里取到等号，设定充分大的值 inf，考虑给每个元素的权值减去 inf，每个集合的权值设定为 inf。若集合个数少于元素个数，则此时总权值是充分小的，最终的答案一定在集合个数和元素个数相等时取到。
CF708D Incorrect Flow
类似有源汇上下界最小费用可行流，先把必须流的流了再调整。
AtCoder Educational DP Contest X. Tower
这种贪心技巧有个名字叫 exchange arguments，考虑交换相邻的两个元素能否使答案更优，从而得到某种最优解所具有的偏序关系进行贪心。
本题中，考虑什么时候 $a$ 一定要放在 $b$ 上方，令放在 $a,b$ 的箱子总重为 $w_0$，则此时有 $w_0+w_b>s_a$ 且 $w_0+w_a\le s_b$，移项联立有 $s_a-w_b<w_0\le s_b-w_a$，即 $s_a+w_a<s_b+w_b$。于是我们按照这一偏序关系排序后做背包即可。
ARC121D 1 or 2
对于选取两个元素的情况很容易发现最大值和最小值配对，次大值和次小值配对，以此类推是最优的。
但是题目的这个结构并不对称，还有只选一个元素的情况，我们可以在序列中添 0，这样选 0 + 某个元素就相当于只选择了一个元素。
枚举 0 的个数，视实现复杂度为 $O(n^2)$ 或 $O(n^2\log n)$。
CF1693C Keshi in Search of AmShZ
dp 是好想的，设 $f_u$ 表示从 $u$ 到 $n$ 最少需要多少天，将一个点的出边集合 $adj$ 按照 $f$ 值从小到大排序，则：
$$
f_u=\min_k\left\{ \sum_{i=1}^k f_{adj_i}+deg_u-k\right\}
$$
问题在于，图中可能有环，难以确定转移顺序。
注意到如果我们将 dp 的转移视作图上的边，显然所有边的权值都是正的，我们可以用 Dijkstra 解决这一问题。
Dijkstra 每次取出一个当前 $dis$ 最小的顶点，在本题中，显然若其他点当前的 $f$ 值都比自己大，从别的点转移显然无论如何都是不优的，那么这个点的 $f$ 值就可以直接固定了。另外，Dijkstra 满足每次处理的点的 $dis$ 是单调不降的，所以我们可以很方便地维护本题中的这一转移方程。
类似的题目有 LG4042 [AHOI2014/JSOI2014] 骑士游戏。
本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
