做题记录 3

fzitb7912 · 2024-11-13 12:36:18 · 个人记录

P8512

别闹。很早就打算写，一直没时间，补一下。

考虑一次覆盖 l~r~x，设当前时间为 t，那么在不被其它区间覆盖的情况下，t\sim n 这些时间 a_l\dots a_r 都将是 x。不难发现这个像是个永久标记（差不多，我也不知道叫啥）。

考虑扫描线。我们去枚举每个时间 r，那么有上面的性质就能直接继承 r-1 时间的值了。只需要改变一个区间内的值。现在考虑将区间在时间 r-1 的值求出来。很显然，因为只有合并几个区间和增加 1 个区间两种情况，所以每次操作只会多出来 O(1) 个区间。均摊是 O(1) 的。那么我们拿一个 set 暴力维护的复杂度就是 O(n\log n) 的。

对于一个询问区间，直接就是查询一下当前时间所有点的值，再除去覆盖之后时间还是不超过 l 的点的值就行了。这个可以拿树状数组维护。总结为超弱 ODT + 超弱扫描线。

P9992

别闹。

很显然，对于一个点 x，记它到 w 的距离为 dis，那么当 d-dis\ge d' 时 (x,d') 是可行的。那么 x 能取到的 d' 的范围就应该是：[0,\min(d+dep_w-dep_x,mdep_x-dep_x)]。

那么我们将询问离线，维护出所有 mdep_x \le d+dep_w 的 mdep_x-dep_x 的和与 mdep_x > d+dep_w\land dep_x \le d+dep_w 的数量与 dep_x 的和就行了。使用树状数组可以做到 O(n\log n)。

P10938

考虑暴力。对于选择了 x 这个点，我们能够求出一个点集 S，使得 S 中任意一个点都不能选。

我们现在需要求最多能选多少个点出来。发现答案就是最小重复路径覆盖。证明。

对于一个 i，我们向 S_i 中所有点的出点连边，然后跑最大流。这样每条边都被选了 1 次。那么最小重复路径覆盖就是点数 - 最小路径点覆盖了。

UVA11270

参考文章，参考文章 2。

考虑轮廓线 DP。对于只有四周的点有用的问题，很多时候都能轮廓线 DP。具体地，我们能够通过记录上一行 j 往后所有点的状态和这一行 j 往前的状态来对 j 进行转移。使得不必要的状态可以直接舍掉。

那么对于这道题，我们在格子 (i,j) 就有三种情况：

不难发现，每次状态的更新只会改变 O(1) 个点，所以转移是 O(1) 的。总的时间复杂度为 O(n2^m)。因为 n\times m \le 100，所以 \min(n,m) \le 10。当 n<m 的时候交换 n,m 对答案无影响。

P1896

虽然但是我是来写轮廓线 DP 的啊。

考虑状压 DP。定义状态函数 f_{i,s,j} 表示前 i 行，放了 j 个国王，第 i 行放国王的状态为 s 的方案数。那么对于相邻两行的状态 s1,s2，只需要保证 s1 整体往左或右移 1 位后与 s2 不存在同一个位置为 1。自己的这一行同理。那么就能直接转移了，时间复杂度 O(nk4^n)。

P1437

虽然但是我是来写轮廓线 DP 的啊。

这里将空的价值定义为 0。

考虑枚举列。定义状态 f_{i,j,k} 表示在第 i 行第 j 列，选了 k 个数的最大价值。如果我们选了 (i,j)，那么 (i,j) 往右上形成的三角形中所有数都将被选。那么当我们倒着枚举列的时候，只要满足上一次选择的点在 (i-1\sim n,j+1)，(i,j) 的贡献就只有这一列的前 i 行了。其它的就被上一个状态包含了。时间复杂度 O(n^3m)。

P4363

虽然但是我是来写轮廓线 DP 的啊。

别闹。这题有点难搞。

一步一步来想。

Hint 1

第 1 次和第 nm 次决策的位置？

