做题记录 - 2021.12

由于 NOIP 已经考完爆炸了，所以开个新坑。 [前传](https://djwj233.blog.luogu.org/noip2021-record) - [CF1228E Another Filling the Grid](https://www.luogu.com.cn/problem/CF1228E) 发现 $n$ 是 $250$，显然是一个 $\mathcal O(n^3)$ 左右的 DP。 记 $dp_{i,j}$ 为前 $i$ 行填满（且均合法），已经有 $j$ 列最小值为 $1$ 的方案数，易知 $dp_{0,0}=1$。 利用容斥，有递推式：心情没有不好，照样可以贴贴 $$ dp_{i,j} = (k-1)^{n-j}\times (k^j-(k-1)^j) \times dp_{i-1,j} + \sum_{t=1}^j \binom{t}{n-j+t}\times k^{j-t}\times(k-1)^{n-j}\times dp_{i-1,j-t} $$ 阶乘需要预处理才能过。[Code](https://www.luogu.com.cn/record/64127171) - [CF1599A Weights](https://www.luogu.com.cn/problem/CF1599A) 不会，看了题解。 题解是一个**从终点状态倒推**的思路，考虑每次从当前状态删去一颗砝码。[Code](https://www.luogu.com.cn/record/64143603) - [AT2382 [AGC015D] A or...or B Problem](https://www.luogu.com.cn/problem/AT2382) 从最高位入手。我们尝试找出一个 $t$，使 $A<2^t\le B$。 1. 如果找不出，那么就是 $[A,B]$ 中每个数一定包含最高位，或起来也一定包含最高位，也就是说我们不用考虑最高位了。 我们找一个 $t$ 使 $2^t\le B< 2^{t+1}$，那么问题就转化成 $[A-2^t,B-2^t]$ 的一个子问题。 2. 否则，我们把 $[A,B]$ 拆成 $[A,2^t-1]$ 和 $[2^t,B]$ 两段。 - 如果最后的或和中不包含 $t$ 这一位，那么就是只含 $[A,2^t-1]$，容易发现最后答案就是 $[A,2^t-1]$ 中的每个数； - 否则，我们用 $[A,2^t-1]$ 中每个数和 $2^t$ 或能够得到 $[A+2^t,2^{t+1}-1]$ 中所有的数，而且 $[A,2^t-1]$ 中的数和 $[2^t,B]$ 中的数或无法得到别的数。 如果或中只出现了 $[2^t,B]$ 中的数，那么设 $B-2^t$ 的最高位为 $x$，所有可能出现的数就是 $[2^t, 2^t+2^{x+1}-1]$ 中的所有数。 （这里注意特判 $B=2^t$ 的情况） 这样分治下去就可以了。复杂度 $\mathcal O(\log^2n)$，实现得好一点可以 $\mathcal O(\log n)$。[Code](https://www.luogu.com.cn/record/64235239) - [P3177 [HAOI2015]树上染色](https://www.luogu.com.cn/problem/P3177) 显然是一个 $\mathcal O(n^2)$ 的 DP。[Code](https://www.luogu.com.cn/record/64725223) 为什么能过呢？事实上，下面这样的复杂度是 $\mathcal O(nk)$ 的。 ```c++ fo(x,1,n) fo(y:son[x]) fo(i,0,min(k,siz[x])) fo(j,0,min(k-i,siz[y])) ... siz[x] += siz[y] ``` 这样是 $\mathcal O(n^2)$ 的： ```c++ fo(x,1,n) fo(y:son[x]) fo(i,0,siz[x]) fo(j,0,siz[y]) ... siz[x] += siz[y] ``` 在这题里都能过。 - [CF1497E2 Square-free division (hard version)](https://www.luogu.com.cn/problem/CF1497E2) 先抠掉所有数的平方因子，转化成区间内不能有一组相等。然后发现改动可以改成一个巨大无比的数，就相当于删去。 观察数据范围，正解显然是什么 $\Omega(nk)$ 的做法，否则 $k$ 会开很大。考虑 DP，我们设 $dp(i,j)$ 为 DP 到 $i$ 为一段，已经花了 $j$ 次改动的最小段数。 我们发现，一段内要的改动次数就是区间长度减去本质不同的数的个数，这可以用数颜色的套路维护。 枚举 $i$ 并维护这个树状数组，再枚举 $j$ 和当前这个段的改动次数 $z$，Binary Search 出一个最小的 $t$ 使 $i-t+1 -num(i,t)\le z$，更新 $dp(i,j)$。 注意到这样是 $\mathcal O(nk^2\log^2n)$ 的，根本跑不过去。但是实际上不用每次都二分，可以统一二分一遍，这样复杂度是 $\mathcal O(nk^2+nk\log^2n)$，还是过不去。 考虑压掉一只 $\log$，我们发现对于同一个 $z$，这个东西是单调不降的，所以可以用 two pointers 维护，这样就是 $\mathcal O(n\sqrt{a_i}+nk^2+nk\log n)$ 了。 [Code](https://www.luogu.com.cn/record/65043642) - [P4602 [CTSC2018]混合果汁](https://www.luogu.com.cn/problem/P4602) 看到最大值最小果断二分，又因为有多次询问，考虑整体二分。 [Code](https://www.luogu.com.cn/record/65094412) - [CF85E Guard Towers](https://www.luogu.com.cn/problem/CF85E) 考虑二分一个答案，然后建出图，把所有曼哈顿距离大于当前枚举答案的点对连上边，然后判断它是不是二分图。 这样可以在 $\mathcal O(n^2\log X)$ 的时间内求出第一问的答案，考虑怎么做第二问。 我们发现，这个问题的本质就是给一张二分图，询问有几种划分左右部的方案。 由于同一个连通块内最多只有两种染色方案，而且块与块之间独立，所以答案就是 $2^{\text{连通块个数}}$。 [Code](https://www.luogu.com.cn/record/65138166) - [P7943 [D2] CONsecutive and CONcat (hard version)](https://www.luogu.com.cn/problem/P7943) 由于不会直接 DP，所以考虑算每个起点位置的贡献。 注意到给定所有字符串的 $m$ 相等且不大，我们猜想出题人可能再提醒我们从每个 $k$ - CON string 的长度入手。 先考虑 $k\le m$ 怎么做。我们发现，实际上答案就是块内的贡献。 之后大于 $m$ 的肯定要用到几个只有一种字母的串，接着算即可。[Code](https://www.luogu.com.cn/record/65194730) - [P4891 序列](https://www.luogu.com.cn/problem/P4891) 太长时间没做过正统的 DS 题，过来写道。 看到有 $\max\limits_{j=1}^i A_j$ 这种东西出现，考虑兔队线段树。发现是假的，于是咕了。 - [ABC191F](https://atcoder.jp/contests/abc191/tasks/abc191_f) 观察操作的本质，我们发现这一系列操作等价于在数列中求一些数的 $\gcd$（必须小于剩下数的最小值），然后把别的数搞掉。 由于答案一定是某个数的一个因子。我们考虑枚举每个因子，然后判断它能不能得到。 怎么判断呢？我们发现，剩下的数中每个数都得是这个因子的倍数，而且把它们全选上一定是最优的。[Code](https://atcoder.jp/contests/abc191/submissions/27960593) 复杂度好像是 $\mathcal O(n^2d(A_i))\sim \mathcal O(n^{\frac{7}{3}})$？不会咕更紧的界 qwq 题解里面好像直接用 `map` 搞到了 $\mathcal O(n^{\frac{4}{3}}\log A_i)$，大受震撼。 - [AGC050A](https://atcoder.jp/contests/agc050/tasks/agc050_a) 更高更妙的构造题。我们发现这个 $10$ 就是 $\log n$，考虑建成一棵二叉树。 实际上，每个点都可以作为根，在 $\bmod n$ 下是同构的。那么这题就做完了。[Code]() 大概考察了转化与同构思想？不太懂。[Code](https://atcoder.jp/contests/agc050/submissions/27962903) - [CF1389F Bicolored Segments](https://www.luogu.com.cn/problem/CF1389F) 区间类最优化问题还是要考虑 DP，那么这个题必然是线段树优化 DP 了。 如果设两位状态就没法维护，因此我们钦定每次转移只能从另一种颜色转移过来，就可以维护了。 - [CF1389E Calendar Ambiguity](https://www.luogu.com.cn/problem/CF1389E) 则必定有： $$ d(x-1)+y\equiv d(y-1)+x\pmod{w} $$ 整理可得： $$ w\mid (d-1)(y-x) $$ 其中 $1\le x<y\le\min\{m, d\}$，令 $n=\min\{m, d\}$。 由于 $d-1$ 和 $w$ 是固定的，因此我们找出 $t=\gcd(w,d-1)$，转化为： $$ \dfrac{w}{t}\mid y-x $$ 因此我们枚举 $k=y-x=i\times\dfrac{w}{t}$，那么对应的方案就是 $n-k$，所以答案为： $$ \sum_{i=1}^{\frac{nt}{w}}n-i\times\dfrac{w}{t}=\dfrac{nt}{w}\times n-\dfrac{w}{t}\times \dfrac{\frac{nt}{w} \times(\frac{nt}{w} + 1)}{2} $$ [Code](https://www.luogu.com.cn/record/65263288) - [CF593E Strange Calculation and Cats](https://www.luogu.com.cn/problem/CF593E) 矩阵乘法，直接写即可。[Code](https://www.luogu.com.cn/record/65313628) - [CF1483F Exam](https://www.luogu.com.cn/problem/CF1483F) 头铁！！硬刚！！！不会！！！！贺！！！！！[Code](https://www.luogu.com.cn/record/65462279) - [AGC032A](https://atcoder.jp/contests/agc032/tasks/agc032_a) 每次从右向左扫到第一个合法的加入位置，再贪心地加入，易证这是对的。 直接 $\mathcal O(n^2)$ 地构造。 - [ABC232G](https://atcoder.jp/contests/abc232/tasks/abc232_g) 一个有点 nb 的模型转化。刚开始想的是拿一个线段树维护，但是非常不行。 由于边权是 $A+B\bmod M$，而且**加与最短路之间难以转换**，考虑转化成 $B - (M-A)\bmod M$，这样就变成了两点间的距离。 考虑构造一个环，贺一张题解里的图：  这样把不用的点缩掉，就变成 $\mathcal O(n)$ 的了。 - [CF1088E Ehab and a component choosing problem](https://www.luogu.com.cn/problem/CF1088E) 容易发现一定存在一种 $k=1$ 取到最大值，然后 DP 即可。 - [CF1217E Sum Queries?](https://www.luogu.com.cn/problem/CF1217E) 猜想最后答案序列的长度恰为 $2$，用线段树对每个十进制位维护最小值、次小值即可。[Code](https://codeforces.com/contest/1217/submission/140237649) - [CF28C Bath Queue](https://www.luogu.com.cn/problem/CF28C) 注意到数据范围小得可怜，所以我们猜测正解是高维 DP。 设 $dp_{i,j,k}$ 为考虑前 $i$ 个房间住了 $j$ 个学生，目前最长队伍为 $k$ 的方案数，那么 $dp_{0,0,0}=1$，有转移： $$ dp_{i,j,k} = \sum_{t=0}^{a_i\times (k-1)}\binom{t}{n-j+t}dp_{i-1,j-t,k} +\sum_{t=a_i\times (k-1)+1}^{a_i\times k}\binom{t}{n-j+t}\sum_{z\le k} dp_{i-1,j-t,z} $$ 其中 $\sum_{z\le k} dp_{i-1,j-t,z}$ 可以在转移时预处理，这样总复杂度是 $\mathcal O(n^4)$ 的。 注意方案数可能很大，所以要用 `double` 存。`double` 在溢出时会自动舍弃低位，恰好符合我们的需求。[Code](https://www.luogu.com.cn/record/65596776) - [CF1264C Beautiful Mirrors with queries](https://www.luogu.com.cn/problem/CF1264C) （以下的 $p_i$ 均指 $\dfrac{p_i}{100}$）。 1. 先考虑不包含修改的弱化版。如果只有 $1$ 号结点一个检查点，那么设答案为 $x$，有： $$ x=\sum_{i=1}^n\left(\prod_{j=1}^{i-1}p_j\times (1-p_i)\times (x+i)\right)+\prod_{j=1}^{n}p_j\times n $$ $$ \prod_{j=1}^{n}p_j\times x=1+\sum_{i=1}^{n-1}\prod_{j=1}^ip_j $$ $$ x=\dfrac{1+\sum_{i=1}^{n-1}\prod_{j=1}^ip_j}{\prod_{j=1}^{n}p_j} $$ 这样答案就被我们化到只剩下 $p_i$ 的前缀积求和的形式。 2. 如果不只一个检查点呢？我们发现，如果问到了后一个检查点，那么就相当于从后一个检查点开始问，这等价于成功。 这样我们只要求出相邻两个检查点之间的距离，然后把全部值加起来。 其中，对区间 $[l, r]$，答案为： $$ x=\dfrac{1+\sum_{i=l}^{r-1}\prod_{j=l}^ip_j}{\prod_{j=l}^{r}p_j} $$ 3. 如果包含修改呢？可以发现，这个操作把一段区间拆成两段或合并两段区间。 先预处理我们需要的东西，每次操作时我们都直接计算此段区间内的答案，更新即可。 用类似于珂朵莉树的一个 `set` 维护，复杂度 $\mathcal O(n\log n)$。[Code](https://www.luogu.com.cn/record/65634804) - [CF725E Too Much Money](https://www.luogu.com.cn/problem/CF725E) 枚举这个数，然后暴力跳。可以发现这样次数至多 $\mathcal O(\sqrt{n})$ 次，所以复杂度是对的。[Code](https://www.luogu.com.cn/record/65675362) --- 打算补一场印尼 OI。 - [P7969 [KSN2021] Self Defence](https://www.luogu.com.cn/problem/P7969) 设 $dp(i,j,s=0/1)$ 为 DP 到第 $i$ 个位置，当前已经有 $j$ 的权值，末尾为 $s$ 且这是最长的连续段的数量。有：（忽略一些特判的细节） $$ dp(i,j,s) = \sum_{k=1}^{M-1}dp_{i-k,j,1-s}+\sum_{k=M}^{lim}dp_{i-k,j-(k-M+1),1-s} $$ 这个转移是 $\mathcal O(n^3)$ 的，跑不过去，考虑优化。实际上，这个转移可以很 Hard 地用前缀和优化。[Code](https://www.luogu.com.cn/record/65653423) - [P7970 [KSN2021] Binary Sea](https://www.luogu.com.cn/problem/P7970) $(i,j)$ 是黑格当且仅当 $i,j$ 的二进制位中没有重复的。根据套路，猜一手复杂度为 $\mathcal O(q\log n)$。 咕咕咕。 - [P7971 [KSN2021] Colouring Balls](https://www.luogu.com.cn/problem/P7971) 这屎题是在强迫我们数据点分治...... - [#2330. 「清华集训 2017」榕树之心](https://loj.ac/p/2330) 先考虑部分分。如果只要求 $1$ 号点，那么就是贪心地平衡最大子树的贡献。 怎么平衡呢？可以考虑 DP。记 $dp_x$ 为只考虑 $x$ 子树内的点，最少能剩下几个点。那么： $$ dp_x=\begin{cases} siz_x \bmod 2 & siz_{x}-siz_{son(x)}-2 \ge dp_{son(x)} \\ dp_{son(x)}-(siz_{x}-siz_{son(x)}-2)& \text{otherwise} \end{cases} $$ 这样根节点可行当且仅当 $dp_{rt}=0$，即 $siz_{rt}\bmod 2 = 1\land\forall y \in son(rt), siz_x-2\ge siz_{y}+dp_y$。 那么由于最后的位移一定是从根节点到当前结点，所以我们记录当前向祖先的 $\max_{siz_y+dp_y}$，看看能否平衡即可。 实际上这个东西等价于将 $1\to x$ 的路径缩成一个根节点。[Code](https://loj.ac/s/1331728) 其实直接贪也能搞（？）只是很屎，这启示我们**如果有复杂的贪心考虑搞成递推 / DP**，想法写在纸上会更好。 - [CF1623E Middle Duplication](https://www.luogu.com.cn/problem/CF1623E) 主要做法就是贪心地从前往后考虑每个字母是否应该被复制，然后搜这棵树。 - [CF442C Artem and Array ](https://www.luogu.com.cn/problem/CF442C) 略推一推可以得到一个结论：如果当前相邻三个出现了 $x>y<z$ 的情况，那么三个数中，先删去 $y$ 一定是更优的。 又因为删去 $y$ 不影响别的数，那么我们可以直接把 $y$ 删去。这样我们从左往右扫一遍，维护这样的操作。 容易发现，扫完后会出现一个先上升后下降的阶梯状的数列，这样我们不断取出最优的删去即可。 当你写完交上去发现过不去，然后发现一大堆傻逼细节要处理。 不过有一种非常简单的处理方式是直接取数列中最小的 $len-2$ 个数。 最后要注意的是维护单调栈时必须保证严格，否则会挂： ``` 6 1 3 3 2 2 4 ``` 这样栈就不单调了。 - [CF1186E Vus the Cossack and a Field](https://www.luogu.com.cn/problem/CF1186E) 显然把这个东西看成前缀和相减的形式，然后就不会了。 题解里面是一个结论：反转和不反转和为总数的一半。[Code](https://www.luogu.com.cn/record/66189328) - [CF1452E Two Editorials](https://www.luogu.com.cn/problem/CF1452E) 复杂度明显应该是 $\mathcal O(n^2)$。**不要轻易转数据结构，可以考虑继续发掘性质。** 我们发现一个段被左边的点选上，当且仅当这个段的中点离左边段的中点更近。因此我们考虑枚举**左边段和右边段各自的中点然后处理**。 [Code](https://www.luogu.com.cn/record/66231106) - [CF1375E Inversion SwapSort](https://www.luogu.com.cn/problem/CF1375E) 手摸几组小样例可以得到一个做法：从前往后扫一遍每个数，把从它出去的所有逆序对按照**终点数从大到小排序**，然后依次操作。 事实上这一定是对的，因为这样交换不会改变后面的数的相对顺序。相同的数可以赋个编号解决。[Code](https://www.luogu.com.cn/record/66273107) - [CF713C Sonya and Problem Wihtout a Legend](https://www.luogu.com.cn/problem/CF713C) 发现严格递增非常难受，于是我们把第 $i$ 个位置的数减去 $i$，这样问题转化为求非严格递增了。 有一个经典结论：最后数列中出现的数一定是原来数列里有的数，否则把它靠到一侧一定更优。 直接 $\mathcal O(n^2)$ DP 即可。[Code](https://www.luogu.com.cn/record/66277672) - [CF839D Winter is here](https://www.luogu.com.cn/problem/CF839D) 考虑枚举 $\gcd$ 为 $x$，如果数列中有 $y$ 个数能被 $x$ 整除，则贡献为 $y\times 2^{y-1}\times x$。 但是我们发现这样会重复计算一部分贡献，那么我们容斥一下。[Code](https://www.luogu.com.cn/record/66279175) - [P4768 [NOI2018] 归程](https://www.luogu.com.cn/problem/P4768) 问题本质上就是求 $v$ 所在的一个无水的连通块内的所有点到 $1$ 号点的最短路。 这样就有了一个离线水位线利用并查集的做法，考虑正解。 我们注意到加边时有一些边其实是无用的，在它加进来之前两个端点已经一定连通了，因此我们可以在跑完最短路后把图简化成一棵**最大生成树**。 但是这样还是不好搞，我们考虑将每次合并两个集合的过程呈现在一棵二叉树上，然后在树上倍增。 实际上这种做法的本质是**离线的操作是单向的、只有合并操作的**，我们相当于记录了这个离线的过程。[Code](https://www.luogu.com.cn/record/66372826) - [CF1209E2 Rotate Columns (hard version)](https://www.luogu.com.cn/problem/CF1209E2) 直接 $\mathcal O(n^22^nm)$ 跑不过去，但是可以把那个 $m$ 剪成 $n$。[Code](https://www.luogu.com.cn/record/66391187) - [P2566 [SCOI2009]围豆豆](https://www.luogu.com.cn/problem/P2566) 有一个结论是：一段路径包含了某个点，当且仅当这个点向一个方向作一条射线后与路径有奇数个交点。 司马出题人！！！！！ 这题必须判断的是计数只能规定一个方向，如果从那里来或者到那里去才算次数。[Code](https://www.luogu.com.cn/record/66395308) - [CF798D Mike and distribution](https://www.luogu.com.cn/problem/CF798D) 画出 $n=3$ 的情况，大致就能猜出结论是一半选 A 中最大值，一半选 B 中最大值。 但这是假的，贺题解去了。[Code](https://www.luogu.com.cn/record/66403956) 题解就是好呀，一发就过 - [CF749E Inversions After Shuffle](https://www.luogu.com.cn/problem/CF749E) 设当前选了 $[l,r]$，那么总逆序对包含原来 $[1,n]$ 中的（记为 $Sum$）减去 $[l,r]$ 内部的（记为 $cnt(l,r)$），这些都是固定的。 不固定的是 $[l,r]$ 内部的逆序对数，但好在由于是排列所以任意长度为 $k$ 的区间答案都是固定的。有递推式： $$ S_n=S_{n-1}\times n+\sum_{k=0}^{n-1}k\times(n-1)!=nS_{n-1}+\dfrac{(n-1)n!}{2} $$ 算算贡献可以得到： $$ S_n=\sum_{k=1}^n\dfrac{k-1}{2}\times n!=\dfrac{n(n-1)}{4}\times n! $$ 那么答案就是： $$ \dfrac{2}{n(n+1)}\sum_{l=1}^n\sum_{r=1}^n\left(\dfrac{S_{r-l+1}}{(r-l+1)!}+Sum-cnt(l,r)\right) $$ $$ \dfrac{2}{n(n+1)}\sum_{l=1}^n\sum_{r=1}^n\left(\dfrac{(r-l)(r-l+1)}{4}+Sum-cnt(l,r)\right) $$ 把两部分拆开算再乘上一个 $\dfrac{2}{n(n+1)}$，前一部分答案为： $$ \sum_{k=1}^n(n-k+1)\times\dfrac{k\times (k-1)}{4} $$ 可以 $\mathcal O(n)$ 算。后一部分为： $$ Sum\times \dfrac{n(n+1)}{2}-\sum_{l=1}^n\sum_{r=1}^n cnt(l,r) $$ 后面那个东西就是： $$ \sum_{l=1}^n\sum_{r=l+1}^n[a_l > a_r]\times l\times(n-r+1) $$ 这就可以树状数组维护了。[Code](https://www.luogu.com.cn/record/66409543) - [P2619 [国家集训队]Tree I](https://www.luogu.com.cn/problem/P2619) 学学 WQS 二分。WQS 二分大致就是有一个**凸函数**，满足**难以单点求值**但是**可以求最值**，问题要你单点求值。 那么我们可以二分一个斜率然后找到切点，比较这个点和目标点的关系然后调整斜率。 这个切点就是构造一个函数 $f(x)=g(x)-kx$，然后找它的最值。 这个题里可以直接在白边的边权中减去。要注意的是，我们要优先选择白边来避免相邻两个差大于 $2$。[Code](https://www.luogu.com.cn/record/66424289) - [P4383 [八省联考 2018] 林克卡特树](https://www.luogu.com.cn/problem/P4383) > 简要题意：在树上选取 $k+1$ 条点不相交的链，使得选取的边权和最大。 WQS 二分主要用于解决带**有限制个数**的问题，比如这个。 一般碰到这种题可能会先搞出一个平方级别的 DP，然后被迷惑了。这时候可以考虑 WQS 二分。 1. 如何解决无限制的问题？ 这其实就是那道没有上司的舞会。 2. 如何加权？ 可以直接在加链的时候加上。 3. 如何处理斜率切不到的问题？ 权相同时优先选加链、返回时直接找**第一个大于它的整数斜率及其所对应的截矩**返回 $k+1$ 处的点值。 这个做法的原理是：由于所有运算都是整数，所以这里一定是有一个平台。[Code](https://www.luogu.com.cn/record/66471336) - [P4767 [IOI2000]邮局](https://www.luogu.com.cn/problem/P4767) 这个东西有一个显然的 DP，是 $\mathcal O(V^3P)$ 的。前缀和一下可以做到 $\mathcal O(V^2P)$，但是还是过不去。 据说写出式子可以四边形不等式优化，咕了。 有一种解法是 WQS 二分优化 DP，感觉非常扯淡。核心思路就是**通过赋权消除个数限制**。 - [CF739E Gosha is hunting](https://www.luogu.com.cn/problem/CF739E) 首先这个 DP 函数的凸性是显然的，然后就可以 WQS 二分了。 考虑一个 $\mathcal O(n^3)$ 的 DP，记 $dp_{i,j,k}$ 为 DP 到第 $i$ 个，用了 $i$ 个 A，$j$ 个 B。有： $$ dp_{i,j,k}=\max\begin{cases} dp_{i-1,j,k} \\ dp_{i-1,j-1,k} + p_i & j>0 \\ dp_{i-1,j,k-1} + u_i & k>0 \\ dp_{i-1,j-1,k-1} + p_i+u_i-p_iu_i & j,k>0 \end{cases} $$ 考虑通过 WQS 二分降掉一维，就变成 $\mathcal O(n^2\log n)$ 的了。[Code](https://www.luogu.com.cn/record/66516103) $$ dp_{i,j}=\max\begin{cases} dp_{i-1,j} \\ dp_{i-1,j-1} + p_i & j>0 \\ dp_{i-1,j} + u_i - k \\ dp_{i-1,j-1,k-1} + p_i+u_i-p_iu_i - k &j>0 \end{cases} $$ 实际上还能搞一个 WQS 套 WQS，搞到 $\mathcal O(n\log^2 n)$。 > **WQS 二分优化 DP 的套路：** > > 适用条件： > > - 有数量限制； > - 函数有凸性； > > 做法： > > - 解决无限制问题 / 写出 DP 式； > - 考虑如何加权； > - 处理斜率切不到的问题。 - [P2260 [清华集训2012]模积和](https://www.luogu.com.cn/problem/P2260) 做个推式子题。由于原式就是 $$ \sum_{i=1}^n(n\bmod i)\times \sum_{j=1}^m (m\bmod j)-\sum_{i=1}^{\min(n, m)}(n\bmod i)(m\bmod i) $$ 直接暴力是 $\mathcal O(n)$ 的，能拿 30 分。 我们考虑怎么计算 $\sum_{i=1}^n (n\bmod i)$。注意到： $$ \sum_{i=1}^n (n\bmod i)=\sum_{i=1}^n(n-\lfloor\dfrac{n}{i}\rfloor\times i)=n^2-\sum_{i=1}^n\lfloor\dfrac{n}{i}\rfloor\times i $$ 然后直接整除分块，复杂度 $\mathcal O(\sqrt{n})$。再暴力计算后一部分可以做到 $\mathcal O(\sqrt{m}+\min\{n,m\})$，有 60 分。 考虑怎么优化计算后面那坨东西。令 $t=\min\{n,m\}$，同样把 $\bmod$ 拆开，得： $$ \sum_{i=1}^{t}(n-\lfloor\dfrac{n}{i}\rfloor\times i)(m-\lfloor\dfrac{m}{i}\rfloor\times i)=\sum_{i=1}^{t}(nm-n\lfloor\dfrac{m}{i}\rfloor\times i-m\lfloor\dfrac{n}{i}\rfloor\times i+\lfloor\dfrac{n}{i}\rfloor\times\lfloor\dfrac{m}{i}\rfloor\times i^2) $$ 也就是 $$ tnm-n\sum_{i=1}^t\lfloor\dfrac{m}{i}\rfloor\times i-m\sum_{i=1}^t\lfloor\dfrac{n}{i}\rfloor\times i+\sum_{i=1}^t\lfloor\dfrac{n}{i}\rfloor\times\lfloor\dfrac{m}{i}\rfloor\times i^2 $$ 其中第二、三项都可以套用上面的做法算，最后一项是一个二元的整除分块。原理是**只要二者之一变化就新开一轮计算**。 由于总轮数最大是 $\sqrt{n}+\sqrt{m}$，因此过得去。[Code](https://www.luogu.com.cn/record/66523773) - [P4606 [SDOI2018]战略游戏](https://www.luogu.com.cn/problem/P4606) 碰到删一个点再看连通性的题，自然想到 Tarjan，把所有的 v - DCC 跑出来，进行一个缩点。 有些细节想不灵清，后来上网搜，学了个东西叫圆方树。 Subtask 1 中，我们可以直接对每组询问暴力遍历； Subtask 2 中，等价于询问两个点之间路径上点的数量； Subtask 3 是一个常见结论，就是把询问中所有点按 DFS 序排序然后相邻 LCA。[Code](https://www.luogu.com.cn/record/66549606) - [P6617 查找 Search](https://www.luogu.com.cn/problem/P6617) 如果不带修，那么我们找出和每个数和为 $w$ 的前一个数下标 $pos_i$，然后比较 $\max\limits_{i=l}^r pos_i$ 和 $l$ 的关系即可。 带修的话我们考虑把每个 $x$ 和 $w-x$ 组成一对去考虑。（$x\le w-x$） 对于每个值对维护一个 `set` 记录它每次出现的下标，将两种不同值的看作两种颜色的球，然后考虑： > 如果出现了 白黑黑 这种情况，那么后面那个黑一定是无用的，$pos$ 可以设为 $0$。 那么每次 $pos$ 更新幅度是 $\mathcal O(1)$ 的，就可以直接线段树维护了。[Code](https://www.luogu.com.cn/record/66667579) - [P5298 [PKUWC2018]Minimax](https://www.luogu.com.cn/problem/P5298) 先对 $w_i$ 进行一个离散化。记第 $i$ 个结点权值为 $j$ 的概率为 $P_{i,j}$，那么： $$ P_{x,i}=p_x\times(P_{lc,i}\times\sum_{j=1}^iP_{rc,j}+P_{rc,i}\times\sum_{j=1}^{i-1}P_{lc,j})+(1-p_x)\times(P_{lc,i}\times\sum_{j=i}^mP_{rc,j}+P_{rc,i}\times\sum_{j=i+1}^mP_{lc,j}) $$ 前缀和优化一下可以 $\mathcal O(n^2)$ DP，拿到 40 分。 当你要用低于 $\mathcal O(n^2)$ 的时间算一个二维 DP，就应该考虑线段树，因此考虑线段树合并优化 DP。 如果一个点是叶子，那么就权值就固定了；如果一个点只有一个儿子，那么转移就是直接传递上去。 否则我们就要合并两棵线段树，结点上维护区间和。 如果两棵树均不为空，那么我们直接向下递归；否则必然有一颗子树为空，这样其实只需要关注两方的前缀、后缀和即可。式子变成： $$ P_{x,i} = p_x\times P_{lc,i}\times\mathrm{Pre_rc}+(1-p_x)\times P_{lc,i}\times \mathrm{Suf_rc} $$ 这样相当于一个修改 $X\gets (p_x\times \mathrm{Pre_rc}+(1-p_x)\times \mathrm{Suf_rc})\times X$，就是一个乘法标记。[Code](https://www.luogu.com.cn/record/66791694) - [CF1625D](https://codeforces.com/contest/1625/problem/D) 有 xor，又显然不是线性基，那就是 0-1 trie 了。 DFS 整棵树，若当前 $k\le 2^{dep}-1$，可以递归下去，在左右子树内分别选出然后再并起来。 否则有 $k\ge 2^{dep}$，那么如果有不只一个解肯定是在两棵子树内分别挑一个，使二者异或和最大。 可以挑出每个数搜一遍取 $\max$。[Code](https://codeforces.com/contest/1625/submission/142769666) - [P5344 【XR-1】逛森林](https://www.luogu.com.cn/problem/P5344) 显然能想到一个边数 $\mathcal O(m\log^2n)$ 的树剖套线段树优化建图的煞笔做法。 优化可以用 **ST 表优化建图**，好像大多数情况下全方位吊打线段树？反正就变成 $\mathcal O(n\log n+m)$ 的了。[Code](https://www.luogu.com.cn/record/67001922) [有个牛逼东西先存一下](https://www.luogu.com.cn/blog/221955/chang-jian-you-hua-jian-tu-ji-qiao) - [P5468 [NOI2019] 回家路线](https://www.luogu.com.cn/problem/P5468) 把式子打开： $$ dp(i)=dp(j)+A(p-q)^2+B(p-q)+C=dp(j)+Ap^2-2Apq+Aq^2+Bp-Bq+C $$ 那么： $$ dp(j)+Aq^2-Bq=2Ap\times q+dp(i)-C-Bp-Ap^2 $$ 单调队列维护下凸包即可。 - [P6185 [NOI Online #1 提高组] 序列](https://www.luogu.com.cn/problem/P6185) 一个结论题。首先 $2$ 操作就是能在一个 $2$ 边连通块内任意传导能量，因此我们可以把 $2$ 的连通块看成一个点。 剩下的就是结论了：如果这张图是二分图，那么合法当且仅当两部差值和相同；否则当且仅当差值和为偶数。 证明是不困难的，难的是猜结论。 - [P2048 [NOI2010] 超级钢琴](https://www.luogu.com.cn/problem/P2048) 先把连续段转化为 $S_r-S_{l-1}$ 的形式。令 $y=r,x=l-1$，那么条件就是要 $y-x\in [L,R]$。 可以对每个 $x$ 去维护当前最优的 $y$，然后压入堆中做。问题还剩下怎么去寻找最优的 $y$。 由于这个问题本质上就是静态在线询问区间第 $K$ 大，所以可以直接主席树。 貌似还有直接 split 区间的牛逼做法...... - [P2522 [HAOI2011]Problem b](https://www.luogu.com.cn/problem/P2522) 莫反一下： $$ \sum_{i=a}^b\sum_{j=c}^d[\gcd(i,j)=k]=\sum_{i=a}^b\sum_{j=c}^d[k\mid \gcd(i,j)]\times\mu(\gcd(i,j)) $$ 换成枚举 $t=\dfrac{\gcd(i,j)}{k}$： $$ \sum_{t}\mu(t)\left(\left\lfloor\dfrac{b}{tk}\right\rfloor-\left\lfloor\dfrac{a-1}{tk}\right\rfloor\right)\left(\left\lfloor\dfrac{d}{tk}\right\rfloor-\left\lfloor\dfrac{c-1}{tk}\right\rfloor\right) $$ 后面那个东西可以裂成四部分，每部分都是 $$ \sum_{t}\mu(t)\left\lfloor\dfrac{n}{tk}\right\rfloor\left\lfloor\dfrac{m}{tk}\right\rfloor $$ 的形式。这个东西可以对 $\mu$ 作前缀和然后整除分块。 - [P3327 [SDOI2015]约数个数和](https://www.luogu.com.cn/problem/P3327) 碰到这种题，如果要莫反肯定是拆成 $\gcd$ 的形式，但是这个 $d$ 非常难拆，好在我们有题解。 反手一下就点开了题解，很快啊！我就看到了一个结论： $$ d(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1] $$ 然后就可以推了： $$ \sum_{i=1}^n\sum_{j=1}^m\sum_{x\mid i}\sum_{y\mid j}\sum_{t\mid \gcd(x,y)}\mu(t) $$ $$ =\sum_{i=1}^n\sum_{j=1}^m\sum_{t=1}^{\min(n,m)}\mu(t)\sum_{x\mid i, t\mid x}\sum_{y\mid j, t\mid y}1 $$ $$ =\sum_{i=1}^n\sum_{j=1}^m\sum_{t=1}^{\min(n,m)}\mu(t)\sum_{x\mid i, t\mid x}\sum_{y\mid j, t\mid y}1 $$ $$ =\sum_{i=1}^n\sum_{j=1}^m\sum_{t=1}^{\min(n,m)}\mu(t)\sum_{x\mid i, t\mid x}\sum_{y\mid j, t\mid y}1 $$ $$ =\sum_{i=1}^n\sum_{j=1}^m\sum_{t\mid i, t\mid j}^{}\mu(t)d\left(\dfrac{i}{t}\right)d\left(\dfrac{j}{t}\right) $$ $$ =\sum_{t}\mu(t)\sum_{i=1}^{\lfloor\frac{n}{t}\rfloor}d(i)\sum_{j=1}^{\lfloor\frac{m}{t}\rfloor}d(j) $$ 预处理 $S(n)=\sum_{i=1}^nd(i)$，原式就是 $$ =\sum_{t}\mu(t)S(\lfloor\frac{n}{t}\rfloor)S(\lfloor\frac{n}{t}\rfloor) $$ 就可以整除分块了。 莫反还有一个套路是把两个变量相乘的形式换元。 - [P2523 [HAOI2011]Problem c](https://www.luogu.com.cn/problem/P2523) 转换题意，就是要制定一种分配 $a_i$ 的方式，使每个后缀和都不大于后缀长度。 那么直接 DP 即可。 - [CF1619H Permutation and Queries](https://www.luogu.com.cn/problem/CF1619H) 有种牛逼做法是根号分治，储存每个数前、后、以及后 $\sqrt{n}$ 个的数。 但是我想不到，只会用 Splay 乱维护。后来发现假了/wq