CSP2024 前做题情况 2

fzitb7912 · 2024-10-17 11:32:22 · 个人记录

CSP2024 前做题情况 1。

AT_arc067_d

没想到还能单调栈啊。

枚举区间 [l,r]，得到每张烧烤券的最优位置，然后取最大价值。这个的时间复杂度是 O(n^2m)，难以接受。

考虑换个角度思考。我们还是去枚举 l，记 q_i 为区间 [l,n] 中最大的一个 b_{j,i} 的位置。那么 r=\max\limits_{i=1}^{m} q_i。不难发现，随着 l 的减小，q_i 不增。同理可得 r 不增。将 r 视作 l 的最优决策点，记为 p_l。那么有：p_i \ge p_{i-1}(2 \le i \le n)。

然后由于决策点有单调性，就能分治求解了。没学过的可以看这里面对 CF321E 的讨论。那么求所有点的最优决策点的复杂度就是 O(nm\log^2 n) - O(nm\log n) 了。最后再对每对 (l,p_l) 求一个最大价值即可。

P11197

参考文献，云浅老师好强。 /bx/bx/bx

发现条件 1 没有什么用。令 a_i 为 i 在 P(1) 中的位置；b_i 为 i 在 P(2) 中的位置；c_i 为 i 在 P(3) 中的位置。若满足 a_i < a_j \land b_i < b_j \land c_i <c_j ，且 T 中 i 在 j 前面，则满足条件。若此时 T 中 i 在 j 后面，那么就可以把 i,j 交换一下，也满足条件。

所以原题就是求满足：a_i <a_j\land b_i < b_j\land c_i<c_j 的二元组 (i,j) 的数量。这是一个三位偏序的板子，使用 CDQ 分治可以做到 O(n \log^2 n)。需要细微卡常，但是能过。

在这里介绍一下时间复杂度为 O(n\log n) 的算法。该算法带了一个 3 倍的常数，不过不影响。我们考虑把一个三维偏序问题转化为 3 个二维偏序问题的交。令 S_1=\{(i,j)|a_i<a_j\},S_2=\{(i,j)|b_i<b_j\},S_3=\{(i,j)|c_i<c_j\}。那么有答案集合 S=S_1\cap S_2\cap S_3，则 (i,j) 的数量为 |S_1\cap S_2\cap S_3|。根据容斥有：|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-|S_1\cup S_2\cup S_3|}{2}。其中 S_1,S_2,S_3 分别能够算出来，难点在于维护 |S_1\cup S_2\cup S_3|。这里需要一点注意力。

对于一对 (i,j)，我们会发现若它们满足一维偏序，则 (j,i) 满足二维偏序；若它们满足二维偏序，则 (j,i) 满足一维偏序；若它们满足三维偏序，则 (j,i) 不满足任何偏序。而 S_1,S_2,S_3 中任何一对 (i,j) 至少满足二维偏序。所以 |S_1\cup S_2\cup S_3| 刚好是无序二元组 (i,j) 的数量，即 \frac{n\times (n-1)}{2}。

所以原式子可以写成：|S_1\cap S_2\cap S_3|=\frac{|S_1\cap S_2|+|S_2\cap S_3|+|S_3\cap S_1|-\frac{n\times(n-1)}{2}}{2}。所以只需要算出来 |S_1\cap S_2|,|S_2\cap S_3|,|S_3\cap S_1| 就能求解三维偏序问题了。时间复杂度 O(n\log n)。

P6885

考虑 DP。

不难发现，原题的操作相当于将序列剖成两个子序列，将其中一个翻转后将第二个拼在它后面。考虑枚举第一个在 1 右边，且在最终的 LIS 上面的点 i。不难发现，i 往后相当于是 i 开头的一个最长上升子序列，i 往前相当于是 i 开头的一个最长下降子序列。直观的感受到，这两个子序列的交只有 i 这个点。所以最终的最长上升子序列仅存在于 i 开头的最长上升子序列与最长下降子序列拼起来的子序列中。