Hint 2

每次决策之后每个点被选择的状态分布？（有棋子就算被选）

Hint 3

如何表示所有被选择的点的状态分布？

Hint 4

每次决策方的最有利的方式？

分析

观察样例解释，不难发现第 1 次决策一定是 (1,1)，第 (n,m) 次决策一定是 (n,m)。想想为什么会这样。很显然的，如果我们选择了一个点 (i,j)，那么 (i-1,j) 和 (i,j-1) 要么不存在，要么被选过了。所以在第 1 次决策的时候，只能选择 (1,1)。而在最后一次决策的时候，因为只剩 1 个点了，如果此时 (n,m) 已被选择，那么前面所有点都将被选择，显然是不可能的。

那么这个能否推出别的某些性质呢？显然是可以的。可以发现，如果选了 (i,j)，那么前 i 行的前 j 列都将被选，那么对于每次决策之后，每个被选择的点的状态分布将形如：

其中红线将所有被选和没被选的点分开了。那问题就变得简单了，我们可以用一条红线唯一地表示一种所有点被选择的状态。那么我们只需要维护出每条红线的最优价值就行了。

考虑对于第 i 次决策，决策方的最优选择点。如果决策方是菲菲，那么他将会尽可能地使答案最大；如果使牛牛，那么他将尽可能地使答案最小。则只要我们知道了某个点在这一轮被选之后的答案，就能知道这一轮该选哪个点了。

联想到数位 DP。在需要知这一位是多少之后的答案时，可以选择记忆化搜索。这题也是一样的。我们可以对状态进行记忆化，那么现在唯一的问题就只有实现红线的表示了。

对于上面那张图，如果我们把最后两列的第 0 行也画上红线，那么红线 n+1 种状态，总的状态数为 (n+1)^{m}。那么我们就可以用一个 n+1 进制数表示这条红线了。

这样的话总的时间复杂度貌似是 O(m \times 有用状态数) 的，应该带点常数。跑得飞快。

P10592

因为我们一旦删成非降的，就停下来了。所以需要保证在最后时刻序列 A 非降，且上一个时刻 A 不是非降。

考虑容斥，那么我们只需要算出最后时刻是非降的方案数与最后时刻与上一个时刻同时为非降的方案数，就能得到满足条件的方案数了。

对于最后时刻非降，定义状态函数 f_{i,j} 表示以 i 为结尾，选了 j 个数的方案数。那么可以用树状数组维护出答案。则最后一个长度为 j 的非降序列的方案数为：\sum f_{i,j}\times (n-j)!。

而对于最后两个时刻都是非降的情况，显然是我们多删了一个数。而这个数一定满足：A_{p_{i-1}}\le A_{p_i} \le A_{p_{i+1}}，即删之后不破坏序列 A 的整体形式。所以倒数第 2 个时刻是非降且最后时刻也是非降对于一个长度为 j 的序列的方案数就是：\sum f_{i,j}\times j \times (n-j)!。

时间复杂度 O(n^2\log n)。

P7836

十分困难。别闹啊。

数据范围明显得要让我们分开搞。

【Sub2】

应该是暴力。这里有个主体思路，我们完全可以贪心地将当前背包里的食材删掉，直到每种出现过的食材数量刚好为 1。因为我们保留更多的是没有用的。那么我们就可以用二进制数表示 x 种食材的出现状态了。

同时，可能存在当前的一个状态 s，将 s 与第 i 个采集点结合时出现了背包装不下，单删掉 s 中的几个 1 后能够装下且更优。这启示我们，对于一个 s 实际上是可能转移到其一个子集会更优。既然都能转到子集了，那么在第 i 个采集点的时候，记 t_i 为这个采集点每个食材的出现状态，我们就完全可以用一个与 t_i 不交的状态 s 来转移。

