题记 1

· · 个人记录

P3778 [APIO2017] 商旅

总结： 01分数规划 + Floyd 判断正环

P3749 [六省联考 2017] 寿司餐厅

总结： 最大权闭合子图

建图思路：

  1. 点权为正： S \rightarrow v，流量为 val
  2. 点权为负： v \rightarrow T，流量为 |val|
  3. 原图中的边流量为 inf
  4. 答案为 sum - flow，sum 为正权点权值之和，flow 为最大流

Igor and Interesting Numbers

总结： 利用 dp 先确定位数再逐位确定每一位上的数字

P3488 [POI2009] LYZ-Ice Skates

总结： 二分图。考虑最劣情况，选择左边连续一段会使右边可匹配的最少。则对任意 l，r 都有 sum_r - sum_{l-1} \le (r + d - l + 1)k，令 a_i' = a_i - k，则有 sum_r' - sum_{l-1}' \le kd。转化为最大子段和判断。

Hall 定理：对一个二分图 G=(V_1,V_2,E)，对 S\subseteq V_1 设 $f(S)

--- [String Set Queries](https://www.luogu.com.cn/problem/CF710F) **总结：** 长度不同的字符串有 $O(\sqrt n)$ 个，可以暴力 Hash 做到 $O(n \sqrt n)$。也可以二进制分组 + ACAM 做（我不会）。 --- [P3435 [POI2006] OKR-Periods of Words](https://www.luogu.com.cn/problem/P3435) **总结：** kmp 中 fail 记录的是最长的 border，那么 $i - fail_i$ 就是最小正周期。那么一直跳 $fail$ 到最小（不为 $0$），得到的就是最长正周期，记忆化优化保证复杂度。 --- [P4126 [AHOI2009] 最小割](https://www.luogu.com.cn/problem/P4126) **总结：** 1. 最小割的可行边：满流，且 $u$ 与 $v$ 不在同一个强连通分量 2. 最小割的必须边：满流，且 $S$ 与 $u$ 在同一强连通分量，$v$ 与 $T$ 同理 注：此处讨论的是残量网络 --- [P4070 [SDOI2016] 生成魔咒](https://www.luogu.com.cn/problem/P4070) **总结：** 对于长为 $n$ 的字符串，本质不同的字串数量为 $\dfrac{n(n+1)}{2}-\sum_{i=1}^{n}height[i]$。本题从后面加入字符，把字符串反过来后相当于多了一个后缀，set 动态维护贡献。新的后缀会贡献 $n-i+1$ 个子串，减去 $Lcp(pre, rk[i])$ 与 $Lcp(rk[i], suc)$，加上重复减去的 $Lcp(pre, suc)$。 --- [P4094 [HEOI2016/TJOI2016] 字符串](https://www.luogu.com.cn/problem/P4094) **总结：** 二分答案，转化为判断后缀 $a,a+1,\dots,b-mid+1$ 与后缀 $c$ 的 lcp 是否大于等于 $mid$。显然只需要找 $rk[a],rk[a+1],\dots,rk[b-mid+1]$ 中小于等于 $rk[c]$ 的最大值和大于 $rk[c]$ 的最小值，并用 st 表查询，即找 $rk[c]$ 的前驱和后继，主席树维护即可。 --- [P4248 [AHOI2013] 差异](https://www.luogu.com.cn/problem/P4248) **总结：** 难点在于求所有后缀的 $\sum_{i=1}^n\sum_{j=1}^m Lcp(T_i,T_j)$。考虑求 lcp 的过程，求的是 $height$ 的区间最小值，用单调栈优化这个过程。 --- [P5309 [Ynoi2011] 初始化](https://www.luogu.com.cn/problem/P5309) **总结：** 根号分治的思想，并用前后缀优化。只是卡常比较恶心，注意取模不要太勤快，同时可以调整块长来优化时间。 --- [Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) **总结：** 长链剖分优化 DP（据说可以优化掉深度那一维 O.o ）。记 $f_{u,i}$ 表示 $u$ 及其子树内深度为 $i$ 的点的数量，易得 $f_{u, i} = \sum f_{v,i-1}$。第二维与深度相关，采用长链剖分暴力把链上的答案合并，并用指针数组（动态空间）做到 时空复杂度都是 $O(n)$。 --- [P5933 [清华集训2012] 串珠子](https://www.luogu.com.cn/problem/P5933) **总结：** 记 $f(S)$ 表示点集 $S$ 的**连通**方案， $g(S)$ 表示点集 $S$ 的**所有边**的方案。显然有**连通方案数=总方案数-不连通方案数**。为不重不漏，转移 $S$ 时随便枚举 $S$ 中的一个固定点 $p$，记包含 $p$ 的点集为 $T$，则 $f(S) = g(S) - \sum f(T) \times g(S -T)$。 ```cpp for (int s = 1; s < (1 << n); s++) { f[s] = g[s]; int k = s ^ (s & -s);//去掉最后一个 1 for (int t = k; t; t = (t - 1) & k) f[s] -= f[t] * g[s ^ t]; } ``` --- [P4292 [WC2010] 重建计划](https://www.luogu.com.cn/problem/P4292) **总结：** 01分数规划（二分），然后转化为求判断长为 $[L,U]$ 的最大链是否大于 $0$。用 $f_{u,i}$ 表示 $u$ 开始往下延伸 $i$ 长的链的最大值，得到 $O(n^2)$ 的朴素 DP。显然可以用长链剖分优化，并使用线段树维护做到 $O(n \log n \log V)$。 将 $f_{u,i}$ 的值记录到 $dfn[u]+i$ 不会冲突（长链剖分序）。 --- [P2150 [NOI2015] 寿司晚宴](https://www.luogu.com.cn/problem/P2150) **总结：** 可以把质数进行状压 DP。对于一个数 $n$，最多有一个大于 $\sqrt n$ 的质数，单独讨论它会在哪个集合，最后对答案去重。记得有相同大质数的一段一段考虑，再加上滚动数组优化。 --- [You Are Given a Tree](https://www.luogu.com.cn/problem/CF1039D) **总结：** 对于一个给定 $k$，可以 $O(n)$ 求出答案，朴素是 $O(n^2)$ 的。考虑根号分治。设定阈值 $B$，对于 $k \le B$ 的可以直接求，这部分是 $O(nB)$ 的；对于 $k > B$，答案小于 $\dfrac{n}{B}$，用二分求出一段答案一样的连续区间，这部分是 $(\dfrac{n^2 \log n}{B})$ 的。当 $B$ 取 $\sqrt{n \log n}$ 时间最优。代码卡常：将树拍成出栈序（非递归）；记忆化； --- [P3674 小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674) **总结：** 用 bitset + 莫队维护区间内出现的数。$f$ 维护 $x$，$g$ 维护 $N - x$。减法：$a-b=x$， $f$ 直接与 $f << x$ 做与运算；加法：$a+b=x \rightarrow a-b=x-N$，$f$ 直接与 $g >> (N - x)$ 做与运算；乘法：暴力枚举质因数 $O(\sqrt n)$。 --- [P5355 [Ynoi2017] 由乃的玉米田](https://www.luogu.com.cn/problem/P5355) **总结：** 用 bitset + 莫队维护区间内出现的数。加减乘不用说。除法考虑根号分治：$x \ge \sqrt n$，除数最大是 $\sqrt n$，暴力枚举做是 $O(\sqrt n)$ 的；$x < \sqrt n$，对于每一个 $x$ 单独考虑，维护 $pre_i$ 表示 $[l,i]$ 中存在 $\dfrac{a}{b}=x$ 的最大的 $l$，最后询问时判断一下 $l \le pre_r$ 即可。莫队 $O(n \sqrt n)$，根号分治 $O(n \sqrt n)$，再加个 bitset，是可以过的。 --- [P4074 [WC2013] 糖果公园](https://www.luogu.com.cn/problem/P4074) **总结：** 树上带修莫队。对于树上部分： 1. 记下点 $u$ 入栈和出栈的顺序 $st_u$ 和 $ed_u$。 2. 对于两点 $u, v \ (st_u>st_v)$。若 $lca(u,v)=u$，则转化为询问区间 $[st_u,st_v]$；反之，询问区间 $[ed_u,st_v]$ 和点 $lca(u,v)$。 对于修改：转化为修改 $st_u$ 和 $ed_u$。如果两个同时（不）在询问区间中，对答案无影响，跳过；反之单点修改。 --- [P8955 「VUSC」Card Tricks](https://www.luogu.com.cn/problem/P8955) **总结：** 首先观察到答案可以二分，想到整体二分。但是每次不好撤回修改。考虑到每次整体二分会使答案区间减小一半，每次对答案区间排序之后扫一遍并用线段树维护即可。 区间或卡常 trick：如果或上一个值之后区间的与没有变化，可以直接不管了。 --- [[AGC001E] BBQ Hard](https://www.luogu.com.cn/problem/AT_agc001_e) **总结：** 转化为求 $\sum_{1\le i,j \le n} \binom{a_i+a_j+b_i+b_j}{a_i+a_j}$ 然后再去重。首先有 $O(n^2)$ 暴力。考虑组合数组合意义：$\binom{x+y}{x}$ 即为 $(0,0)$ 每次只向上和向右走，走到 $(x,y)$ 的路径数。于是题目转化为从 $(-a_j,-b_j)$ 走到 $(a_i,b_i)$，直接 $O(V^2)$ 的 DP 即可。 --- [P1450 [HAOI2008] 硬币购物](https://www.luogu.com.cn/problem/P1450) **总结：** 每次做多重背包会超时。转化为完全背包+容斥。 **背包求方案数（01）：** 注意到如果当前物品体积为 $0$ 要跳过。 ```cpp f[0] = 1; for (int i = 1; i <= n; i++) for (int j = m; j >= v[i]; j--) if (v[i]) f[j] += f[j - v[i]]; ``` **可撤销背包：** 将物品加入背包对体积枚举的循环倒过来：(01) ```cpp f[0] = 1; for (int i = 1; i <= n; i++) for (int j = v[i]; j <= m; j++) if (v[i]) f[j] -= f[j - v[i]]; ``` --- 题意：给定 $n \times m$ 个字符串，求 $\sum_{i=1}^{n} \sum_{j=1}^{n} \max_{k=1}^{m}LCP(s_{i,k},s_{j,k})$。 **总结：** 考虑到 $\sum_{i=1}^{n} \sum_{j=1}^{n} \min_{k=1}^{m}LCP(s_{i,k},s_{j,k})$ 是好求的。将 $m$ 个字符串拆开再逐位拼接，放到字典树上，最后对答案的贡献（LCA 的深度）要除以 $m$。然后 $\min$ - $\max$ 容斥一下即可。 $\min$ - $\max$ 容斥： $$\max S = \sum_{T \subseteq S} (-1)^{|T|-1} \min T$$ $$\min S = \sum_{T \subseteq S} (-1)^{|T|-1} \max T$$ --- [P9619 生成树](https://www.luogu.com.cn/problem/P9619) **总结：** 完全图 $G_n$ 有 $n^{n-2}$ 个生成树，每一条边出现的次数为： $$\dfrac{n^{n-2} \times (n-1)}{\dfrac{n \times (n-1)}{2}} = 2 \times n ^ {n - 3}$$ --- [P4381 [IOI2008] Island](https://www.luogu.com.cn/problem/P4381) **总结：** 求基环树森林的最大直径之和。对于一颗基环树来说，直径就是**非环子树直径**和**环上两点间距离及两点最长链的和**，两者的最大值。预处理好信息后可以用单调队列优化。 找环：（画图理解怎么找环） ```cpp void find_cir(int u) { dfn[u] = ++tsp; for (int i = h[u]; ~i; i = ne[i]) { int v = e[i]; if (v == fa[u]) continue; if (dfn[v]) { if (dfn[v] < dfn[u]) continue; for (int x = v; x != fa[u]; x = fa[x]) tmp[++cnt] = x; } else fa[v] = u, find_cir(v); } } ``` --- [Optimal Partition](https://www.luogu.com.cn/problem/CF1667B) / [P7302 [NOI1998] 免费的馅饼](https://www.luogu.com.cn/problem/P7302) **总结：** 依据某些条件才能转移的 DP，并且状态数已经无法优化时，考虑根据条件讨论，采取一些数据结构优化，达到降低复杂度的目的。有时候可以根据条件排序，可以少枚举一个条件，另一些条件用树状数组维护。 --- [The Bakery](https://www.luogu.com.cn/problem/CF833B) / [P2605 [ZJOI2010] 基站选址](https://www.luogu.com.cn/problem/P2605) **总结：** 有些时候可以考虑拆开 DP 转移时的一些贡献，将这部分贡献用数据结构维护，优化时间复杂度。举例来说，有些情况下考虑到当前节点，它对应的会对一个区间有影响，这可以使用线段树维护。（这两道题有一些共通之处：设计完 DP 状态后发现贡献部分相当难处理，于是转换思维，考虑当前点/当前村庄的影响，相当巧妙） --- [Power Tree](https://www.luogu.com.cn/problem/CF1120D) **总结：** 修改子树节点/修改子树里面的叶节点可以转换为 dfs 序来做，同时可以用差分的思想。 生成树的可行边：应当把相同权值的边一起考虑。 --- [Steps to One](https://www.luogu.com.cn/problem/CF1139D) **总结：** 非常好题目，爱来自期望。有时候期望回到定义来推导会有奇效。 遇到 $\gcd$ 时试着想想莫反。额外赠送[莫比乌斯反演套餐](https://www.luogu.com.cn/blog/482965/qian-xue-mu-bi-wu-si-fan-yan)。 无穷递缩等比数列（公比小于 $1$）： $$s=x+x^2+x^3+\dots$$ $$sx=x^2+x^3+\dots$$ $$s-sx=x$$ $$s=\dfrac{x}{1-x}$$ --- [Till I Collapse](https://www.luogu.com.cn/problem/CF786C) **总结：** 发现如果给定 $k$，我们可以 $O(n)$ 暴力求解。怎么有点眼熟？运用根号分治的思想，对于 $k \le B$，暴力求解；对于 $k > B$，答案小于 $\dfrac{n}{B}$，二分出答案一样的区间。容易发现 $B$ 取 $\sqrt {n \log n}$ 最优。 --- [P3734 [HAOI2017] 方案数](https://www.luogu.com.cn/problem/P3734) / [Grid 2](https://www.luogu.com.cn/problem/AT_dp_y) **总结：** 对于到一点方案数的 DP 非常好求。将所有障碍点以及终点排序，并将 DP 重新设计成到达该点且不经过其他障碍点的方案数，容斥即可。 --- [P4067 [SDOI2016] 储能表](https://www.luogu.com.cn/problem/P4067) **总结：** 转化为异或值大于等于 $k$ 的异或和减去 $k$ 乘以异或值大于等于 $k$ 的对数。就是一个上界为 $n-1$，上界为 $m-1$，下界为 $k$ 的数位 DP。由于要记录值和对数，记搜返回 ```pair``` 即可。 --- [P1989 无向图三元环计数](https://www.luogu.com.cn/problem/P1989) **总结：** 将度数大的点向度数小的点连边，若度数相同，则编号小的点向编号大的点连边，使图变成一个有向无环图。先对 $(u,v)$ 标记所有的 $v$，然后枚举 $(u,v)$ 和 $(v, w)$，若 $w$ 被标记，则 $(u,v,w)$ 是一个三元环，最后撤销标记。这样子不重不漏，时间复杂度 $O(m\sqrt m)$。 --- [P4036 [JSOI2008] 火星人](https://www.luogu.com.cn/problem/P4036) / [Kefa and Watch](https://www.luogu.com.cn/problem/CF580E) **总结：** 用平衡树动态维护当前字符串的 Hash 值。/线段树维护 Hash 值，询问将左右两区间合并的时候要稍微注意。 --- [P3538 [POI2012] OKR-A Horrible Poem](https://www.luogu.com.cn/problem/P3538) **总结：** 1. 一个数的质因数个数大概有 $\log_2 n$ 个。 2. 一个串的循环节一定是串长度的约数，求最小循环节只需要枚举长度的质因数看是否需要除掉。 3. $k$ 是串 $s[l,r]$ 的循环节，当且仅当 $s[l+k,r]=s[l,r-k]$。 --- [P3167 [CQOI2014] 通配符匹配](https://www.luogu.com.cn/problem/P3167) **总结：** 字符串中有特殊符号时，看能否将其分段再考虑。本题中将通配符左右分开，再用 DP 考虑。 --- [P2714 四元组统计](https://www.luogu.com.cn/problem/P2714) **总结：** 正难则反。运用容斥，答案为 $\gcd$ 为 $i$ 的倍数的对数减去 $\gcd$ 为 $2i,3i,\dots,ki$ 的对数。 --- [P4318 完全平方数](https://www.luogu.com.cn/problem/P4318) **总结：** 有时候可以注意容斥系数与莫比乌斯函数的关系，这往往和特殊题意相关联。 --- [P3702 [SDOI2017] 序列计数](https://www.luogu.com.cn/problem/P3702) **总结：** 有时候对题意进行转化会更好着手，例如简单容斥一下。先从暴力 DP 入手，然后再去往优化的方向想。 --- [P5503 [JSOI2016] 灯塔](https://www.luogu.com.cn/problem/P5503) **总结：** 题目中带有根号的，可以想到 $\sqrt n$ 的取值范围可能比较小，枚举其取值可能会有解法。 --- [P3888 [GDOI2014] 拯救莫莉斯](https://www.luogu.com.cn/problem/P3888) **总结：** 题目特殊的数据范围往往有提示性。为了满足 DP 的无后效性，有时候会在 DP 状态中多记录一些信息。 --- [P5502 [JSOI2015] 最大公约数](https://www.luogu.com.cn/problem/P5502) **总结：** 区间公约数具有可合并性。如果区间左端点固定，那么区间 $\gcd$ 的取值只有 $\log_2V$ 种，因为区间右端点每扩展一个数，加入一个数后 $\gcd$ 要么不变要么变为原来的 $\dfrac{1}{2}$。用类似数论分块的做法再加上每次二分找右端点，即可做到 $O(n \log n \log V)$。 --- [P2290 [HNOI2004] 树的计数](https://www.luogu.com.cn/problem/P2290) **总结：** $prufer$ 序列的强大之处，建立序列与无根树之间的双射。 性质：度数为 $d_i$ 的点会在 $prufer$ 序列中出现 $d_i-1$ 次。所以对于给定度数 $d_{1 \sim n}$ 的无根树有 $\dfrac{(n-2)!}{\prod_{i=1}^{n}(d_i-1)!}$ 种。 --- [P7521 [省选联考 2021 B 卷] 取模](https://www.luogu.com.cn/problem/P7521) **总结：** 看似简单的优化有可能就让时间复杂度正确了。 --- [P9745 「KDOI-06-S」树上异或](https://www.luogu.com.cn/problem/P9745) **总结：** 树形 DP，但是重点是二进制拆位。利用 $u$ 所在连通块的特殊性质，枚举 $(u,v)$ 边断或者不断计算贡献。 --- [P8819 [CSP-S 2022] 星战](https://www.luogu.com.cn/problem/P8819) **总结：** 题目要求维护所有点的出度。每个点作为一条边的起点只出现一次即有解，用**和哈希**可以大概率保证有解；也因为出度均为 $1$ 的特殊性质，只要所有点出度均为奇数即有解，也可以**异或哈希**维护。