那么就很容易了。令 f_i 表示 i 往后的最长上升子序列长度，fcnt_i 表示 i 往后最长上升子序列数量；g_i 和 gcnt_i 同理。那么就有：M=\max\limits_{i=1}^{n} (f_i+g_i-1)。

现在考虑如何求方案数。对于一个 i，它存在于最终的最长上升子序列中当且仅当 f_i+g_i-1=M。那么此时这 M 个数选出来的方案数即为 fcnt_i \times gcnt_i。然后剩下的点放左边、右边随便选，1 这个点可以看作放在了空点的左边或者右边，所以总的方案数为：\sum\limits_{i=1}^{n}fcnt_i\times gcnt_i\times 2^{n-M}[f_i+g_i-1=M]。时间复杂度为 O(n\log n)。

P6371

记得 10 月初的时候谁问过我（好像是 CEFqwq）？然后没找到原题。

很显然的，我们有一个数位 DP 的做法。f_{i,j} 表示到第 i 位，前面的数对 x 取模之后为 j 的数量。那么一个数可行当且仅当 j=0。注意前导 0 是可取的，但是非前导 0 可能不可取即可。该算法时间复杂度为 O(X\times len)。

因为这题空间比较离谱，x 也很大。考虑另一种做法。我们直接去枚举 X 的倍数，暴力地判断是否可行。时间复杂度为 O(\frac{V}{X}\times len)。两个做法中和一下即可。

P7482

考虑分治。对于一个下标 x，我们令 1 表示选择它，0 表示不选。那么对于跨 mid 的一段区间，mid-1,mid,mid+1,mid+2 这 4 个点的选择情况可能为：

1. 1 ~0~0~1
2. 1~0~1~0
3. 0~1~0~1

我们记 f_{i,0} 表示 mid 这个点一定不选时的最大和，f_{i,1} 表示 mid 这个点可能选时的最大和；g_{i,0} 表示 mid 这个点一定不选时的最大和，g_{i,1} 表示 mid 这个点可能选时的最大和。那么对于一组 l,r，它的最大和即为 \max(f_{l,0}+g_{r,1},f_{l,1}+g_{r,0})。

若 f_{l,0}+g_{r,1} > f_{l,1}+g_{r,0}，则选左方更优，此时有：f_{l,0}-f_{l,1}>g_{r,0}-g_{r,1}。也就是说只要满足该不等式，左边就一定最优。那么直接按照差值排序之后双指针就行了。时间复杂度 O(n\log^2 n)。

这道题存在线性做法。

AT_arc071_c

好玩。

很显然，我们可以将所有 A 变成 B 或者把所有 B 变成 A。因为将一个 A 变成 B 再变成 A 将会得到 4 个 A，消掉 3 个就只剩 1 个。这是无效操作。拿前者举例，1 个 B 能变成 2 个 A。则区间 [l,r] 能够得到 cntA_r-cntA_{l-1}+2\times (cntB_r-cntB_{l-1}) 个 A。记 S_{a\dots b} 中有 x 个 A，T_{c\dots d} 中有 y 个 A。

现在只能进行消除操作了，那么 x 个 A 将剩下 x \bmod 3 个 A。y 同理。所以当 x 与 y 模 3 同余时，S_{a\dots b} 能够变成 T_{c \dots d}，否则不行。时间复杂度 O(n+q)。

AT_agc003_f

考虑连通块的数量会怎么变化。分情况讨论：

1. 原图所有黑色点形成一个连通块，即竖直、水平均连通。那么无论这个网格怎么分形，它都将会是一个连通块。答案为 1。
2. 原图所有黑色点都不相邻，即竖直、水平均不连通。那么网格每分形一次，连通块数量就会变成 cnt^{k-1} 个。cnt 为原图中黑点的数量，k 为当前分形是第几个。注意 0 级分形是 1 个连通块。
3. 原图黑点部分相邻。此时需要单独计算。