我们对于当前能够达到的所有状态 s 去转移 s'。如果 s' 已经被转移过了，那显然是没有必要再转移一次的。那么我们就能保证每个状态最多被转移 1 次。同时，因为 s 的所有子集也可以去转移，所以算上枚举子集的复杂度就是 O(3^x) 的。

这里给个小优化：因为 n 十分巨大，如果我们对于每个 t_i 都去枚举它能达到的状态 s'，最坏是 O(2^xn) 的，但是根据上一自然段的分析，得知对于相同的 t_i 是没必要再去遍历一遍的，直接清空就行。具体操作的时候会发现，我们可能一个 |s'|+V_i >v 了，在这个采集点是无法转移的，而可能会有后面的某个转移点可以转移，但是我们给它清空了。为了避免这种情况，我们可以存一下 |s'|。

【Sub3】

我是来做轮廓线 DP 的。

考虑到，对于一个状态 s'，如果它可以通过 t_i 和 s 得到，当且仅当 s' 是 t_i \cap s 的子集。根据 Sub2 分析的第二个自然段，可以进一步得到：当状态 s' 能被转移到时，需要满足 s' 的所有子集都能被转移到。那么我们拿一个 set 来记录所有合法的状态，如果一个状态可以得到，我们去推它的一个超集，动态插入所有从不合法变成合法的超集。那么之后任意时间，这个状态都没有用了，可以直接删掉。

现在考虑枚举超集。根据上述的条件，我们得知 s' 合法的前提是其子集都合法，那么我们枚举超集的时候就只需要枚举所有 |S|=|s'|+1 的 s' 的超集，只要 S 删掉任意一个 1 得到的集合都合法，那么它就合法了。为什么不需要枚举 |S|=|s'|+2 的超集？很显然，当 |S'|=|s'|+1 且 S' 是 S 的子集时，如果 S' 仍不合法，那么 S 显然不合法。如果 S' 合法，那么 S 将在枚举 S' 的超集时被枚举到。所以这样就是对的。

因为这样我们保证了对于任意时刻，不存在 set 中的两个状态 a,b，有 a 是 b 的子集。所以 set 中最多 x 个状态。额，分析不来了。复杂度未知，应该不是很大。

貌似不删除的复杂度是 O(2^xn) 的，也能过。

AT_agc017_f

陈年老题，听了若干遍都没补。

很显然，一条路径 p 我们可以用唯一的二进制数 s 表示出来，其中 s_i=0 表示第 i 步向左走，反之同理。不难发现，当我们走到了第 j 行，那么上一条路径前 j-1 步是没有用的。于是就可以考虑轮廓线 DP。

因为强调在上一条路径的右边，不妨让这条路径初始时与上一条路径完全重合。那么只需要考虑拐弯的情况。定义状态函数 f_{i,j,s} 表示第 i 条路径，走到第 j 行，每一步的状态为 s 时的方案数。考虑对第 j 步向左向右的情况进行分类讨论：

向左走。那么前提条件是这一步没有被强制向右走，且上一条路径也是向左走。因为如果我们上一条路径是向右的，那么就跑到上一条路径的左边去了。
向右走。如果这一步没有被强制向左走，且上一条路径也是向右，那么就可以向右。如果上一条路径是向左，那么我们向右拐之后需要一直向左，直到再次与上一条路径重合，具体实现只需要找到第 j 步之后第一次向右的位置，然后这个区间所有的状态都变成向左就行了。

时间复杂度 O(nm2^n)。

CF1098B

绿题。

不难发现，对于第 i 行如果我们确定了连续的 4 个的值，那么第 i+1 行值的情况就不会超过 2 种。例如第 i 行为：1~3~1~3 时第 i+1 行为：2~4~2~ 或 4~2~4~2。而当第 i 行为： 1~2~3~4 时第 i+1 行为：3~4~1~2。那么就可以 DP 解决了，时间复杂度 O(nmk)，其中 k 为所有合法的连续 4 个的值的数量。

P8163

奶龙题，别闹。

