P14404 [JOISC 2016] 最差的记者 2 / Worst Reporter 2
首先按照 \(B_i,D_i\) 升序排序。
那么对于一个 \(2\) 小时后的结果 \(i\)，它在结束时可以变成任意 \(D_j \ge B_i\)，代价为 \([A_i \ne C_j]\)。相当于 \([pos_i,n]\) 这些都可以选，且当 \(A_i =C_j\) 时不需要代价。
现在要给每个点匹配一个点，使得代价和最小，且不能匹配相同的点。
如果 \(x \to X,y \to Y\)：
- \(A_x =C_X \land A_y=C_Y\)。代价为 \(0\)。
- \(A_x =C_X \land A_y \ne C_Y\)，在能交换的情况下，交换没用。
- \(A_x \ne C_X \land A_y =C_Y\)，同上。
- \(A_x \ne C_X \land A_y\ne C_Y\)。
- \(A_x =C_Y \lor A_y=C_{X}\)，在能交换的情况下，交换更优。
- \(A_x \ne C_Y \land A_y \ne C_X\)，交换没用。
同时由于 \(pos_i\) 单增，所以首先尽量给每个点匹配最右边和它颜色相同的点不劣。剩下的点一定要代价。
但是直接给每个点匹配最右边能匹配上的颜色相同的点，会有些点匹配不上的情况。就比如：
3
1 0
2 1
3 23 0
1 1
3 2
此时 \(1\) 匹配 \(2\)，\(3\) 匹配 \(3\) 的话，\(2\) 就配不上了。
问题就是到 \(i\) 的时候 \([pos_i,n]\) 都满了，此时应该选择一个最小的，且匹配点在 \([pos_i,n]\) 的点撤销它的匹配。如果撤销后仍然能找到和它颜色相同的，那一定是这个点前面一个同色的点的匹配点，此时是一个整体平移，直到第一个不能找到同色点为止。那么我们撤销的点实际上应该是这么平移后得到的最前面那个无法找到同色点 \(id\) 最小的那个。
维护每个点的 \(next\)，表示如果它的 \(next\) 被撤销了，将会匹配这个点现在的匹配点，同时令这个点撤销。那么每次就是找到区间 \([pos_i,n]\) 中链头 \(id\) 最小的那个撤销。如果这个颜色能一直匹配，链头为 \(0\)。但是很难维护感觉。
发现可以倒着直接做，因为我们的决策是优先给能匹配上的点匹配不劣。所以倒着枚举 \(i\)，每次找到一个最小的 \(j\)，使得它们颜色相同且 \(B_i \le D_j\) 且 \(i\) 可以匹配上 \(j\)。类似于染色法，如果这个 \(j\) 已经被匹配了，但是匹配它的点和它颜色不同，那么在这个点可匹配其它点的情况下我们也是可以让 \(i,j\) 匹配的。如果不存在，找到最小的一个 \(j\)，使得 \(B_i \le D_j\) 即可。直接做时间复杂度 \(O(n^2)\)。
考虑优化这个过程。首先找到第一个同色未匹配点可以直接拿 set 进行二分，时间复杂度 \(O(\log n)\)。找到第一个未匹配点也可以用 set。而对于找第一个同色被匹配且该匹配点和它颜色不同且可以撤销匹配的点，根据 \(pos_i\) 随 \(i\) 增加不降，如果存在，一定是第一个被匹配且匹配点和它颜色不同的同色点。这个也可以拿 set 维护。总时间复杂度 \(O(n\log n)\)。
P11812 [PA 2015] 精确打击 / Kontrmanifestacja
找到所有边数 \(\ge 1\) 的环的交。
先缩点，那么只会有一个强连通分量大小大于 \(1\)，否则交集一定为空集。
一个点在所有环的交上，当仅当删掉它之后所有强连通分量大小为 \(1\)。直接做时间复杂度 \(O(n^2)\)。
判断它是交集中的点不好做，那么考虑判断这个点不在交集中。也就是是否存在至少一个环没有经过 \(x\)。
换个思路。因为是求所有环的交，所以答案一定在某个环上。任意找到其中一个环，显然这个环包含了答案中的所有点。此时删去这个环上的点后不能够存在其它环，否则这两个环是相互无交的，答案一定为空。
也就是说，删掉环上点后，图为 DAG。那么考虑环上的附加，如果对于环上两个点 \(u,v\)，存在一条除了起始点外不经过环上边的路径 \(P\)，使得 \(P\) 从 \(u\) 到 \(v\)，那么显然环上 \(u\) 到 \(v\) 的路径中所有点都不会是答案。因为 \(P + p(v,u)\) 是一个环。
那么对每个 \(u\)，找到环上距离它最远的 \(v\)，使得存在这样的路径 \(P\)。就可以把所有不在交集中的点删掉，且剩下的点一定是交集中的点。考虑反证法，若存在 \(u,v\)，使得 \(v\) 剩下了且不在交集中：
- 有一个经过了 非环上的边与环上的边的环，该环经过 \(u\) 且不经过 \(v\)。此时这个环第 \(2\) 次经过环上点时到达的点 \(w\) 显然满足 \(p(u,v)\subset p(u,w)\)。那么 \(v\) 理应删掉。
- 有一个只经过非环上的边。答案理应是空集。
那么我们只需要维护从 \(u\) 出发，不经过环上的边时，能够到达和 \(u\) 距离最远的点。破环成链，给环上点重标号，那么就是一个简单 DAG 上 DP。时间复杂度 \(O(n\log n+m)\)。
P9758 [COCI 2022/2023 #3] Baltazar
先求 \(d_{x,y,0/1}\) 表示从 \(x\) 走到 \(y\) 的最短路、次短路。
把 \(u - v\) 之间的边长度增加 \(2\)，有：
- 存在一条最短路不经过这条边。最短路长度不变。
- 所有最短路都经过这条边，且存在一条不经过这条边的次短路。最短路变为：\(\min(d_{1,n,1},d_{1,n,0}+2)\)。
- 所有最短路都经过这条边，且所有次短路都经过这条边。因为第 \(3\) 短路长度 \(D\) 满足 \(D \ge d_{1,n,0}+2\)，所以可以不管。最短路变为 \(d_{1,n,0}+2\)。
那么我们只需要判断某条边是否在最短路图、次短路图，某条边是否一定被经过即可。维护最短路，次短路数量就行了。时间复杂度 \(O(n\log n)\)。
P10046 [CCPC 2023 北京市赛] 哈密顿
答案下界 \(\sum a_i -\sum b_i\)。
考虑 \(a_i,b_i\) 只会有：
- \(++\)。此时贡献 \(2\)。
- $+- $ 或 \(-+\)。此时贡献 \(0\)。
- \(--\)。此时贡献 \(-2\)。
只要最后贡献和为 \(0\)，也就是有 \(n\) 个 \(+\) 和 \(n\) 个 \(-\)，且要么只有 \(+-\)，要么只有 \(-+\)，要么都有且有至少一个 \(++\) 或 \(--\) 就一定可以凑出一个回路。定义状态函数 \(f_{i,j,0/1}\) 表示前 \(i\) 个数，贡献和为 \(j\)，且是否有 \(++\) 或 \(--\) 时的最大价值和。时间复杂度 \(O(n^2)\)。
暴力 \(O(nV)\) 就过了，把 \(V\) 开到 \(1000\)。其中 \(V\) 是 \(|cnt_{+}-cnt_{-}|\)。
AT_agc056_d [AGC056D] Subset Sum Game
枚举 Alice 第一次拿的数。那么变成 Bob 先手，且 \(L' \le S_a \le R'\)。那么若 Bob 最后拿的数是 \(x\)，删去 \(x\) 后 Alice 能够拿到的最小和 \(S_{amin} > R'\) 或者最大和 \(S_{amax} < L'\)，则 Bob 一定有办法让 Alice 输。同时如果满足 \(S_{amin}<L' \land S_{amax}>R'\)，Alice 也不能赢。反之 Alice 可以通过两两捆绑的形式让自己赢。此时只需要满足无论 Bob 最后一个数 \(x\) 是剩下的 \(n-1\) 个数中哪一个 Alice 都能赢，Alice 就必赢。否则必输。