这里水平连通指存在 i(1\le i \le n)，使得 a_{i,1}=1\land a_{i,m}=1。其中 1 表示黑色点。竖直连通同理。

考虑计算第 3 种情况的答案。不难发现，此时仅存在水平连通或竖直连通 2 种情况。它们本质上是相同的，这里仅考虑水平连通的情况。记 c1 为当前分形中黑点数量，c2 为当前分形中相邻的黑点对数。即 a_{i,j}=1\land a_{i,j+1}=1(1 \le i \le n\land 1 \le j <m) 的 (i,j) 数量。会发现，当当前分形继续分形一次后，会增加 c1-c2 个连通块。那么就好做了，定义状态函数 f_i 表示第 i 次分形的连通块数量。记 x 为原图中黑点数量，y 为原图中相邻黑点对数，z 为 a_{i,1}=1\land a_{i,m}=1(1\le i \le n) 的数量。那么有：f_{i}=f_{i-1}\times x -y\times z^{i-1}。

发现 k 的值域很大。但是递推的方式相同，我们把 z^{i-1} 也当作状态方程放进去转移，记作 g。那么就有：\begin{bmatrix}f_{i-1} &g_{i-1} \end{bmatrix} \times \begin{bmatrix} x & 0\\ -y & z \end{bmatrix}=\begin{bmatrix}f_{i} &g_{i} \end{bmatrix} 。直接矩阵快速幂优化能够做到 O(nm+\log k) 的时间复杂度。

P7577

发现性质题。因为 l 固定，r 连续的一些区间，F(l,r) 的值也是一定的。那么记 F(l,c)=x,F(l,d)=y，根据界值定理，F(l,c),F(l,c+1),\dots,F(l,d) 一定取遍了 [x,y] 中的所有数。那么 G(F(l,c),F(l,c+1),\dots,F(l,d))=y-x+1。

现在就好做了。考虑容斥，即 \le f 的答案减去 <e 的答案。我们需要维护 \sum\limits_{l=a}^{b}[F(l,d)-F(l,c)+1\le x]。求区间出现次数有一个很经典的 trick，记 pre_i 为最大的 j，使得 a_j=a_i\land j<i，没有记为 0。那么对于区间 [l,r]，一个数是第一次出现的当且仅当 pre_i <l。也就是说区间数的数量与 \sum\limits_{i=l}^{r} [pre_i<l] 相等。

则问题转化为：\sum\limits_{l=a}^{b}[\sum\limits_{i=c+1}^{d}[pre_i < l]\le x-1]。很显然的，\sum\limits_{i=c+1}^{d}[pre_i < l] 随 l 增大不降，故具有可二分性。那我们直接去二分，每次 check 一下是否可行就行了。求区间小于某个数的数量用主席树即可。该算法的时间复杂度为 O(n\log^2 n)。

存在 O(n\log n) 的主席树上二分的做法。

AT_arc107_d

好玩。

对于一个合法的序列，将其排序后一定形如：(\dots,\frac{1}{16},\frac{1}{8},\frac{1}{4},\frac{1}{2})。会发现，这个序列相当于在每个位置进行了若干次形如“将该位置的前缀整体除以 2”的操作。然后就好做了，定义状态函数 f_{i,j} 表示前 i 个数，和为 j 的方案数。那么对于这个数，有 2 种情况：

1. 不进行操作，f_{i,j}=f_{i,j}+f_{i-1,j-1}。

2. 进行若干次操作。因为没有次数限制，所以是个完全背包的形式。有：f_{i,j}=f_{i,j}+f_{i,j\times 2}。

   该算法的时间复杂度为 O(n^2)。

AT_joisc2016_h

注意到不正常的时限。考虑分块做法。