考虑 A_i < B_i \land S_j < T_j 怎么做。记 r_x 为从 x 出发，能够不换乘到达的最远的位置。那么我们可以用 1 的代价，将起点从 x 变为 [x+1,r_x] 中的任意位置。这里有个简单的贪心，既然我们要换乘，那显然换乘到 r_{x'} 最大的那个点。

然后做法就简单了。因为我们要从 S_j 走到 T_j，那么考虑从 S_j 出发，每次走到 [x+1,r_x] 里面 r_{x'} 最大的那个点去换乘，直到 x \le T_j \le r_x。发现方案一定，记 R_{x,i} 表示从 x 出发，换乘 2^i 次能到达的最远的位置。然后倍增查询即可。

现在考虑 A_i >B_i 怎么做。发现往左走与往右走等价，这里只考虑往右走。记 L_{x,i} 为从 x 出发，向左走 2^{i} 步能到达的最远的位置。那么对于 x 往右走一步，我们就可以将起点变成 [L_{x,0},R_{x,0}] 中的任意一个点了。也就是说，最大的 r_{x'} 将可能出现在 [L_{x,0},x-1] 中。那么在预处理倍增的时候，我们就可以再维护一个区间最大值或最小值来跑了。也就是说，这是一个倍增套倍增？

查询的时候和 A_i <B_i 的情况类似，只需要一直拓展左右端点，找到最小的步数使得左右端点完全包含 S_j 和 T_j 即可。时间复杂度 O(n\log ^2 n)。

注意，这里查询倍增的时候是不能一味的往一边倍增，需要使用维护的区间最大值和最小值。不懂可以看样例 4 的倒数第 3 个查询。

AT_arc136_d

考虑对于 a_i，一个 a_j 与其相加不会进位，当且仅当对于每个 k，都有：a_{i,k}+a_{j,k} \le 9。

那么我们对于每个 i 就得到了 \log_{10} a_i 个限制，第 j 个限制 b_j 表示与其相加不进位的数第 j 位不能超过 b_j。那么做一个 6 维的前缀和就行了。

这里对于一个 k 维的前缀和，我们可以在 O(kn^k) 内求解。一共跑 k 次前缀和，第 i 次前缀和有：s_{a_1,a_2,\dots,a_k}+=s_{a_1,a_2,\dots,a_{i}-1,a_{i+1},\dots,a_k}。

P6442

定义状态 f_{s} 表示 s 是一个箱子中没出现过的玩具状态的子集的数量。考虑容斥，因为我们要求没有玩具没出现过，所以只需要求出没出现过的玩具数量 \ge 1 的方案数。记 w_s 为没出现过的玩具子集为 s 的方案数，那么有：w_s=2^{f_s}-1。求 f_s 直接 SOS DP 即可。时间复杂度 O(m2^m)。

CF165E

AT_arc136_d 的双倍经验吧。对于 a_i 二进制下第 x 位，如果为 0，那么另一个数可以是 0/1；如果是 1，那么另一个数是 0。不难发现这就相当于 \le b_x。然后记录一下数字就行了。时间复杂度 O(V\log V)。

CF383E

P6442 的双倍经验吧。

因为它问满足至少 1 个元音字母，那么可以通过有 0 个元音字母容斥得到。

那么对于一个字母的出现状态 s，因为元音字母的状态 t 可以是任意一个字符集，所以这个 s 一定能恰好对应一个 t 的补集。那么我们只需要求出有多少个单词 i，使得其字母的出现状态为 s 的子集。这个可以直接 SOS DP。时间复杂度 O(V2^V)。

CF1620G

P6442 的双倍经验吧。

观察到这题给了 10s。

对于一个下标集合 s，记 cnt_x = \min\limits_{i\in s} Cnt_{i,x}。那么这些下标对应的字符串共有的子序列数量就是 (\prod (cnt_x+1) )。那么记 f_i 为集合 i 的所有子集对应的公共子序列数量的和，因为要求 \ge 1 的数量，所以容斥一下就行了。使用 SOS DP 可以做到 O(n2^n+2^{n+1}V)。

P9333

别闹。这题有点难搞。

直觉告诉我们这题可能只能暴力枚举每个人当总统。那么对于第 i 个人当总统的情况，可以发现当去掉第 i 个人的所有投票后，因为赞成的票数不会增加，所以当第 j 项投票的赞成票数量小于 \lfloor \frac{n}{2}\rfloor 时，是不可能有贡献的。而当数量大于 \lfloor \frac{n}{2}\rfloor 时，在最坏情况下也不会小于 \lfloor \frac{n}{2}\rfloor，所以是一定有贡献的。

那么现在只需要考虑等于 \lfloor \frac{n}{2}\rfloor 的情况。记其下标集合为 s。现在考虑对于一个人 j，那么他的贡献将是：-\sum\limits_{x\in s}^{} [a_{j,x}=1]。可以将 s 看作一个二进制数，其中 x \in s 的位置为 1，记为 t，那么贡献就是 -|t \cup a_j|。所以现在对于第 i 个人当总统的情况，我们就只需要解决除了 i 以外 |t \cup a_j| 的最小值。j \ne i 这个限制很弱，统计最小和次小就行了。

这里只针对了最大值，实际上为了保证 i \ne j 还需要记录次大值。证明可行简单。参考 CSP-J 2024 T4 题解。

注意记录最大值和次大值的时候，需要保证这两个值的编号不同。

P2435

考虑轮廓线 DP。定义状态函数 f_{i,j,s} 表示到第 i 行第 j 列，第 i 行的前 j 列与第 i-1 行的第 j+1~\sim m 列形成的颜色状态为 s 的方案数。那么只需要用 k 进制数表示 s，要满足第 j 列与其左边和上面不同就行了，转移 O(k)。时间复杂度 O(nmk^{m+1})。

AT_arc100_c

简单吧。不难发现，i 可能对 K 有贡献，当且仅当 i 是 K 的子集。那么问题就变成：对于每个 K，在其子集里面选 2 个数 i,j，使得 a_i+a_j 最大。然后取前缀 \max。跑个高维前缀 \max 可以做到 O(n2^n)。

CF1208F

考虑枚举 i。那么对于一对可行的 j,k，有 \min(j,k) >i。那么如果我们再去枚举 d_j \& d_k，就只需要维护所有 d_j \& d_k =x 时 \min(j,k) 的最大值了。只要这个最大值大于 i，那么 d_j \& d_k 显然是存在的。如果直接这样做，复杂度是 O(nV) 的。考虑优化。

不难发现，高位肯定是比低位优先的。记当前能够达到的最大的 d_j \& d_k 的值为 x。那么对于一个低位 s，它能加到 x 上成为新的最大值当且仅当 x+2^s 这个值不大于一对 d_j\& d_k \land \min(j,k) >i。也就是说，当一个 x' \ge x+2^s 且对应最大的 \min(j,k)>i 时，s 就会有贡献。

直接高维后缀 \max 就行了。复杂度 O(V\log V+n\log V)。

AT_agc038_c

乱推式子。

\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} \operatorname{lcm}(a_i,a_j)\\ =\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} \frac{a_ia_j}{\gcd(a_i,a_j)}\\ =\sum\limits_{d=1}^{V}\frac{1}{d}\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} a_ia_j[\gcd(a_i,a_j)=d]

