做题笔记（二）

30 mins 还没想法的题或者值得记录的题目：

CF1566F - Points Movement *2600

自己只会 \(\mathcal{O}(nm^2)\) 的 DP，当时以为 DP 没有前途，转而去想其他做法，但是实际上正解就是 DP。

首先要把题目简化，不要让没用的东西影响思考，这一步虽然是简单的，但是确确实实能优化算法。

对于已经被点覆盖到的线段和包含其他线段的线段，可以去掉。

CF1498D - Bananas in a Microwave *2200

这题提供了 另一种求解可行性多重背包 的方法，将物品个数的看作是对转移次数的限制。

设 \(f_i\) 表示之前凑出 \(i\) 最早在哪里，然后 \(g_i\) 表示 这一轮 凑出 \(i\) 所需的最小步数，一开始 \(g_i = [f_i = \inf] \times \inf\)。

对于加法我们有 \(g_{i + a} = \min(g_{i + a}, g_i + 1)\)，对于乘法可以 \(g_{p} = \min(g_{p}, g_i + 1)\)，一个转移合法，当且仅当 \(g_i \le y\)，那么更新 \(f\) 数组即可。

相似题：POJ 1742 Coins。

这东西可扩展性非常广，对于不能保证 \(k\) 和 \(\mathrm{op}(k)\) 大小关系的，可以利用桶优化 Dijkstra 一样做到 \(\mathcal{O}(V)\)。

upd on 8.11：假了，可能会出现先超出值域再变回来的情况。

CF1863G - Swaps *2800

想到了 \(i \to a_i\) 连边，每个连通块独立，这个的交换两点等于交换出边。

然后不清楚贡献怎么算，实际上遇到这样的问题首先考虑树的做法，再考虑加上一个环的解法。

发现了 \(u \to v, v \to v\) 的结构，对于 \(u\) 操作是没用的。

模拟一下发现了操作一下 \(u \to v\)，就会让 \(v\) 变成一个自环。

但是自己没有结合起来考虑，也就是每个点的入边最多选一条。

那么对于树的答案就是 \(\prod (\mathrm{ind}_i + 1)\)，加一是因为可以不选，这样进一步发现所有的树上的点都独立了。

考虑环上：

首先去思考对树的解法放到环上有什么影响，答案是算重了。

一个环有 \(n\) 个点 \(n\) 条边，但是发现我们选择 \(n - 1\) 条边就已经将所有的点变成自环了。

那么对于这种情况，实际上就是有 \(\sum_{i \in \text{cycle}} d_i\)，对于 \(i \to a_i\) 这条边钦定不选，那么其他 \(x \to a_x(x \not= i \and x\in \text{cycle})\) 都选上了，这个点还可以在剩下 \(d_i - 1\) 条边中选或不选，有 \(d\) 种方案。

那么环的答案就是 \(\prod (\mathrm{ind}_i + 1) - \sum_{i \in \text{cycle}} d_i\)。

对于不同的部分显然是独立的，那么直接乘起来。

CF1327F - AND Segments *2500

首先每一位是独立的，限制形如区间均为 \(1\) 和区间存在 \(0\)。

然后卡住了，没有什么解题方向，实际上这时候应该先去考虑暴力的 DP。

设 \(f(i, j)\) 表示填了前 \(i\) 个位置，最后一个 \(0\) 的位置为 \(j\) 的方案，预处理出一个 \(\mathrm{pos}(i)\) 表示 \(i\) 之前（不含 \(i\)）的 \(0\) 能放到的最前的位置。

对于一个限制 \(\exists i \in [l, r], a_i = 0\)，我们令 \(\mathrm{pos}(r + 1) = \max(\mathrm{pos}(r + 1), l)\)。

然后考虑 \(f(i, j)\) 暴力的转移：

若 \(j < \mathrm{pos}(i)\)，\(f(i, j) = 0\)，这个，直接维护前缀为 \(0\) 的位置即可。

若 \(\mathrm{pos}(i) \le j < i\)，\(f(i, j) = f(i, j - 1)\)，这个相当于不用转移。

若 \(j = i\)，如果限制了 \(a_i = 1\)，那么答案为 \(0\)，否则答案为 \(\sum\limits_{k = \mathrm{pos}(i)}^{s} f(i - 1, k)\)，此时相当于是整个数组的和，维护这个即可。

于是转移均摊 \(\mathcal{O}(1)\)，总复杂度 \(\mathcal{O}(k(n + m))\)。

以这题为基准，还有许多应用：P6773，P4229，ABC262Ex。

CF1218G - Alpha planetary system *3000

首先我想到了第一步：将三组数分为 \(3k,3k + 1,3k + 2\) 的形式。

当时我认为这个很难直接构造，先思考了二分图的情况，实际上这也是重要的，但是突破口有问题，直接在 DFS 树上构造就至多会有一个不合法！

启发：图的问题先思考树的情况。

对于这一个不合法的，自然是想办法调整。

发现图中有奇环的情况，我们可以 \(+1, +2, +1, \dots\) 来使得这个点的权值加 \(1\)，其他点不变。

否则，说明图是一个二分图。

转而思考将图分成 \(3k + 1, 3k + 2\) 的情况，不妨令根 \(r\) 的目标为 \(3k + 1\)。

若 \(w(r) \not= 2 \pmod 3\)，那么直接合法，因为下一层的点的 \(w = 2\)。

若根的度数为 \(1\)，那么也无妨，因为题目保证了 \(n \ge 3\)，所以下面的点的权值一定大于 \(r\) 的权值。

否则考虑 \((r, x), (r, y)\) 这两条边，令其都加一，最后得到 \(w(r) = 1, w(x) = w(y) = 0\)。

因为 \(x,y\) 不相邻（否则存在奇环），并且其他位置没有 \(w = 0\) 的情况，所以这是合法的。

CF1312F - Attack on Red Kingdom *2500

博弈论好题。

对博弈论方面不够敏感，花了 30mins 才往每个游戏组合起来和 SG 函数上去考虑，然后问题就在于 \(a_i\) 过大，无法暴力求解 SG 函数。

这题的关键在于寻找 SG 函数的循环节。

将连续 \(5\) 个 SG 函数（共 \(15\) 个数字作为一个组合），暴力查找循环节，理论上的最劣情况是 \(4^{15}\)，但是实际上这个值不会超过 36。

那么我们可以快速算 SG 函数，问题也就迎刃而解。