对于一个区间 [l,r] 与当前的 x。x 遍历完这个区间之后一定会成为 \max(\max\limits_{i=l}^{r}a_i,x)。看出这个不难。那么，我们对于每个块动态维护其最大值，就能得到 x 最终的值了。

现在考虑修改。记 j 为区间 [l_i,r_i] 中第一个比 x 大的位置。那么 [j,r_i] 一定程不降的形式，因为一但有一个 a_k >a_{k+1}，我们都会通过 x 将其排好。那么对于 [l_r,j) 中的值，能够保证 \forall k\in[l_i,j),a_k<a_j。因为 a_k\le x\land a_j >x。于是就好做了，我们能够通过维护前缀最小值得到 a_i 的值。形式化地，对于每次将最大值与 x 比较时，先将 x 加入队列。对于每个 i，将 a_i 加入队列。然后每次 a_i 的实际值为当前最小的值。

证明简单。如果 x 存在 x<a_j 的情况，那么 Max 将会被顶出来。如果不存在，那么 x 将会成为最后一个（这里的最后一个不一定是队列的最后一个，因为可能存在多个这样的 x）。

动态维护最大和最小值，使用优先队列即可。时间复杂度 O(q\sqrt{n}\log n)。9 秒足够了。

AT_arc104_d

好玩。考虑 DP。

对于一个平均数为 x 的和 \sum a_i，我们有：

不妨将所有选出来的数减去 x。那么就相当于在 [1-x,n-x] 中选数，使得和为 0。这里需要一点注意力。可以把它拆成三个区间：[1-x,-1],[0,0],[1,n-x]。发现负数与正数对称，即 [1-x,-1] 中凑成和为 -s 的方案数与 [1,x-1] 中凑成和为 s 的方案数相同。定义状态函数 f_{i,j} 表示使用 [1,i] 凑出和为 j 的方案数。则总的方案数就是 ((k+1)\times \sum f_{x-1,i}\times f_{n-x,i}) -1。

难点在于维护 f_{i,j}。有转移方程：f_{i,j}=\sum\limits_{w=0}^{k} f_{i-1,j-w \times i}。由于状态数是 n^2k 的，所以这样做的时间复杂度是 O(n^3k^2)。用前缀和优化可以做到 O(n^3k)。但是我现在不会，所以这题做了一半。

怎么能不会呢。这是一个下标为等差数列的求和，直接算就行了。时间复杂度 O(n^3k)。

P4093

以前做过。

记 mx_i 为 i 下标上的最大值，mi_i 为 i 下标上的最小值。定义状态函数 f_i 为前 i 个数中，i 必选的最长长度。那么有：f_i=\max\{f_j|mx_j\le a_i\land a_j \le mi_i\land j<i\}。这玩意是个三维偏序问题。但是不能使用 O(n\log n) 的容斥优化，原因简单。所以使用 CDQ 分治能够做到 O(n\log^2 n) 的复杂度。

P6163

难爆了。

考虑先去掉绝对值。这里 a_i 默认已排序。

那么有：

然后需要很多注意力。我们观察到，a_i 与 a_{n-i+1} 在某种关系下是对称的。形式化的，有：

也就是说，我们只需要让后半部分尽量小，前半部分尽量大，答案就不劣。难点在于构造。

这里给出结论：按照 l 从大到小选，r 从小到大从小到大选一定是最优的。接下来是证明：

对于一组 (l_i,r_j)。如果 l_i,r_j 这 2 条线段均没被用过，那么选择一定最优。如果 l_i 用过，r_j 没用过。那么因为 r_i\le r_j，所以 l_i \le r_j。且 l_j \le l_i，所以 l_j \le l_i \le r_i \le r_j。由于我们 a_i 默认升序,所以在这之后任意一个 i 和 j，我们都能取到相同的点。r_j 用过,l_i 没用过同理。而这样一定能够分配到一个 i' 和 j 匹配，且取到了相同的位置。于是这样选，直到第一次 l_i\le r_j 或有一个点选过了，后面的贡献就是 0 了。