记 f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=i+1}^{n} a_ia_j[\gcd(a_i,a_j)=d]。根据容斥，我们有：

$$\sum\limits_{i=1}^{n} a_i[d|a_i] \sum\limits_{j=i+1}^{n}a_j[d|a_j]\\=\frac{\sum\limits_{i=1}^{n} a_i[d|a_i](\sum\limits_{j=1}^{n} a_j[d|a_j]-a_i[d|a_i])}{2}\\ =\frac{(\sum\limits_{i=1}^{n} a_i[d|a_i])^2-\sum\limits_{i=1}^{n} a_i^2[d|a_i]}{2}

记 cnt_x=\sum\limits_{i=1}^{n} [a_i=x]，那么有：

\frac{(\sum\limits_{i=1}^{n} a_i[d|a_i])^2-\sum\limits_{i=1}^{n} a_i^2[d|a_i]}{2}\\ =\frac{(\sum\limits_{x=1}^{\lfloor\frac{V}{d}\rfloor} cnt_{xd}xd)^2-\sum\limits_{x=1}^{\lfloor\frac{V}{d}\rfloor}cnt_{xd}x^2d^2}{2}

这个可以在 O(V\log V) 预处理出来，记为 g(d)。那么有：f(d)=g(d)-\sum\limits_{x=2}^{\lfloor\frac{V}{d}\rfloor}f(xd)。这个也可以在 O(V\log V) 解决。那么有答案为：\sum\limits_{d=1}^{V}\frac{1}{d}f(d)。时间复杂度 O(V\log V)。

