最近写的一些 WC2019 上讲的一些题。还是怕忘了，写点东西记录一下。
LOJ2983 「WC2019」数树
题意
本题包含三个问题：
- 问题 0：已知两棵 (n) 个节点的树的形态（两棵树的节点标号均为 (1) 至 (n)），其中第一棵树是红树，第二棵树是蓝树。要给予每个节点一个 ([1, y]) 中的整数，使得对于任意两个节点 (p, q)，如果存在一条路径 ((a_1 = p, a_2, cdots , a_m = q)) 同时属于这两棵树，则 (p, q) 必须被给予相同的数。求给予数的方案数。
- 存在一条路径同时属于这两棵树的定义见「题目背景」。
- 问题 1：已知蓝树，对于红树的所有 (n^{n−2}) 种选择方案，求问题 0 的答案之和。
- 问题 2：对于蓝树的所有 (n^{n−2}) 种选择方案，求问题 1 的答案之和。
提示：(n) 个节点的树一共有 (n^{n−2}) 种。
在不同的测试点中，你将可能需要回答不同的问题。我们将用 ( ext{op}) 来指代你需要回答的问题编号（对应上述 0、 1、 2）。
由于答案可能很大，因此你只需要输出答案对 (998, 244, 353) 取模的结果即可。
所有测试点均满足 (3 le n le 10^5， 1 le y lt 998244353， ext{op} in {0, 1, 2})。
题解
( ext{op} = 0) 送分。
op = 1
考场上其实想到了 (O(n^2)) 的 ( ext{DP}) 做法，然而没有意识到自己容斥容反了，调了一个世纪也没调出来……耗去了2.5h最后却只收获了暴力分……赛后补题的时候，尝试把考场代码重新写一下，结果再次得到了和考场上一样的答案……最后想了好久才找到问题……
无根树计数容易想到利用 Prufer 序列。考虑枚举蓝树上的一个边集 (S) ，强制让红树选择这个边集，这样红树就形成了 (m = n - |S|) 个联通块。我们把每个联通块缩成一个点，再将这些点用一些边相连，就是红树的方案数。注意一个点的度数对应到 Prufer 序列上就是这个点的出现次数 + 1。因此，对应到 Prufer 序上，如果我们定义一个 Prufer 序列的权值，等于 Prufer 序列上每个位置代表的联通块的大小的乘积，那么红树的方案数，就相当于所有 Prufer 序列的权值之和，在乘上每个联通块的大小的乘积。由于 Prufer 序上每个位置的出现都是等概率的，所以所有的方案之和，就等于 (n^{m - 2} displaystyle prod_{i = 1}^{m} sz_i) 。其中 (sz_i) 表示第 (i) 个联通块的大小。
注意到在这里我们只强制了某些树边一定存在，但没有强制其它边一定不存在，因此还要考虑怎么容斥。考虑对于红树和蓝树有 (i) 条重边的时候，对答案的贡献是 (y^{n - i})。而如果我们按照上面所述进行计算的时候，我们会对 (S) 的每个子集算出它的贡献。也就是说，我们需要构造一个容斥系数，满足 (displaystyle sum_{i = 0}^{|S|} y^{n - i} {|S| choose i} f_i = y^{n - |S|}) 。
我们考虑在最后对答案乘上 (y^n) ，用 (y) 的逆元代替 (y)，则上式可化为 (displaystyle sum_{i = 0}^{|S|} y^i {|S| choose i} f_i = y^{|S|}) 。容易发现，(y^i f_i = (y - 1)^i) 。
有了前面这些东西，我们就可以直接 ( ext{DP}) 了。设 (dp_{i,j}) 表示考虑到了 (i) 的子树，(i) 所在的联通块大小为 (j) 的贡献之和。转移直接拼子树，然后在 (i) 处考虑是否断开 (i) 与 (i) 的父亲之间的边就行了。
考试的时候犯的错误，就是少了对 (y) 求逆，答案乘上 (y^n) 那一步，然后就导致容斥的时候往 (> |S|) 的那个方向容斥了，过不了样例的时候心态很爆炸……缺少冷静分析。
由 (O(n^2)) 优化到 (O(n)) 只需要考虑这个 ( ext{DP}) 的组合意义。注意到难以处理的地方就在于这个联通块大小的乘积。我们发现这个东西的组合意义，就是在每个联通块内选出一个点，因此可以用 (dp_{i,0/1}) 表示是否在这个联通块内选出了点，直接 ( ext{DP}) 即可。
op = 2
事实上，有了我们刚刚的推论，接下来的问题也就没那么复杂了。考虑两棵树都没有确定时，同样枚举两树的公共边集 (|S|)，那么接下来只需要把两棵树分别连起来就好。因此答案就可以表示为 (displaystyle sum_{S} (n^{m - 2} displaystyle prod_{i = 1}^{m} sz_i)^2 (y - 1)^{|S|}) 。
考虑对集合 (S) 进行 ( ext{DP})。设 (dp_{i}) 表示选出了一个大小为 (i) 的集合的贡献之和。转移只需要枚举一个联通块的大小 (j)，然后把贡献拆掉乘进去就行了。注意需要强制转移的顺序，因为联通块之间是无序的。这样就可以得到一个 (O(n^2)) 的解法了。
很容易发现这个 ( ext{DP}) 可以轻松用多项式优化。可以写分治 + ( ext{FFT})，也可以多项式 ( ext{exp}) 。复杂度分别为 (O(n log^2 n)) 和 (O(n log n))，通过此题都绰绰有余。
总结
容斥的时候一定要仔细分析清楚啊……至今仍然对这个题耿耿于怀。毕竟在得到 (op = 1) 的 (O(n^2)) 做法之后，想要得到 (op = 2) 的 (O(n log^2 n)) 做法实在难度不大。不过考试毕竟是考试吧，与平常的练习肯定是有区别的。即使当时心态没有爆炸，在考场上真的写出了这个题的高分做法的话，其他题的得分也不会太好看。所以说考试的时候还是要适当取舍，要的就是尽快抢分，而不是死刚一题的倔强。
以及自己对于 Matrix-Tree 那套理论不大熟悉，也要注意一下。
LOJ2864 「IOI2018」排座位
题意
你要在一个长方形大厅里举办国际编程比赛，该大厅共有 (HW) 个座位（(H) 行 (W) 列）。行的编号是从 (0) 到 (H-1)，列的编号是从 (0) 到 (W-1)。位于 (r) 行 (c) 列的座位用 ((r,c)) 表示。一共邀请了 (HW) 位参赛者，编号是从 (0) 到 (HW-1)。你制定好了一个座位表，第 (i)（(0le ile HW-1)）个参赛者被安排到座位 ((R_i,C_i))。座位表中参赛者和座位是一一对应的。
大厅中一个座位集合 (S) 被称为是长方形的，如果存在整数 (r_1,r_2,c_1) 和 (c_2) 满足下列条件：
- (0le r_1le r_2le H-1)。
- (0le c_1le c_2le W-1)。
- (S) 正好是所有满足 (r_1le rle r_2) 和 (c_1le cle c_2) 的座位 ((r,c)) 的集合。
如果一个长方形座位集合包含 (k)（(1le kle HW)）个座位，并且被分配到这个集合的参赛者的编号恰好是从 (0) 到 (k-1)，那么该集合是美妙的。一个座位表的美妙度定义为这个表中美妙的长方形座位集合的个数。
在准备好座位表后，你会收到一些交换两个参赛者座位的请求。具体来说，有 (Q) 个这样的请求，按时间顺序编号为 (0) 到 (Q-1)。第 (j)（(0le jle Q-1)）个请求希望交换参赛者 (A_j) 和 (B_j) 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。
- (1le H)
- (1le W)
- (HWle 1 000 000)
- (0le R_ile H - 1)（(0 le i le HW - 1)）
- (0le C_ile W - 1)（(0 le i le HW - 1)）
- ((R_i,C_i) e(R_j,C_j))（(0 le i < j le HW-1)）
- (1le Qle 50 000)
题解
题目中 Subtask5 是个很重要的提示，即考虑对于 (H = 1) 的情况该如何处理。注意到当 (H = 1) 时，等价于求有多少个 (k) 满足如果我们将所有编号小于等于 (k) 的格子染黑，那么这些黑色格子必须要形成一个联通块，即 (点数 - 边数 = 1)。我们发现，每次修改只会对常数个位置的点数和边数进行修改，因此就可以在 (O(Q log (HW))) 的时间内解决 Subtask5。
对于 Subtask6，一维坐标变为了二维坐标，这样不仅要求只有一个联通块，还要求这个联通块一定是一个矩形。把规律总结一下，就需要满足以下两个条件：
- 左边和上面都不是黑点的黑点有恰好 (1) 个。
- 上下左右有至少 (2) 个黑点的白点只有 (0) 个。
看起来需要满足两个条件，然而条件 (1) 中合法的不会 (< 1) 个，条件 (2) 中合法的不会 (< 0) 个，于是只要加起来看是否 (= 1) 就行了。每次修改同样只会对常数个位置进行修改，因此直接用线段树维护这两个值相加的最小值和最小值个数即可。时间复杂度 (O(Q log (HW)))。
总结
对于这类联通块个数相关的问题，可以考虑转化为点数 - 边数。然后用数据结构来维护相关信息，很常用的一个套路。
LOJ2866 「IOI2018」机械娃娃
题意
告诉你触发器的数量 (M)。再给你一个长度为 (N) 的序列 (A)，序列的每个元素都是某个触发器的序列号。每个触发器会在序列 (A) 中出现若干次（也可能是零次）。你的任务是设计一个管路，以满足如下条件：
- 球在若干步之后返回到起点。
- 当球首次返回到起点时，所有开关的状态都是
X。 - 在球首次返回到起点时，此前它进入所有触发器的总次数恰好为 (N)。这些被进入过的触发器，其序列号按照被球经过的顺序依次为 (A_0,A_1,ldots ,A_{N-1})。
- 设 (P) 为球首次返回到起点时，球所引起的所有开关状态切换的总次数。(P) 不能超过 (2 imes 10^7)。
同时，你不想用太多的开关。
对于全部数据，(1le Mle 10^5,1le Nle 2 imes 10^5,1le A_kle N (0le kle N-1))。如果 (Sle N+log_2 N)，你将获得该测试样例的满分。
题解
如果序列长度恰好满足 (N = 2^k) ，那么可以考虑用一个二叉树进行构造。其中每个节点往下连接两个节点处，使用一个开关，最后所有的叶子节点连向目标触发器，每个触发器连向二叉树的根，最后一个叶子节点直接连回起点。注意由于最后这个叶子不能用上，所以可以在起点先连向第一个触发器。
如果 (N eq 2^k) ，可以考虑 (N) 的二进制拆分，然后对于每个二进制为 (1) 的位都建一棵二叉树相连。这样总开关个数就是 (N + log_2 N) 级别了。
总结
纯粹的脑洞题吧，不过还是可以从交互次数出发，思考一下相关的做法。
LOJ2867 「IOI2018」高速公路收费
题意
在日本，城市是用一个高速公路网络连接起来的。这个网络包含 (N) 个城市和 (M) 条高速公路。每条高速公路都连接着两个不同的城市。不会有两条高速公路连接相同的两个城市。城市的编号是从 (0) 到 (N-1)，高速公路的编号则是从 (0) 到 (M-1)。每条高速公路都可以双向行驶。你可以从任何一个城市出发，通过这些高速公路到达其他任何一个城市。
使用每条高速公路都要收费。每条高速公路的收费都会取决于它的交通状况。交通状况或者为顺畅，或者为繁忙。当一条高速公路的交通状况为顺畅时，费用为 (A) 日元（日本货币），而当交通状况为繁忙时，费用为 (B) 日元。这里必有 (Alt B)。注意，(A) 和 (B) 的值对你是已知的。
你有一部机器，当给定所有高速公路的交通状况后，它就能计算出在给定的交通状况下，在两个城市 (S) 和 (T)（(S eq T)）之间旅行所需要的最小的高速总费用。
然而，这台机器只是一个原型。所以 (S) 和 (T) 的值是固定的（即它已经被硬编码到机器中），但是你并不知道它们的值是什么。你的任务就是去找出 (S) 和 (T) 的值。为了找出答案，你打算先给机器设定几种交通状况，然后利用它输出的高速费用来推断出 (S) 和 (T)。由于设定高速公路交通状况的代价很大，所以你并不想使用这台机器很多次。
对于全部数据：
- (2le Nle 9 imes 10^4,1le Mle 1.3 imes 10^5,1le Alt Ble 10^9)
- 对于每一个 (0le ile M-1)
- (0le U[i],V[i]le N-1)
- (U[i] eq V[i])
- 保证数据无重边。
- 你可以从任何一个城市出发，通过高速公路到达其他任何一个城市。
- (0le S,Tle N-1,S eq T)
设函数 ask 调用了 (X) 次。如果 (Xle 50) ，你将获得满分。
题解
首先考虑树的情况怎么做。考虑从任意一个点开始，在 bfs 序上二分，可以轻松找到那个 bfs 序更大的那个点。再从这个点出发，再做一次 bfs 二分就能得到起点与终点的位置。次数是 (2 log_2 N) 的。
当我们把树上的做法扩展到图上的时候，我们发现二分并不能直接得到 bfs 更大的那个点了。但我们可以任选一个点作为起点，建出它的 bfs 树，用二分得到最短路上的一个点。我们再以这个点为根，建立 bfs 树。容易发现这样我们就转化为了树的情况。不过这么做，我们需要 (3 log_2 N + 1 = 52) 次。
考虑沿用上面的方法，但是我们这次直接二分得到最短路上的一条边。这样我们对这条边的两侧分别做一次二分，这样由于两侧大小除了个 (2) 。于是次数就变成了 (3 log_2 frac{N}{2} + 1 = 50) 次，出题人早帮你算好了。
总结
对于图上的某些问题，可以先考虑将问题特殊化的做法——即放到树上考虑。以及同样的，可以对着交互次数来凑算法。
LOJ2868 「IOI2018」会议
题意
有 (N) 座山横着排成一行，从左到右编号为从 (0) 到 (N-1)。山 (i) 的高度为 (H_i)（(0le ile N-1)）。每座山的顶上恰好住着一个人。
你打算举行 (Q) 个会议，编号为从 (0) 到 (Q-1)。会议 (j)（(0le jle Q-1)）的参加者为住在从山 (L_j) 到山 (R_j)（包括 (L_j) 和 (R_j)）上的人（(0le L_jle R_jle N-1)）。对于该会议，你必须选择某个山 (x) 做为会议举办地（(L_jle xle R_j)）。举办该会议的成本与你的选择有关，其计算方式如下：
- 来自每座山 (y)（(L_jle yle R_j)）的参会者的成本，等于在山 (x) 和 (y) 之间（包含 (x) 和 (y)）的所有山的最大高度。特别地，来自山 (x) 的参会者的成本是 (H_x)，也就是山 (x) 的高度。
- 会议的成本等于其所有参会者的成本之和。
你想要用最低的成本来举办每个会议。
注意，所有的参会者将在每次会议后回到他们自己的山；所以一个会议的成本不会受到先前会议的影响。
对于全部数据：
- (1le N,Qle 7.5 imes 10^5)
- (1le H_ile 10^9) ((0le ile N-1))
- (0le L_jle R_jle N-1) 且保证区间两两不同（(0le jle Q-1)）。
题解
考虑最后选择的会议点 (p) 会在哪里。如果恰好选在了区间最大值处，可以直接计算，否则一定处在最大值某一侧。两侧显然是等价的，不妨设这个点位于区间最大值的右侧。
我们发现，如果这个点 (p) 位于区间 ([l,r]) 最大值 (x) 的右侧，那么这个贡献可以转化为一个 ([x + 1,r]) 的子问题加上一个定值。于是可以考虑每次找到区间最大值，递归两侧来解决，即建出序列的笛卡尔树。可以发现，我们只要能对于笛卡尔树上的每一个区间 ([l,r]) 维护出所有区间 ([l,i](l le i le r)) 的最小成本，那么最后的答案也能轻松计算了。显然对于区间 ([l,r]) 的最大值的位置 (x)，(l le i le x) 的最小成本我们可以直接从左子树沿用过来，所以我们只需要快速维护处右子树的答案。可以发现
注意到这里两个决策是有可二分的，即从某个位置 (pos) 开始，后面的决策会更优，否则前面的决策会更优。这是因为 (Cost(x + 1, i + 1) − Cost(x + 1, i) le max_{x + 1 le j le i + 1}H_j le H_x) 。
于是我们可以直接用线段树来维护这些最小成本。在线段树上二分得到 (pos) ，随后只要支持区间加等差数列，区间赋值即可。时间复杂度 (O((n + q) log n)) 。
总结
题目很神仙，很多地方思路挺卡人的。包括第一步里面考虑决策点与最大值的位置关系，发现信息可以共用之后，建出笛卡尔树来计算，以及最后这个决策可二分都比较巧妙。
对于这种贡献和区间最大值关系密切的问题，建出笛卡尔树可以让题目更加清晰。以及对于不少问题，利用树的结构来共用信息，降低复杂度——这似乎是一个很通用的 idea，本质上有点类似于记忆化搜索？
LOJ2390 「JOISC2017 Day 1」开荒者
题意
开荒者要让一片长方形的平原长满草。这个长方形可视为 (W) 行 (H) 列的正方形网格，底平行于南北方向，高平行于东西方向。我们用 ((1,1)) 表示网格的西北角，((W,H)) 表示网格的东南角。开始时有且只有 (N) 个网格内长有野草，其余网格内既没有草也没有草籽。开荒者们可以控制这片平原上的风往东、西、南、北四个方向中的一个方向吹。
每年夏天，草会制造草籽。开荒者们会选定当年夏天的风向。所有草籽会被风扬起，并根据风向移动一格。来年春天，有草籽降落的网格就会有草萌发。假设草不会枯萎。
我们假设不会有草籽从平原外飘进平原内，飘出网格的草籽不会发芽。试求：让这片平原长满草最少需要几年。
(1le Nle 300, 1le W, Hle 10^9, 1le S_i le W, 1le E_ile H, (S_i, E_i)≠(S_j, E_j)(1le i<jle N)) 。
题解
考虑只有一行的情况，设最左边的草与左边界的距离为 (A) ，最右边的草与右边界的距离为 (B) ，相邻两个长有草的格子最大距离为 (C) 。这样最小步数就是 (max{A + B,C}) 。
注意到操作顺序是无关的，所以先枚举往上走了 (X) 步，往下走了 (Y) 步。注意到这里可以看做枚举一共向下走了 (X + Y) 步，再把网格往下移动 (Y) 步。这样我们用一个单调队列维护 (max A,max B,max C) 即可在 (O(NH)) 内解决。
显然有效状态数不多，考虑如何压状态。首先考虑，如果我们确定了 (X + Y) 的值，即形成了一列一列的草块，哪些位置作为网格的上边界是有效的。我们只需要保留那些上边界从上往下扫过来，一行的状态变优的位置。这些位置就只包含第一行，以及所有草块开头的行。这样合法的 (X + Y) 是 (O(n)) 级别的。
现在如果我们确定了网格的位置，考虑哪些 (X + Y) 是有效的。
- 首先很显然所有的 (x_j < x_i,X + Y = x_i - x_j - 1) 是有效的。可能会有疑问，为何 (X + Y = x_i - x_j) 不是有效的呢？如果 (X + Y = x_i - x_j) 意味着第 (i) 块草与第 (j) 块草同时存在于某一行。对于 (H ge 2) 的情况，与这一行相邻的两行相对于这两个元素的状态，仍然是相同的。因此这种操作没有意义；对于 (H = 1) 就不存在这种情况。
- 还有一个有些容易忽略的就是，(X + Y = x_i - x_j + H - 1) ，这个原因需要结合之前所说的合法网格上边界。考虑一个合法的上边界为 (x_i) ，这样当 (X + Y) 从 (0) 开始不断增大的过程中，当 (X + Y = x_i - x_j + H - 1) 的时候，(x_j) 处的草会长到下边界处。这样对于 (x_j) 而言状态发生了改变，因此需要记录下来。
于是合法的 (X + Y) 的数量就是 (O(n^2)) 级别的。利用精致的枚举我们终于把这个题优化到了 (O(n^3)) 。
总结
又是一道神仙题，而且还比较难写……对于状态数十分稀疏的问题，可以考虑哪些状态是有效的，然后对于有效的状态去枚举或者 DP。尤其是对于一类最优化问题，需要仔细分析各种性质，尽可能舍弃重复或者不优于某些状态的状态。
LOJ2392 「JOISC 2017 Day 1」烟花棒
题意
有 (N) 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 (T) 秒。每个烟花只能被点燃一次。
(1) 号站在原点，(i) 号 ((1le ile N)) 到 (1) 号的距离为 (X_i)。保证 (X_1=0,) (X_1, X_2, dots, X_N) 单调递增（可能有人位置重叠）。
开始时， (K) 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。
求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数。
(1le K, N le 10^5, 1le Tle 10^9, 0le X_ile 10^9 (1le ile N), X_1 = 0, {X_N}) 单调递增。
题解
显然需要二分答案。注意到无论 (K) 号怎么走，其他的人肯定都是向中间靠拢。我们让 (K) 不动，相当于可以让左侧的人或者右侧的人以 (2s) 的速度向 (K) 靠拢。我们求出 (K) 左侧和 (K) 右侧的相邻两人距离。这样，模型转化为，有两个栈，栈中每个元素有一个权值，你不能在任何时刻使得你取的每个元素权值之和为负数，问是否可能。
类似于 HNOI2018 Day2T2 的贪心，就能得到一个 (O(n log^2 n)) 的做法。不过这里我只需要判断是否合法，相较于原问题少了一个限制。事实上这种做法还不够优秀。
考虑如果取走某个栈的某个前缀之后，会使得你手上的权值之和变大，并且你手上的权值可以保证在拿这个前缀的过程中不会变成负数，那么你肯定会贪心取。这么不断取下去，直到不能取为止。如果此时存在某个栈的某个前缀和为正，但是却取不到，那么一定是无解的。
剩下的该如何做呢？可以发现如果把取物品的过程倒过来，从序列末尾开始做一次相同的贪心。即初始手上的权值即为两个序列的权值之和，每次取一个物品，就将手上的权值减去物品的权值。如果最后也能贪心取到之前两个序列的位置，那么就是合法的。不太好解释到底怎么想到的，感觉这个地方不是那么好想。
总结
对于模型比较绕的题目，可以先转到一个十分基础的模型再来考虑问题。感觉 HNOI2018 Day2T2 那种贪心运用还挺广泛的。
LOJ2398 「JOISC2017 Day 3」自然公园
题意
JOI 岛是一个观光胜地，全岛被定为一个自然公园。
JOI 岛有 (N) 个广场和若干条道路。广场从 (0) 至 (N - 1) 编号。每条道路联结岛内两个不同的广场，可以双向通行。对于每一个广场，至多有 (7) 条道路将它与其他广场相连。对于任意两个不同的广场，至多有 (1) 条道路将它们相连。此外，我们已知任意两个广场都可以通过若干条道路互相到达。
你和你的朋友 IOI 酱决定考察 JOI 岛。为了考察能够高效进行，你不得不掌握全岛的结构。岛上的诸多动物会带来危险，因此由运动细胞发达的 IOI 酱去探索全岛，而你则负责基于 IOI 酱的报告来确定岛的结构。
你可以对 IOI 酱指定两个广场 (A)、(B)，以及若干可以经过的广场，向其询问是否可以只经由指定的广场从 (A) 到达 (B)。IOI 酱会按照询问的内容在岛上探索并报告结果。
由于考察不能持续过长时间，需要将询问次数限制在 (45\,000) 次以内。
题解
先考虑树怎么做。考虑现在有一棵已知树，现在需要扩展一个节点。首先可以用一次二分得到编号最小的与已知树相邻的节点。接着在 bfs 序上二分就可以得到这个节点和已知树中哪个点相连。这样总次数 (2n log_2 n) 。
扩展到图上之后，我们还是可以在 (log n) 的时间找到一个与已知图相邻的点 (x) 。随后我们还要找到和 (x) 直接相邻的剩下的点，这里我就要删掉已经找到的点。对于每个形成的联通块，先判断这个联通块内是否有与 (x) 相连的点，随后继续二分。容易发现这样的次数是 (O(7m + (n + m) log n)) 的。
总结
仍然是从特殊问题出发；对于这种全图的状态未知，需要通过询问得到的问题，可以考虑按点或者按边依次考虑，不断加入已知图。
Codeforces Gym101955F Counting Sheep in Ami Dongsuo
题意
有一张 (n) 个点的拓扑图，每个点有个权值。权值不超过 (w)。有三个人要从同一个点出发，走三条不同的路线，这种方案的权值就是他们最后停在的那三个点的权值和。对于 (k = 0 sim 3w) ，问权值为 (k) 的方案有多少种。模 (10^9 + 7)。
(n le 10000,m le 30000,w le 400) 。
题解
三个人路线不同随便容斥一下就行了。接下来直接考虑从某个点出发，三个人结束时点权和为 (w) 的方案数。直接 ( ext{FFT}) 合并可以做到 (O(mw log w)) ，不过不够优秀。
注意到这里只要求所有点的方案之和，可以考虑先求出每个点的多项式在 (1 sim 3w) 处的点值，直接对点值 ( ext{DP}) ，最后把多项式再插值插回来。这样复杂度就优化到了 (O(mw + w^2)) 。
不大会插值插多项式比较好的方法，也看不太懂 wxh 的代码……就写了个炒鸡麻烦的拉格朗日插值。
总结
比较有意思的 idea。本质上其实也就是对每个多项式 ( ext{DFT}) 之后再加起来 ( ext{IDFT}) 。但是由于初始多项式很稀疏，所以求点值就会很快。
Codeforces Gym101981C Cherry and Chocolate
题意
(A) 和 (B) 在一棵树上玩游戏。(A) 先选一个点染成粉色，(B) 选一个点染成棕色，(A) 再选一个点染成粉色。然后统计这样的点 (v) 的数量：不存在它到棕色点的不经过粉色点的路径。
(A) 想要最大化这个数量，(B) 想要最小化，问最后这个值是多少。
(n le 10^5) 。
题解
考虑两个人的策略。首先 (A) 选了一个点之后，整棵树会断成若干个联通块。(B) 肯定会选择若干个联通块中的某一个重心。随后 (A) 会选择这个重心的最大子树。这样只要枚举 (A) 选择的点，就可以做到 (O(n^2)) 。
注意到 (A,B) 各选定一个点 (x,y) 之后，假如我们现在需要调整 (A) 第一步的策略。如果点 (x) 向点 (y) 相反方向移动的话，那么 (B) 保持原有策略，答案不会变得更劣。因此 (x) 一定会向着 (y) 所在的子树移动。这样只要类似于点分治，每次找到 (y) 所在的子树的重心，然后不断递归，复杂度就是 (O(n log n)) 的了。
总结
对于博弈题，一个重要的思考角度就是，分析出让状态不会变优的策略，然后减掉这些策略的情况，也许复杂度就会变得正确。
Codeforces Gym101981L Lagrange the Chef
题意
给出 (n, X, Y) 和 (n) 个数 (A_i) ，要通过若干次把某个数移到某个位置的操作，使得不存在相邻的 (X) 和 (Y)。问最小操作步数。
(n le 5000, ext{TL = 3s}) 。
题解
先判掉各种答案是 (0 / -1) 的情况。
如果存在一对相邻的 (X) 与 (Y) ，只有两种方式使得他们隔开。一个是往这两个数中间丢一个不是 (X) 或者 (Y) 的数；另一个就是把一个 (X) 或者 (Y) 丢到某个地方去。注意把 (X) 到丢到别的地方，要么是丢到一个 (X) 旁边，要么是丢到既不是 (X) 也不是 (Y) 的旁边。如果是后者，那么答案至少是 (X) 的个数，至多是 (X) 的个数 (+1) ，这个可以直接判掉。如果是前者，我们就可以在 ( ext{DP}) 的时候多记一个状态，即是否有还没动过的 (X) 和 (Y) ，最后强制一定有动过的 (X) 和 (Y) 。
于是就可以 ( ext{DP}) 了。设 (dp_{i,j,x,y,p}) 表示到了第 (i) 个位置，前面空出来了 (j) 个不是 (X) 也不是 (Y) 的数还没放到序列里，是否有 (x / y) 没有动过，以及上一个的数字是什么，转移直接对着两个操作转移即可，时间复杂度 (O(n^2)) 。
总结
可以考虑将有用的操作进行归类，总结出每一类的规律，分类进行转移。