化简一下，答案就是：2 \times \sum\limits_{i=1\land l_i > r_i}^{n} (n+1-2\times i)\times (l_i-r_i)。时间复杂度 O(n\log n)。

AT_arc147_c 与该题是同一题，不在赘述。

P11039

好题。

考虑到 T' 中任意两个关键点的 \operatorname{LCA} 都与 G 相同，不妨先将这些关键点的虚树建出来。记虚树上有 m 个节点，那么问题就转化为：将 n-m 个点插入虚树中，求最终生成树的数量。

现在对 T' 的树根进行分类讨论：

对于情况 1。那 n-m 个点可能会插入当前树上的边，也可能会直接与当前树上的点连接。考虑枚举插到边里面的点的数量，记为 x。因为每加一个点会多出来 1 条边，而一开始有 m-1 条边，所以第 i 个点能插在 m-1+i-1 条边中的任意一条里面。所以有方案数为：C_{n-m}^{x}\times (\prod\limits_{i=m-1}^{m-1+x-1}i)。

对于剩下的 n-m-x 个点，我们将当前的树 T' 看作 1 个大小为 m+x 的连通块，剩下的点看作 n-m-x 个大小为 1 的连通块。通过 Prüfer 序列，我们可以得到生成树的数量为：n^{(n-m-x+1)-2}\times (m+x)\times (\prod\limits_{i=2}^{n-m-x+1}1)。

那么，对于情况 1，生成树的数量即为：\sum\limits_{x=0}^{n-m} C_{n-m}^{x}\times (\prod\limits_{i=m-1}^{m-1+x-1}i)\times n^{(n-m-x+1)-2}\times (m+x)\times (\prod\limits_{i=2}^{n-m-x+1}1)。这里令当 x 为 n-m 时，后半部分结果为 1。

现在看情况 2。发现这实际上就相当于在 n-m 个点中选了 1 个点当虚树的新根，然后就变成情况 1 了。

该算法时间复杂度为 O(n\log n)\sim O(n)。

P11214

考虑对于 n 个 a_i,b_i，我们能够找到一个 k，使得：\forall i,a_i=0\lor a_i\ge k，\forall i,b_i=0\lor b_i\ge k。这样的话，我们就能找到最大的一个长度，使得这个长度内的任意一个数都有对应的序列 y 满足 |x_i-y_i| 相等。有方案数：k\times \prod\limits_{i=1}^{n}([a_i\ne 0]+[b_i\ne 0])。但是这样取了之后，可能还会有解，于是将所有 a_i,b_i 减去 k，继续计算。知道存在至少一个 i，有 a_i=0\land b_i=0 为止。使用 set 维护的时间复杂度为 O(n\log n)。

P11217

比较一眼，符合 CSP-S 的 T1。

考虑二分答案。因为每次都会使攻击翻倍，所以第 i 个整轮结束后，一共会受到 (2^{i}-1)\times \sum\limits_{j=1}^{n} a_j 的伤害。所以我们能够直接算出 youyou 进行了多少次整轮。然后剩下的生命值可能还可以继续战斗，二分最多能打到第几个垃圾桶即可。使用线段树维护单点修改，然后在线段树上进行二分可以做到 O(n\log n)。

P11218

我们记 fuc 为选出的连通块中，某一列只选了 1 行且这一列是 0,1 交错的数量。那么 yy 的最优方案显然是翻转这些列。那么对于当前选出来的连通块，其价值就是 cnt_1-cnt_0-2\times \min(m,fuc)。进行分类讨论：