P7447

别闹。这题强暴了，有点好玩。

一步一步来。

Hint 1

如何暴力？

Hint 2

能不能优化暴力？复杂度证明？

Hint 3

为什么复杂度不对？进一步优化？复杂度证明？

分析

下面的 B 和 b 是一个东西。

虽然上面说了跟没说一样，但是跟着上面来。

首先暴力简单。考虑枚举区间 [l,r] 的每一个数，当其 >x 时就减掉。

考虑线段树，发现因为 a_i 不增，那么很多区间实际上是没用的。对于每个区间维护其最大值，最小值。若最大值不大于 x，那么这个区间不会有数被减。同理，如果这个区间的最小值仍大于 x，那么区间所有数都将被减。这样就已经比暴力好很多了，但是如果构造使得 \min \le x < \max，那么最坏的复杂度将是 O(n V)。

发现导致上面的线段树做法复杂度错误的原因是会存在 x，使其不断递归到叶子节点。那么既然直接维护序列不行，就可以考虑维护值域。对于一个值域区间 [x,y]，我们去维护这个值域里面的所有下标，但是注意到当 a_i-x 后，它的值域会改变。那么这样一次修改就会影响最坏 n 个点，也难以接受。

既然直接维护值域和直接维护序列都不行，那考虑在维护值域的基础上维护序列。我们考虑对值域分块，对于一个值域块 [X,Y] 用一棵线段树维护序列。那么再使用最开始的方式维护。当区间最大值不大于 x，操作无效。当区间最小值大于 x，整体减去 x，动态维护这个区间的值域。如果减去之后跨越 X，将这些被影响的线段树重构。其它情况继续下传。

这样的话，如果我们将第 i 个块的值域赋成 [B_i,B^{i+1})，那么会得到 \log_bV 棵线段树。对于跨越值域的情况，考虑均摊分析：因为每个点不增，所以最多会跨越 \log_b V 次。那么暴力重构总的复杂度就是 O(n\log_b V \log n)。而没有重构的情况，直接打 tag 的复杂度是 O(m\log_b V\log n) 的。

那么对于 \min \le x < \max 的情况。因为一个点在块内最多被减 \frac{B_{i+1}}{B_i}\log_b V 次，那么总的复杂度就是 O(B n \log_b V \log n) 的。

那么这样做的总时间复杂度就是 O(Bn\log n\log_b V+(n+m)\log n\log_b V) 的。空间复杂度 O(n\log_b V)。

这就已经是正解了。但是空间有点炸裂。

注意到时限给了若干秒，考虑拿时间换空间。考虑到一棵线段树的节点数量随 b 按指数增加，那么考虑对一个深度进行剪枝。具体的，我们对于一个深度 dep，当这棵树深度比 dep 大时，考虑暴力修改序列。这样常数炸裂，但是空间少很多。

具体实现恐怖，建议口胡。预计实现 1h+，调试 1h+。

实测 B=32 能过。