补丁
alexbear103
·
·
个人记录
♿蓝题思路概括♿
1 P1074
远古搜索题，每次先搜确定数量多的行/列以缩小搜索树宽度
2 P1120
远古搜索题。用到以下剪枝：
- 长的先放，因为长的留到后面更不好放
- 如果某个木棍放在目前位置不行，那么所有长度和它相等的也不行（可以加“当前弧优化”）
3 P1262
直接缩点。只用控制一出度点即可。如果有不能被控制的就输出。
4 P1272
树上背包。设f_{p,s}表示生成以p点为根的大小为s的连通块的最小代价。按照0-1背包的思路合并子树状态即可。
注意如果目前的p不是根，则更新答案时要统计上它和父亲的边，也就是要用f_{p,s}+1更新答案。
5 P1278
记搜+状压经典题目。记状态f_{S,c}为将集合S中的字符串拼起来使结尾为c能否做到。
6 P1343
Dinic板子，无需多盐
7 P1350
考虑现在蓝色位置填x个，那么剩下k-x个相当于放到一个a \times (b + d - x)的棋盘里。枚举x并计算组合数即可。
8 P1412
较巧妙的DP。正序转移会有后效性（每次的决策会使后面的收益乘某个系数），故倒序转移
9 P1437
背包。设f_{i, j, k}为[i, n]列中选了k个，第i列选了j个的最大收益。则有转移：
f_{i,l,k + l} \leftarrow f_{i + 1, j, k} + \sum\limits_{p\in [1, l]} a_{i, p}
其中l\in[0, \min(m - k, j + 1)]
答案为f_{0,0,m}
10 P1450
容斥原理。设f_{v}为没有硬币数量限制情况下花v块钱的方案数，可以背包计算。则f_{v-d_i\times c_i}即为规定第i种硬币超限时的方案。容斥计算即可。
11 P1463
约定质因数升序
这样的数若不满足以下条件则一定更劣：
- 质因数指数不升（否则可以将大的指数交换到小的质因子上，以获得更小的大小和不变的因数个数）
- 质因数使用连续（同理，否则可以移到更小的质因数上）
考虑满足以上限制的数质因子最多只用考虑到31。先把满足条件的数搜出来，再取因数个数相同条件下最小的数即可。
12 P1491
次短路。可以把最短路找出来然后枚举删掉最短路中的一条边后计算此时的最短路。可以保证计算出无环的次短路。
一次dijkstra也可以求解次短路，但不保证不重复经过点(?。有时若题目有限制，最短路不能走，则可以考虑次短路。
13 P1640
双倍经验。将武器与属性值建边，得到二分图。依次找每个属性的匹配，若找不到就退出。
14 P1879
状压DP简单题。设f_{i,S}为第i行取S状态的方案数。可以通过预处理单行内合法状态的方式优化。
15 P1896
状压DP简单题。和上道没啥区别。
16 P1950
悬线法经典题。枚举行坐标i，记h_j为(i,j)位置开始向上有多少个可取的点，若该点不可取则约定为-1。
记l_j为j左侧第一个位置p满足h_p \le h_j，r_j为j右侧第一个位置q满足h_q < h_j，可以用单调栈求解。
则j的贡献为(j - l_j) \times (r_j - j) \times h_j。因为l为左侧第一个不大于，r为右侧第一个小于，所以并不会出将一个长方形重复计算的情况（可以感性理解一下）。
17 P1966
策略为将b序列中元素排名和a序列对齐。即b中第i个元素位置要与a中第i个相同。
证明：根据排序不等式，顺序积大于乱序积。故顺序时\sum (a_i - b_i)^2 = \sum a_i ^ 2 + \sum b_i ^2 - 2\sum a_ib_i最小
我们可以记p_i为b_i的排名在a_i排名中的位置（或者说是按照a_i排名进行的排名的排名）。则序列{p_i}需要递增。每次只能邻项交换，则最小交换次数为逆序对个数（典中典）
18 P2034
单调队列典中典。记f_i为前i个中选i的最大收益，则有转移：
f_i = \max\limits_{j\in[i - k, i - 1]} f_{j - 1} + \sum\limits_{l\in(j, i]} a_l
考虑\max中只和j有关，可以单调队列维护
19 P2055
挺唐的二分图（）
将所有需要床的人和他们可以睡的床连边，跑最大匹配。如果所有需要床的人都能匹配上就合法（只能将需要床的人和床连边。不然可能出现你的最大匹配里算了不需要床的人导致NO => YES的情况）
20 P2272
缩点，最后结果为DAG中siz和最大的链。维护最优值的时候顺便更新方案数即可
21 P2107
反悔贪心。对于每个机房，先把走过去并AK的时间算上，并把当前机房放到堆里。如果剩余时间为负，就从堆顶取出一个需要时间最长的机房并放弃。
22 P2158
对于坐标(i,j)如果\gcd(i,j) \neq 1，则会被覆盖。所以最终答案为\{2\sum\limits_{i\in[1, n - 1]} \phi(i)\} -1
23 P2205
离散化操作然后差分即可。虚高了
24 P2202
每次只用考虑和当前正方形离得最近的几个即可。考虑将正方形按照横坐标升序，然后将横坐标差\le k的正方形以纵坐标为关键字加入set中，每次查询其前驱以及后继检查是否重合即可。
insert(x)会返回一个pair，第一个是x在set中的迭代器，第二个是插入是否成功。
所以用set可以做到查询某个元素的指针。将这个指针++或--即可得到前驱后继。
25 P2290
根据prufer序列的性质，问题转换为有一个长为n - 2的序列，其中数i出现d_i - 1次，求合法序列个数。
若\sum d_i - 1 = n - 2，则答案为\large\frac{(n - 2)!}{\prod (d_i - 1)!}。否则条件不合法。
26 P2303
转化思路：枚举\gcd(i,n)，记为d。则[1, n]中与n的\gcd为d的数有\phi (\lfloor \frac n d \rfloor)个
27 P2491
考虑肯定在直径上取。因为在直径上取若不优，则直径可以被优化，矛盾。
双指针枚举直径上边权和不超过r的区间，分别计算到直径两端的距离和从这段区间中的点开始到叶子节点最长距离的贡献即可。
28 P2512
设X_i为第i个人向它左边给出了多少糖果。若其从左边接受糖果则为负数。有a_i - X_i + X_{i + 1} = ave
29 P2518
30 P2520
考虑实际上只有四种操作(a,b),(b,a),(a,-b),(b,-a)，设这四种操作的执行次数为p,q,r,s
则问题转化为使以下两个方程：
(p + r)a + (q + s)b = x
(p - r)b + (q - s)a = y
有合法的解使p,q,r,s为整数，即使p+r,p-r同奇偶，q+s,q-s同奇偶。
若p+r,q+s,p-r,q-s均偶，则方程两边可以提取2。有解条件为 2\gcd(a,b) | x 且 2\gcd(a,b) | y
若p+r,p-r奇，q+s,q-s偶，则可以给第一个方程配一个a，第二个配一个b，然后提取2。有解条件为 2\gcd(a,b) | x+a 且 2\gcd(a,b) | y+b
其余情况同理。
31 P2567
容斥+搜索。
先将1e10中的幸运数字预处理出来。然后搜索计算[1, n]中其倍数的数量。可用剪枝如下：
- 是别的幸运数字倍数的幸运数字不用算
- 目前搜到的lcm超出了就不用继续算
- 可以降序幸运数字，使得lcm能更快超越限制。
32 P2569
降蓝了，苦しい。
朴素转移
设计状态f_{i, s}表示在第i天持有s枚股票的最大收益。则第i天有以下几种转移策略：
-
何もしないで，f_{i, j} = f_{i - 1, j}
-
买入。f_{i, j} = \max\limits_{k \in [j - AS_i, j)} f_{i - W, k} - (j - k) \times AP_i
-
卖出。f_{i, j} = \max\limits_{k \in (j, j + BS_i]} f_{i - W, k} + (k - j) \times BP_i
交易日期一定是i - W，因为情况1将之前的情况合并到现在了
最后的答案：f_{T,0}
时间复杂度O(n^3)
单调队列优化
将 f_{i, j} = \max\limits_{k \in [j - AS_i, j)} f_{i - W, k} - (j - k) \times AP_i整理可得 f_{i, j} = \max\limits_{k \in [j - AS_i, j)}(f_{i - W, k} + k \times AP_i) - j \times AP_i
发现\max里面只和k有关，考虑单调队列维护
时间复杂度O(n^2)
33 P3942
可以进行一个贪心。记f_{p,0}为离p最远的未控制点，f_{p,1}为离p最近的控制站。则如果f_{p,1} + f_{p,0} \ge k，那么p必须被控制。否则我们让p被祖先控制。
感性理解一下：祖先可以覆盖更多节点，所以我们尽量让控制站更靠近祖先更优。
最后判断一下根有没有被控制，若没有则需要在根再建一个。
34 P2657
数位DP经典题。记f_{i,d}为最高位i填d的合法数个数，转移显然。
最后拆数的时候需要注意。记数位数为len。则 f_{i,d} (i\in[1, len),d任意) 都可以取。而 f_{len, d} (d < a_{len}) 也都可以取。最后当第len位填a_{len}时，需要从len-1到1依次填到顶，计算此时的解。即依次计算前i位填满时的解。如果前i位填满不合法就可以直接break
35 P2680
史题无需多盐。
二分最大用时，将超时的路径找出来，用路径差分标记每条边。
然后考虑每条边。如果它能被所有超时路径经过并且能将所有路径优化到mid以下，就合法。
36 P2698
虚高。二分窗口宽度，单调队列维护窗口内最大时间差即可。
37 P2704
状压DP典中典，无需多盐
38 P2740
Dinic板子，无需多盐
39 P2751
贪心。第一问每次取最快完成的A机器。第二问根据第一问完成时间排序，给最晚完成的工件分配最快完成的B机器
38 P1471
线段树经典题。考虑计算方差只需要知道这两个东西：\sum a_i^2，\sum a_i。线段树直接维护即可。
39 P2831
记搜+状压。考虑一个抛物线有两种情况：只打一只猪和打多只猪。
第一种情况的抛物线一定是合法的。
对于第二种情况，可以枚举其穿过的两只猪计算抛物线方程，再计算这条抛物线穿过的点集S。若a\ge 0，则S = \varnothing。否则枚举所有的点，检查是否经过。
设f_{S}为将S集合全部消灭的最小花费。直接记搜即可。
40 P2860
典中典。缩边双，图变成树。计算叶子节点个数lev，则答案为\lceil \frac {lev} 2 \rceil
41 P2882
枚举k，检验是否可行。策略：遇到方向不对的直接反转。如果最后k-1个中还有反向的就不合法，否则用反转次数更新答案。
正确性：每个反向的牛至少被操作一次。可以是被之前的位置操作，或者直接在此处操作。而目前的牛已经被之前的位置操作了，若其反向则必须被操作。第一个反向的牛也必须在此处直接被操作（往前不优，同时不可能再往后了）。归纳法得证。
42 P2915
状压+记搜。记f_{S,i}为集合S已经加入队列并且结尾是i的方案数。
43 P3017
二分每块和的下界。贪心check。策略为尽量让每一块超出的最少。
枚举行。记目前行到上一次横着切的位置为一段。枚举列，若将该段中这一列都加入到目前这块中会导致和超出mid，则切一刀。如果我们要切超过b刀，就需要横着切一刀。最后检查横着是否切了到达了a刀。若到达了a，则我们一定可以让和最小的一块大于mid（可以将多切的横刀撤回）
44 P3066
树上差分。会对所有距离不超过t的祖先产生贡献。路径差分即可。
但注意，这里是子树内距离不超过t。若不限制子树内，则需考虑分层图等其他做法
45 P3072
考虑贴着边走。只搜和标记位置有公共点的方格。公共边长度即外侧周长。
46 P3076
贪心。考虑我们至少要走\sum |s_i - t_i|。而为了载所有乘客，我们需要走n-1次从某人终点到某人起点的路程。同时我们还要从1走到m。
考虑将m视为司机的起点，1视为司机终点（因为司机第一最后一步是从某个终点走到m）。为了最小化终点到起点的代价，我们可以把所有起点终点升序，再对应相减。
47 P3118
状压DP。记f_{S}为看电影集合为S的最晚结束时间。转移：
f_{S\bigcup \{i\}} \leftarrow t_{i,p} + d_i \space (i \notin S, t_{i,p} \le f_S, p极大)
初始化时，若第i个电影有从0时刻开始的场次，则f_{\{ i \}} = d_{i}。否则f_{\{i\}} = -\operatorname{inf}
48 P3119
典中典了。先缩SCC。将建出DAG及其反图，跑以1为源点的最长路。则最后的答案为：
\max\limits_{u\rightarrow v \in rev} dis_u + revdis_v + w_{u\rightarrow v}
因反图上到点v的最长路代表了正图上从v返回1的最长路。
49 P3155
树形DP。记f_{p,0/1}为将p点染为白/黑后使p子树合法的最小代价。叶子节点根据其要求的颜色初始化。
$$f_{p, 0} \leftarrow \min({f_{v, 0} - 1, f_{v, 1}})$$
即$p$的儿子$v$可以选择染为黑，或直接使用$p$的白色。
$f_{p,1}$转移同理。
### #50 P3177
典中典了。树上背包，拆边贡献。
记$f_{p,j}$为$p$子树中有$j$个黑点的最大收益。
转移：
$$f_{p, j + l} \leftarrow f_{v,l} + x \times w_{p\rightarrow v}$$
$$x = (k - l) \times l + (n - k - l + siz_{v}) \times (siz_v - l)$$
$x$为边$p\rightarrow v$被经过的次数。
### #51 P3225
缩vDCC。
特殊情况：
1. 图是一条链：建两个，方案数为$\frac{n(n-1)} 2
- 图是一个巨大的点双：建两个，\frac{n(n-1)} 2
一个点双如果与别的点双只有 < 2个点连接，则必须在这个点双里建两个
一个点双如果与别的点双有\ge2个点连接，可以不建。
52 P3365
典中典。BST中序遍历递增。故先求原树中序遍历，问题转化为将一个序列修改至递增。
考虑如果有两个位置i>j满足a_i - a_j \ge i - j，就可以把(j, i)中的数修改使序列递增。
记f_i为将[1,i]修改至递增并且i不修改时，最多有多少个位置不用修改。则有转移：
f_i = \max\limits_{a_i - a_j \ge i - j} f_j + 1
发现就是\{ a_i - i \}的最长不降子序列长度，O(n\log n)。可求
53 P3469
需要有一个感性理解：点双构成一个类似树的结构（实际上可以建出来，就是圆方树）
下文中的树指dfs树
考虑求割点。对于一个割点p，若删掉它，则它的所有子节点v对应的子树之间都不连通。并且和p子树以外的点也不连通。
对于一个一般的点，删掉以后剩下n-1个点跟他都不连通。
故对于一个点p，删掉它造成的不连通点对数是：
n - 1 + \frac 1 2\sum\limits_{i,j\in son_p} siz_i \times siz_j + (n - siz_p) \times (siz_p - 1)
54 P3694
写一辈子状压
记f_{S}为让S中的乐队归位的最小花费。转移：
f_{S \bigcup \{i\}} \leftarrow f_{S} + c_i - s_{i,r} + s_{i,l-1}
r = \sum\limits_{v \in S \bigcup \{i\}} c_v, l = \sum\limits_{v\in S} c_v
s_{i,p} = \sum\limits_{j\in [1,p]} [a_j = i]
原理比较好理解
55 P3857
建线性基。若线性基个数为x，则答案为2^x
56 P3966
建AC自动机。将每个位置的父亲设为其fail指针指向的点，建出fail树。
设AC自动机中一个点的点权表示它被多少字符串包含。则一个单词在别的单词中出现次数为子树中的权值和。
57 P4090
原题给的是与队尾的距离，现改写为与队头的距离，记为c_i。
若在某个位置i之前存在k个人都满足c_j \le k，则这些人只要到达过一次对头，排名就不会再超过k，那么i就永远拿不到礼物。
所以可以二分第一个拿不到礼物的人。假如能找到k个人使得c_j \le k就成立了。
58 P4145
典中典了。线段树维护。考虑维护区间和的同时维护区间最大值。若执行开跟操作时发现一个区间的最大值为1，就可以不用开了。否则暴力开下去。考虑开根至少会使原数\times 0.5，故复杂度为均摊O(n\log n)
59 CF438D
典中典了。取模时同样检查最大值。同样为均摊O(n\log n)
60 CF165E
高维前缀和板子。维护f_{S}，存放一个为S子集的数。转移显然。
一个和x按位与为0的数为f_{\overline{x}}
61 P4185
离线询问，并查集维护。
62 P4186
和将军令那道题思路有点像（尝试联想一下），我们尽量让一个更大的子树被一个叶子节点控制。
考虑子树p中距p最近的叶子节点的距离mxdis_p若满足mxdis_p \le dep_p，那么子树p中就只用放一个就可以了。
我们可以在所有满足这个要求的点上打个标记，再dfs一次，遇到有标记的点就将答案加一并返回即可
63 P4188
离散化，差分，找所有区间中1数量最小的即可。
64 P4180
先把MST找出来。枚举每一条未加入的边(u,v)，树上倍增求解u\rightarrow v路径上最长的一条边替换掉。就可以得到把(u,v)塞进去的生成树边权和。
65 P4269
典中典了
离线询问，按照s_i升序处理。我们将所有\le s_i的位置都改成-\operatorname{inf}，其余位置设成1。那么全局的最大子段和就是我们最远需要跨越的步长。
线段树维护最大子段和即可。
66 P4268
可以建模为带权树重心，换根DP（）但是码农题。
67 P4281
在树上里三个点距离和最小的点为三个点两两LCA中深度最大的一个，树上倍增即可。
68 P4380
69 P4377
分数规划模板。
考虑二分答案。只需检查是否存在选择集合S使得\frac{\sum\limits_{v\in S} t_v}{\sum\limits_{v\in S} w_v} \ge mid且\sum\limits_{v\in S} w_v \ge W。
将第一个式子移项，得到
\sum\limits_{v\in S} t_v \ge mid \sum\limits_{v\in S} w_v
即
\sum\limits_{v\in S} t_v - mid\times w_v \ge 0
背包，以w_v为代价，t_v - mid \times w_v为收获。将所有代价大于W的状态都合并到W。最后检查是否满足f_W \ge 0即可。
70 P4376
虚高了。二分能满足前几条条件，拓扑排序检查是否有环即可。
71 P4408
看到最长链一定要想到直径（）
找出直径，则A和B分别在直径端点最优。不妨设CA < CB，枚举C取所有点并用CA + d更新答案即可。
72 P4513
线段树维护最大子段和，无需多盐
73 P4550
期望DP典中典。
设f_i为买了i种邮票后，要买到n种邮票的期望次数。转移如下:
f_{i} = \frac{i}{n} (f_{i} + 1) + \frac{n - i}{n}(f_{i + 1} + 1)
化简一下得到f_{i} = f_{i + 1} + \frac{n}{n - i}
设g_i为买了i种邮票，要买到n种邮票的期望价格。转移如下：
g_i = \frac{i}{n}\times(g_i + f_i + 1) + \frac{n - i}{n} (g_{i + 1} + f_{i + 1} + 1)
化简得到g_i = \frac n {n - i} \times f_i + g_{i + 1} + f_{i + 1} + \frac{n}{n-i}
比较关键的是状态设计。为了能够使用全期望公式，需要使每个状态对应的事件发生概率为1。故一般定义为从某处开始到完成的期望代价
74 P4910
矩阵快速幂模板。
转化题意为确定一个01串使得任意相邻两项逻辑或为1
设f_{i,0/1}为第i为填0/1的方案数
有转移f_{i,0} = f_{i - 1, 1}，f_{i,1} = f_{i - 1, 0} + f_{i - 1, 1}
转成矩阵形式：
\begin{bmatrix} f_{n, 0} & f_{n,1}
\end{bmatrix} =
\begin{bmatrix} f_{1, 0} & f_{1,1}
\end{bmatrix} \times
\begin{pmatrix} 0 & 1 \\
1 & 1
\end{pmatrix} ^ {n - 1}
最后的答案为f_{n+1,0}+f_{n+1,1}
75 P5058
缩vDCC。从a开始dfs。若找到一个割点p，且其一个子节点v满足dfn_v \le dfn_b，则可以说明b在v的子树里。
下面考虑反证。假设b不在v子树里：
- 若b先于v搜到，则与 dfn_v \le dfn_b 矛盾。
- 若b在v子树被搜完以后搜到，则此时 dfn_b 仍然为0，同样与 dfn_v \le dfn_b 矛盾。
76 P5122
巧妙的图论建模题
先以n为源点跑一次最短路，记n到点p的距离为dis_p
考虑建一个虚点n+1，将k个有干草块的点p与n+1连边一条长为dis_p - y_p的边。再以n+1为源点跑一次最短路。若此时到点i的距离不大于原来的距离，则证明i会去某个干草块觅食。
77 P5123
bitset作法。
可以用bitset记录喜欢冰激凌x的牛的集合S_x。对于某个牛i,和它不能和平相处的牛的个数即为:
\overline {\bigcup\limits_{j\in[1,5]} S_{a_{i,j}}}
78 P5505
组合数学+容斥
计数难点在于“需要保证所有人都有特产”。
我们先考虑一下如果没有“所有人都要有特产”这条限制该怎么做。
我们可以依次把a_{1 \dots m}分给n个人（允许为空）。则插板法可做。
现在我们考虑设f_i为至少有i个人拿不到特产的方案数。考虑这也比较好算，我们直接少i个板子就好了。有：
f_i = \prod\limits_{j \in [1,m]} \binom{a_j + n - i - 1}{n - i - 1}
设g_i为正好有i个人拿不到特产的方案数。那么有了f_i这就可以容斥了。
g_i = \sum\limits_{j\in [i, n]} (-1)^{j - i} f_j
最后的答案就是g_0
79 P5521
首先考虑为什么DP不行：子树之间的答案不是独立的。一个子树剩下的花可以用于别的子树。所以一个子树的答案是依赖于先于它的子树的答案的。转移会有后效性，于是DP就被毙掉了。
根据上面我们对问题的分析，可以发现将每个子节点放上花的花费是和解决子节点的顺序相关的。记f_u为将u放上w_u朵花的费用，则可以给出如下式子：
f_u = \max\{\max\limits_{v\in son_u}\{f_v + \sum\limits_{k\in son_u, k先于v} w_k \}, \sum\limits_{v\in son_u} w_v \}
所以我们需要确定一个v的顺序使得\max\limits_{v\in son_u}\{f_v + \sum\limits_{k\in son_u, k先于v} w_k \}最小。
考察两个u的子节点x,y，现在考虑若x,y相邻，哪个放在前面。记x,y前的子节点w值之和为s
x$在前时，这两个点的贡献是$\max\{f_x + s, f_y + s + w_x\}
同理，y在前时这两个点贡献是\max\{f_y + s, f_x + s + w_y\}
若x在前，则需满足:
\max\{f_x + s, f_y + s + w_x\} \le \max\{f_y + s, f_x + s + w_y\}
两边同时消去s得：
\max\{f_x, f_y + w_x \} \le \max\{f_y, f_x + w_y \}
考虑有f_x + w_y > f_x，故只需f_x + w_y > f_y + w_x，即f_x - w_x > f_y - w_y即可
所以所有节点按照f_x - w_x降序，即可得到最优序列。
80 P5664
容斥+DP
发表一下感言。其实计数问题没有那么难，要抓住导致直接计数难算的关键矛盾。
比如说这道题：如果没有每列不能选超过\lfloor \frac k 2 \rfloor个这个限制，就很好算了。
我们先考虑把这种情况算出来再容斥。记f_{i,j}为在前i行选j个菜做的方案数。则有转移：
f_{i, j + 1} = f_{i - 1,j} + \sum\limits_{l\in [1, m]} a_{i,l}
注意到\lfloor \frac k 2 \rfloor这个限制，注定了只能有一列超限。我们可以枚举这个超限的列p。记g_{i,d}为前i行中在第p列中选出的比在别的列选出的多d的方案数。则有转移
g_{i,d} = g_{i - 1,d} + g_{i - 1, d + 1} + \sum\limits_{l\in [1, m], l \neq p} a_i,l + g_{i - 1, d - 1} + a_{i,p}
则p超限的方案数和为\sum\limits_{l\in[0,n]} g_{n,l}
从\sum\limits_{l \in [1, n]}f_{n,l}中刨掉即可。
81 P2748
82 P6268
将跳过舞的人建边并染色，建出二分图。答案即为二分图最大独立集大小。考虑独立集中不能存在任意两个可以匹配的点。所以有最大独立集 = 点数 - 最大匹配边数
83 P6554
84 P6475
考虑如果一段楼高不降/不增，并且最高和最低的楼确定，那么方案数可以简单插板计算。
讨论x,y是否在n的同侧。分别计算即可（）
实际上可以是高考题
85 P7077
因为没有递归，故函数调用关系成一个DAG。可以将全局乘法转换为将所有已调用过的加法函数调用次数翻倍。
故可以先在反图上拓扑，求出每个函数调用后会使全局乘法标签翻多少倍。
然后在正图上拓扑，求出每个加法函数的调用次数。
大体思路是这样的，然而代码比较难写（
86 P7687
缩eDCC。考虑一条边u\rightarrow v如果是关键的，那么必然会出现v子树中的所有点或v子树外的所有点将所有提供A/B服务的点独占的情况。求割边时判断一下即可。
♿紫题思路概括♿
1 P1848
动态规划优化DP。
可以给出naive的转移：
f_i = \min\limits_{\sum\limits_{l \in (j, i]} w_l \le L} (f_j + \max\limits_{l\in(j,i]}h_l)
发现\min中和i有关的项可以被线段树维护。具体方法为：用单调栈维护i左侧第一个j满足h_j > h_i。加入h_i时将(j,i]区间赋值为h_i，就可以维护\max h_l。计算完f_i后将f_i加入线段树。再维护f_j + \max h_l的区间最值即可
2 P2045
费用流典中典。
拆点，将一个位置拆成入点和出点。出点向邻接点的入点连流量为k，费用为0的边。入点向相应的出点连一条流量为1、费用为a_{i,j}的边，再连一条流量为k - 1、费用为0的边。跑最大费用最大流即可。
3 P2048
典中典了。
主要矛盾在于我们没法枚举所有子段。
但是如果我们确定了一个区间的左端点和右端点的选取区间，那最优解可以通过在前缀和数组上RMQ得到。
形式地说，记sum_i为到i的前缀和。如果确定左端点为o，右端点的选取区间为[l,r]，则对于这一组条件(o,l,r)最优解为：
\max\limits_{i\in[l,r]} sum_i - sum_{o - 1}
考虑对于一组条件(o,l,r)，若最优解在t取到，那么次优解只能在(o,l,t - 1)或(o,t+1,r)中取到。
解法就呼之欲出了。先把所有(o,o+L,o+R)以最优解的值为关键字放到堆里。每次取出堆顶(o,l,r)，并将(o,l,t-1)和(o,t+1,r)放回堆。注意对于条件(o,l,r)如果r<l，那就不用再进队。
4 P2123
邻项交换法典中典。
5 P3647
换根DP
其实这个游戏规则的限制只有一个点不能作为两条以上蓝线的中点。
现在我们规定蓝线的方向只能是从祖先到后代。即不允许u,v\in son_p，u\rightarrow p \rightarrow v这样的线。那么我们只需要枚举每个点分别作为根的时候的答案即可。
现在考虑求解根确定时的答案。设f_{p,0/1}为p是/不是蓝线中点时p子树的最大贡献。
考虑转移：
f_{p,0} \leftarrow \max(f_{v,0}, f_{v,1} + w_{p\rightarrow v})
定义r_{p\rightarrow v} = {f_{v,0} + w_{p \rightarrow v} - \max(f_{v,0}, f_{v,1} + w_{p\rightarrow v})}，其意义为v对f_{p,1}的贡献
f_{p,1} = f_{p,0} + \max\limits_{v\in son_p}r_v
现考虑O(1)换根。设f_{p,0/1}为在1为根意义下的答案，g_{p,0/1}为在p为根意义下的答案，up_{p,0/1}为在1为根意义下p子节点v子树外的答案。
记p父亲为z，定义r_{p\rightarrow z} = up_{z,0} + w_{z\rightarrow p} - \max(up_{z,0}, up_{z,1} + w_{z\rightarrow p})
那么从p转移到v的过程中：
g_{v,0} = f_{v,0} + \max(up_{p,0}, up_{p,1} + w_{p\rightarrow v})
g_{v,1} = g_{v,0} + \max(\max_{u\in son_v} r_{u \rightarrow v}, r_{v \rightarrow p})
up_{p,0} = g_{p,0} - \max(f_{v,0},f_{v,1} + w_{p\rightarrow v})
up_{p,1} = up_{p,0} + \max(\max\limits_{u \in son_p, u \neq v} r_{p \rightarrow v}, r_{p\rightarrow z})
关于\max\limits_{u \in son_p, u \neq v} r_{p \rightarrow v}，可以维护r_{p \rightarrow v}的最大值和次大值O(1)解决。
换根思路就是去子树贡献。其实很套路。
6 P2480
数论模板全家桶，无需多盐。
题目大意：求\large g^{\sum_{d|n} \binom{n}{d}}，对合数999911659取模
质数がないなら、わたし↑
没有质数没法Lucas，急。所以把模数分解，得到999911659 = 2 \times 3 \times 4679 \times 35617。
考虑分别在四个质数模数意义下算出解，然后发现只需要一次CRT就可以求出原模数意义下的解了。
7 P3622
状压DP好题
设f_{i,S}为考虑到i，从i开始后5个状态为S的最优解。
気付け！S的低位存储的是i，高位存储的是i+4。不要搞反了。
可以先预处理出来w_{i,S}表示站在第i位置我们的方案を楽しめる子的个数。有转移：
f_{i,S} \leftarrow \max(f_{i-1,(S \& 15) << 1}, f_{i - 1, ((s \& 15) << 1) |1}) + w_{i,S}
（latex爆炸致歉。
为了符合环的要求，需要0和n填写的状态能接上。可以枚举开始几位填的状态T。将f_{0,T}设为0，其余设为-inf。最后只用f_{n,T}更新答案。
8 P3629
$k=2$，考虑如下贪心：第一条还是连直径。然后把直径上的边权设为$-1$，再求一次直径。第二条连第二个“直径”的两端。
### #9 P2857
网络流建模一道，比较好理解
考虑建一个虚源点和一个虚汇点。将源点和每头牛之间连一条流量为$1$的边，将汇点和牛棚之间连流量为牛棚容量的边。
那么假如我们确定了每头牛愿意接受哪些牛棚，那存在解的判据就是**最大流为n**
于是我们可以二分座次的跨度，check时枚举座次的范围并据此建图跑最大流即可。
### #10 P2868
分数规划+spfa判负环
我们先二分答案$d$，检查是否存在环使得$\large\frac{\sum F_u}{\sum T_e} \ge d
由于T为正，我们可以稍微移个项，得到：
\sum F_u - d \times \sum T_e \ge 0
即
\sum F_u - dT_e \ge 0
我们发现可以用spfa判负环解决
具体来说，我们将u\rightarrow v的边权修改为F_u - d \times w_{u\rightarrow v}，然后跑SPFA判负环即可。
关于SPFA并不能判复杂负环的问题：发现有复杂负环必定有简单负环，从中拽出一个就好了（）并不存在什么问题。
关于SPFA判的是严格负环而不能取0的问题，我们只要提高二分的精度就可以解决了。
11 P3117
12 P3121
AC自动机+栈
先对模式串建AC自动机，在主串上匹配。用栈记录每次AC自动机上的指针位置。
如果匹配到了模式串t，就将栈顶|t|个元素弹出。然后将AC自动机指针重置到栈顶位置，继续匹配。
13 P3959
状态设计比较有意思
数据范围提示状压。关键问题在于：如何处理代价L\times K中的K。我们考虑将树高这一维写进状态，按照深度顺序加点。
即设f_{S,h}为加入点集合为S，目前树高为h的最小代价。设S中的叶子节点经过一次图上的边能够达到的点集为Z，可以得到以下转移：
f_{S \cup s, h + 1} \leftarrow f_{S, h} + \min (w_{(u, v)}) \times h \\(s \subseteq Z, v\in s, u\in S, (v, p) \in E)
解释：v是由S中叶子点经一条边可达的点。我们只需要贪心地选择一个连到S中点的边权最小的边即可。虽然我们并没有要求，但我们可以认为点v的深度是h+1（因为v深度更小的情况也会被枚举到）。
最后的答案就是\min\limits_{h\in (1,n)} f_{U, h}
14 P3354
主要矛盾是我们需要知道木料运输的终点才方便计算答案。
不妨把终点设计到状态里。设f_{u,t,j,0/1}为在u的子树中，离u最近的伐木场为t且子树中建了j个伐木场的情况下，u建/不建伐木场的最小花费。
设f_{u,t,j,2} = \max(f_{u,t,j,0}, f_{u,t,j,1})，因为转移完u我们就不关心u建没建了。
转移就是树上背包：
f_{u,t,j+l,0} \leftarrow f_{v,t,l,2} + f'_{u,t,j,0}
f_{u,t,j+l,1} \leftarrow f_{v,u,l,2} + f'_{u,t,j,1}
(注意此时并没有计算u的贡献)
合并时：
f_{u,t,0,2} = f_{u,t,0,0} + dis_{t\rightarrow u} \times w_u
f_{u,t,j,2} = \max(f_{u,t,j,0} + dis_{t\rightarrow u} \times w_u, f_{u,t,j - 1,1})
15 P3162
我们假设生产第i个零件的车间中对答案有贡献的车间坐标为f_i，最优解为x，则花费为：
\sum(x - f_i)^2 \\ = nx^2 - 2x\sum f_i + \sum f_i ^ 2
可以发现，x最优位置为\large\frac {\sum f_i}{n}，取到最小花费\sum f_i^2 - \large\frac{(\sum f_i) ^ 2}{n}
那么我们就得到了40分做法：直接枚举f_i是哪些，求出\sum f_i, \sum f_i^2并依照上式计算费用即可。
贪心
但是这其中有些枚举是不必要的。我们转而考虑一个贪心策略：
将生产每种零件的车间坐标升序排序。每次考虑将生产某种零件的一个车间替换为它后面的一个。记将在x位置的车间替换为y的操作为x \rightarrow y。将所有x \rightarrow y按照x + y升序，再依次操作即可。
每个车间只被考虑一次，再加上排序，复杂度O(n \log n)
正确性
我们考虑这种贪心策略忽略了哪些状态的枚举：
假如先后有两次操作x_1 \rightarrow y_1，x_2 \rightarrow y_2，那么x_1,y_2同时选取的情况就被我们忽略了。
假设x_1, y_2同时选取的情况在最优解里。设最优解的位置是p，则p满足p - x_1 < y_1 - p，p - x_2 < y_2 - p，即\frac{x_2 + y_2}{2} < p < {\frac{x_1 + y_1}{2}}，这与x + y升序矛盾。
16 P3226
17 P3237
唯一真史。
人话题意
给一棵树，每个点有一个权值，要求修改一些点的权值，使得：
-
同一个父亲的儿子权值必须相同
-
父亲的取值必须是所有儿子权值之和
哈希。发现只要根节点的权值确定，整棵树就确定了。
我们可以枚举维持点p权值不变条件下根节点的权值f_p。最后只用统计f的众数，即为可以保留不变的位置的最大值。
根据定义给出f_p表达式:
f_{p} = a_p \times \prod_{z\in anc_p} |son_z|
但这样f_{p}一定会乘飞。考虑全体f对2取对数，将乘法转化为加法。
18 P3239
19 P3533
一生に、基环树をやれる。
显然内向树森林。
假如a,b不在同个连通块，寄
假如在同一个子树，会合点为LCA
不在同一个子树，分别尝试从a的根走到b的根和从b的根走到a的根，按照题目要求取最优解即可。
20 P4083
非常好的建图题，使我读谱旋转。
朴素做法
考虑将送馅饼的过程反过来，考虑收到一个馅饼前上一个人送来的馅饼可能是哪些。
将某人评价为0的点设为起点。将一个点它的合法前驱连边。则从某个点i开始最少要传递的次数相当于从某个起点到i的最短路长度。01 bfs可做。
优化
其实已经呼之欲出了。考虑不带边权的话一个点最多被松弛一次。用set维护没有被松弛的节点。每次二分前驱在set中的区间，将每个点松弛后入队并在set中删除即可。
每个点只进出set各一次，O(n \log n)
code
假如说现在的馅饼$p$是人$0$做的，人$0$对它的评分为$x$，它的前驱一定是人$1$做的馅饼中人$0$评分在$[x - d, x)$区间中的。在$set_1$中二分即可。
```cpp
#include <bits/stdc++.h>
#define int long long
#define inf 100000000ll
#define endl '\n'
using namespace std;
const int maxn = 1e5 + 5;
int n, d, a[maxn * 2][2], dis[maxn * 2];
set<pair<int, int> > rem[2]; //存储对方对自己的馅饼的评价
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> d;
for (int i = 1; i <= (n << 1); ++i) {
cin >> a[i][0] >> a[i][1];
}
queue<int> q;
for (int i = 1; i <= (n << 1); ++i) {
if (!a[i][i <= n]) { //如果对方评分为0，作为起点入队
dis[i] = 1;
q.push(i);
} else {
rem[i > n].insert(make_pair(a[i][i <= n], i)); //在自己的集合中加入对方的评分
}
}
while (!q.empty()) {
int now = q.front();
q.pop();
int tp = (now > n);
set<pair<int, int> >::iterator st = rem[tp ^ 1].lower_bound(make_pair(a[now][tp] - d, -inf));
set<pair<int, int> >::iterator en = rem[tp ^ 1].upper_bound(make_pair(a[now][tp], inf));
//在对方做的馅饼中找目前点的前驱
if (st == rem[tp ^ 1].end()) continue;
for (set<pair<int, int> >::iterator it = st; it != en;) {
dis[it->second] = dis[now] + 1;
q.push(it->second);
rem[tp ^ 1].erase(it++);
//松弛，入队，删除。
}
}
for (int i = 1; i <= n; ++i) {
if (!dis[i]) {
cout << -1 << endl;
} else {
cout << dis[i] << endl;
}
}
return 0;
}
```
### #21 P4135
そろそろ詩も終わる時間だ、やっと君の番だからさ。
我本来是要莫队的啊，但是这小子，啪的一下，很快啊，就给我强制在线了。
本来以为要用什么奇技淫巧但实际上还挺板的。
对于一个询问$(l,r)$，如果我们能知道包含在$[l,r]$中的整块中每个数的出现次数，和只考虑这些整块的答案，那合并散块就很好做了。
而这些东西也很好维护。可以维护$f_{i,j}$表示计算整块$i$到整块$j$中哪些数出现了偶数次。再维护$cnt_{i,v}$表示$v$出现的次数的前缀和，便可知道整块部分中每个数出现了多少次。
合并散块时在桶里计数，统计出现在这个数出现了多少次。如果奇变偶就增加答案，否则就减少答案。
对于没有整块的情况暴力计算即可
复杂度$O(n^{\frac{3}{2}})
22 P8867
纯难。
23 P4182
24 P4187
非常好数学题
首先需要掌握判据：合法的充要条件是必须存在一段长度不小于k的同色区间。
直观的做法是枚举同色区间的位置，然后容斥。但发现假如有多个同色区间没法去重。
正难则反
从所有颜色序列中减去不合法的，即没有任何一个同色区间长度\ge k
记f_i为长度为i的不合法序列数量。
若i < k，f_i = mf_{i-1}（随便填）
若i \ge k，f_i = (m-1)\sum\limits_{l \in [i - k + 1]} f_l（接上颜色不同且长度<k的一段）
25 P4211
树剖，将$S$中的点的到根链上点权全部$+1$，答案即为$u$到根链上的点权和
这道题离线询问，按端点升序。按顺序染色到根链并处理询问即可。
### #26 AT_agc018_c
转化题意：先让所有人选金币。再选$y$个人换成银币（收获为$b-a$，记为$e$），选$z$个人换成铜币（收获为$c-a$，记为$f$）。求最大收获
邻项交换法确定哪些人选银币，哪些人选铜币。
假设$x$选银，$y$选铜。不交换的条件为：
$$e_x + f_y \ge e_y + f_x$$
即：
$$e_x - f_x \ge e_y - f_y$$
按照$e-f$降序，显然严格弱序。
只需维护每个位置前缀选$y$个，后缀选$z$个的最大值即可。
### #27 AT_arc018_c
不妨设$x < y
分讨最大值和最小值是否同色。
不同色
#### 同色
不妨设最大和最小都涂的蓝色。现在要最小化红色的极差。
首先最大值位置相对的$x$和最小值位置相对的$y$是肯定要染红的。（这两个位置也要进队）
让剩下的元素按照$x$升序。将所有$x$插入优先队列。枚举将所有的$x$逐步替换为$y$，即将$x$出队，再将$y$加入。查询队列最大值和最小值即可。这个有优先队列可以用```multiset```实现。
#### code
```cpp
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
struct node {
int x, y;
} z[maxn];
signed main() {
int n; cin >> n;
int bmin = 1e18, bmax = 0, rmin = 1e18, rmax = 0;
multiset<int> pq;
for (int i = 1; i <= n; ++i) {
cin >> z[i].x >> z[i].y;
if (z[i].x > z[i].y) swap(z[i].x, z[i].y);
bmin = min(bmin, z[i].x);
rmin = min(rmin, z[i].y);
bmax = max(bmax, z[i].x);
rmax = max(rmax, z[i].y);
pq.insert(z[i].x);
}
int ans = (bmax - bmin) * (rmax - rmin);
sort(z + 1, z + 1 + n, [](node n1, node n2) {
return n1.x < n2.x;
});
for (int i = 1; i < n; ++i) {
pq.erase(pq.find(z[i].x));
pq.insert(z[i].y);
auto bg = pq.begin(), ed = pq.end();
ans = min(ans, (rmax - bmin) * (*(--ed) - *bg));
}
cout << ans << endl;
return 0;
}
```
### #28 P8819
和哈希判基环树森林。
给每个点$p$随机一个权值$w_p
定义r_p = \sum\limits_{v\rightarrow p \in E} w_v
可以O(1)实时维护r_p。
图是基环树森林的判据是\sum r_p = \sum w_p
29 P4381
唯一真史。
基环树直径。
先找环。对于每个联通分量，将其每个子树的直径（别忘了用它更新答案）和最长到根链处理出来。然后再在环上考虑。选定一个环上的点s将环断开并复制一遍。记环上点p子树中的最长到根链长度为f_p，p到s的前缀距离为d_p。则p的贡献为：
\max_{p - v < n}{f_v + f_p + d_p - d_v}
整理
f_p + d_p + \max_{p-v < n}{f_v - d_v}
单调队列即可。
30 P4516
无意义卡空间卡读写卡常数的送去出演新一季奶龙。
树形DP底力题
状态设计
设f_{p,j,0/1,0/1}在p的子树中放了j个监视器，p不放/放，p没被监听/被监听的方案数。
考虑分讨并转移。
转移到f_{p,j,0,0}，v一定不能放，并且得被监听。故f_{p,j + l,0,0} \leftarrow f'_{p,j,0,0} \times f_{v,l,0,1}
转移到f_{p,j,0,1}。讨论p先前的状态。如果之前就被监听了，那v放不放都可以。如果之前没被监听，v需要放监听器。而且无论如何v都需要被监听。故f_{p,j+l,0,1} \leftarrow f'_{p,j,0,0} \times f_{v,l,1,1} + f'_{p,j,0,1} \times (f_{v,l,0,1} + f_{v,l,1,1})
转移到f_{p,j,1,0}。所有v都不能放。但是被不被监听都行。故f_{p,j+l,1,0} \leftarrow f'_{p,j,1,0} \times (f_{v,l,0,0} + f_{v,l,0,1})
转移到f_{p,j,1,1}。讨论p以前的状态。假如p之前就被监听。那v爱咋放咋放。假如p之前没被监听，那v得放，被不被监听无所谓。故f_{p,j+l,1,1} \leftarrow f'_{p,j,1,0} \times (f_{v,l,1,0} + f_{v,l,1,1}) + f'_{p,j,1,1} \times (f_{v,l,0,0} + f_{v,l,0,1} + f_{v,l,1,0} + f_{v,l,1,1})
卡空间，全long long开不下。クソ！
建议单写一个加法函数。并且每次转移的时候把f复制一遍，避免f'被更新
31 P4597
哎这回真是典中典了。
按顺序遍历，将元素放入优先队列。新元素如果比堆顶小，就把堆顶弹出并强行改成当前元素大小。
关于非降：使a_i \leftarrow a_i - i，转成递增。（非常好trick使我码量旋转
32 P4819
缩SCC。发现我们只用查证0入度点即可。
同时，假如我们能找到一个大小为1的SCC满足它所有后继点的前驱不唯一，那我们可以不查证它（其他SCC查证完了它自然就是杀手了）。此时需要查证的点数-1
最后如果我们至少要查证t个点那我们的安全概率就是1 - \frac{t}{n}，即危险点不在这t个中的概率。
33 P4785
贪心，无需多盐。
很容易发现交换成一个二叉树结构。
对于每个位置p，讨论最小值在p，lch_p还是rch_p
若最小值在p，则不交换最优。
若最小值在lch_p，则只能交换一次p和lch_pa_
若最小值在rch_p，则需要考虑p和rch_p的顺序。不妨设a_p \le a_{rch_p}。考虑记忆化搜索p在左子树还是右子树更优（因为最多跳\log层不会有问题）。