对于情况 1，如果我们将 fuc 中的一列全选，其价值变化为：cnt_1-(cnt_0+1)-2\times (fuc-1)=cnt1-cnt_0-2\times fuc+1。发现此时价值不劣与不全选。所以此时我们就能将连通块中只选了一行的全部调整为两行都选。我们按照两行都是 0 的列将原序列分成若干段，其中每段都全选。那么合并相邻两段的代价就是 1。贪心即可。

对于情况 2，因为无论如何我们都需要减去 2\times m 的代价，所以可以将后面的看成定值。那么问题就变成了求 cnt_1-cnt_0 最大是多少。考虑 DP。定义状态函数 f_{i,0/1/2} 表示在前 i 列选，且第 i 列选了第 1 行，第 2 行或全选的最大价值。那么有：

那么最大的价值就是 \max\limits_{i=1}^{n}\max\limits_{j=0}^{2}f_{i,j} 了。该做法不需要考虑选出来的 fuc 是否大于 m。因为当选出来的 fuc \le m 时，一定不优于情况 1 的答案。则最终的答案就是两种情况中更大的一个价值了。时间复杂度 O(n)。

AT_joisc2016_j

注意力极强。赛时因为题面难懂就看番去了，故不会。

注意到，我们最优的方案显然是走最短路。也就是说，只要我们将 (r1,c1) 到 (r2,c2) 的最短路求出来，这题就解决了。

考虑最短路是什么形式的。记最短路依次经过的点的序列为 P。如果存在 P_i=P_j\land i<j，那么我们完全可以不要 (i,j] 这一段，直接从 P_i 到 P_{j+1}。所以，如果一条路径是最短的，一定不会经过同一个点两次。

有这个性质，这题就好做了。不难发现，题目中将经过的点设为不可走实际上没有任何用。那么考虑建图。对于点 (i,j) 要到相邻的点，其最少步数一定为 2，如果直接向相邻点移动之后直接停在相邻点除外。因为我们过去再回来，出发点已经不可走了，所以会停在那个点上。同时，我们再将一个点向四周移动所到达的点连一条边权为 1 的边。

接下来证明该建图的可行性。对于一个点 (x,y) 到 (x',y')，如果能够通过这些边直连，那么一定是最短路。如果不能，考虑到 (x,y) 这个点下一步只能向某个方向行走，再下一步要么折返要么继续朝其它地方走。其它地方走的情况 (x,y) 对其没有影响，只有折返时会停在 (x,y) 的一个四联通点上。所以连这种边可以保证正确性。由于点只能这么走，所以最短路一定会是这些边组成的路径。

建完边之后跑个最短路就行了。时间复杂度 O(hw\log hw)。

CF1733E

注意力极强。赛时因为只想到打表找规律就看番去了，故不会。

会发现，t 时刻是否有点在 (x,y) 相当于判断 t 时刻前经过 (x,y) 的点的数量是否比 t-1 时刻前经过 (x,y) 的点的数量多。因为如果有多的，那么多出来的显然只会在 t 时刻经过。

那么问题就转化为求有多少个点在 t 时刻前经过了 (x,y)。发现每个点产生的时刻不同，即对于每个时刻 t，每个点走过的路径长度 p_i 互不相同。又因为只会向下或者向右走，所以不可能存在合并的情况。那么，我们就可以将所有的点全部放在 (0,0)，然后让它们一起走，看有多少个点经过了 (x,y)。记 f_{i,j} 为经过 (i,j) 的点的数量。那么对于第奇数次经过，那些点会跑到 (i,j+1)，其它的点会跑到 (i+1,j)。即有 \lceil \frac{f_{i,j}}{2} \rceil 的点会到 (i,j+1)，\lfloor \frac{f_{i,j}}{2} \rfloor 的点会到 (i+1,j)。那么就可以 O(n^2) 转移了。

对于初始的点的数量，只有 p_i \ge x+y 的点才可能经过，所以 p_i <x+y 的点没有任何作用，即 t 时刻有用的点数为 t-x-y+1。时间复杂度 O(tn^2)。