2024暑假总结2

2024暑假总结（7.22-7.27）：

Day1（7.22）

今天请了学长zzh来讲杂题选讲，主要是一些偏技巧类的题目，一些我认为有意义的题目如下：

• CF1028G：一道外壳为交互题，实则是dp题的题目，需要注意 \(k\le x\) 这一条件，设dp状态 \(f_{i,j}\) 表示左端点为 \(i\)，用 \(j\) 次询问最多能询问到哪里，然后正常转移即可。
• P5163：这题首先用到了一个技巧，就是将询问倒序枚举，这样删边操作就变成了加边操作，然后又发现不能很好地维护强连通分量，于是考虑整体二分，每次加上一半的边，然后看哪些点在同一个边双里面，然后就可以做了。
• P6109：这题是一道很巧妙的题，因为求max不能差分，所以考虑用分治算法。每次有一个mid，然后处理分治区间包含的询问，每次从mid开始依次往两边加，维护区间历史最大值即可。

下午是hdu多校acm，感觉里面的题出的中规中矩，做了四道签到题之后，我和drk一人做了两道比较难的题，最终以8道题排名51。

Day2（7.23）

今天上午是考试。首先拿到题之后先去看t1，先是写了个暴力找规律，发现答案就是 \(n\times 2\)，然后证明了一下就过了。t2是一道类似埃及分数的题，但仔细想想似乎跟迭代加深没有一点关系，于是考虑改变枚举顺序，质因子较大的放在前面，然后就过了50分的暴力，t3是一道跑很多遍网络流的模板，但有个图完全随机的性质，但是我考场上还是没有想到合适的做法，只拿了30分的暴力。t4就是个dp，打了50分的暴力就没管了，最后检查了一下四篇代码，得分100+50+30+50=230。居然t2我是唯一有分的，并且拿了rk1。

下午听评讲+讲课，t2是在我的代码上加一个背包，相当于把两个做法拼起来了，t3要写一个最普通的dfs网络流，因为图随机所以跑很快，而不应该写dinic。t4是容斥+dp，是一个数学题。

讲课还是杂题选讲，放一道有意思的：

• CF1188D：本题如果正常的dp的话是 \(O(2^n\log n)\) 的，但是有个性质，就是第 \(i\) 位能进位的一定是前面的数更大的，即是排序后的一个后缀，所以只需要记录一个数来表示哪些会进位即可

Day3-4（7.24-7.25）

这两天请了金牌gzy来讲dp，还是放一些有意义的题目：

• uoj37：这道题是强连通分量计数，具体做法是设 \(f_i\) 表示 \(i\) 个点形成一整个强连通分量的数量，\(g_i,h_i\) 表示形成奇数/偶数个强连通分量的情况，\(g,h\) 是很好递推的。求 \(f\) 的话首先容斥，变为总数减缩点后为 DAG 的数量，这可以沿用 DAG 计数的思路，即枚举所有入度为 \(0\) 的点，做一个二项式反演即可。

• CF1608F：这道题我写了一篇题解，就直接复制过来：

首先还是转化为前 \(i\) 个数的 \(mex\) 在区间 \([l_i,r_i]\) 内。

我们用 dp 数组 \(f_{i,x,c}\) 表示处理到了第 \(i\) 个数，当前的 mex 为 \(x\)，大于 mex 一共有 \(c\) 个不同的数。这里我们并不关心大于 mex 的数具体是哪些，而只关心有多少个，因为只要满足大于 mex 一共有 \(c\) 个不同的数，方案数都是一样的，我们只需要记录这个一样的方案数即可。注意这里钦定了这 \(c\) 个数的顺序，即这 \(c\) 个数是有序的（看不懂的话可以根据下面的转移来理解）。

根据定义，考虑有哪些方式能转移到 \(f_{i,x,c}\)：

• 这个位置填了一个之前已经出现过的数，这样的数共有 \(x+c\) 个，所以转移为 \(f_{i-1,x,c}*(x+c)\rightarrow f_{i,j,k}\)
• 这个位置填了大于 mex 且之前没有出现过的数，那肯定是由 \(f_{i,x,c-1}\) 转移过来，因为原先有 \(c-1\) 个数，而数是有序的，所以新加的数与这 \(c-1\) 个数的相对顺序共有 \(c\) 种，所以转移为 \(f_{i,x,c-1}*c\rightarrow f_{i,j,k}\)
• 第三种情况也是本题的核心，即这个位置填了 mex，这样子我们并不知道有哪些状态能更新到。这时就需要辅助数组 \(g\)，用 \(g_{i,x,c}\) 表示填到了第 \(i\) 个数，小于 \(x\) 的数都出现过，大于等于 \(x\) 共有 \(c\) 个不同的数。

这样 \(g\) 怎么辅助数组 \(f\) 来转移呢？具体流程为，先处理前两个转移，同时更新数组 \(g\)，然后再用 \(g\) 来更新 \(f\) 的第三个转移。

• 对于 \(f\) 到 \(g\) 的转移，即这个位置填了 mex，显然有 \(f_{i,x,c}\rightarrow g_{i,x+1,c}\)
• 对于 \(g\) 到 \(f\) 的转移，那么对 \(g_{i,x,c}\) 分两种情况，即是否出现了 \(x\) 这个数。如果出现了，那么应该转移 \(g_{i,x,c}\rightarrow g_{i,x+1,c-1}\)，如果没有出现，那么应该转移 \(g_{i,x,c} \rightarrow f_{i,x,c}\)

最后统计答案，对于 \(f_{n,x,c}\)，由于我们没有关心这 \(c\) 个数具体是啥，所以要在剩下的 \(n-x\) 个数中选 \(c\) 个，因为已经钦定了 \(c\) 个数的顺序，所以 \(f_{n,x,c}\) 对答案的贡献为 \(f_{n,x,c}*\binom{n-x}{c}\)

• CF1616H：这题如果正常去做dp的话是行不通的，因为两个子树会互相关联，这时候就一定要大胆猜测：用 \(f_{i,j}\) 表示在子树 \(i,j\) 里面选若干个数满足条件的方案数，转移就枚举当前这一位是啥分类讨论，然后你惊奇的发现互相关联的 \((i,j)\) 一共只有 \(n\log n\) 种，然后就可以做了。

• CF1874D：首先这道题需要先做一个数学问题，将题目中的期望转化为关于 \(a_i\) 的式子，然后你现在需要让这个结果最小，于是就有了一个很简单的 \(o(n^2)\) 的 dp。简单分析一下可得 \(a_i\) 是单调不降的，那么每一个 \(a_i\) 就是有上界的了，每个 \(a_i\) 的上界加起来是调和级数，即 \(O(n\log n)\)，于是就将时间复杂度优化到了 \(O(n^2\log n)\)

Day5-6（7.26-27）

这两天就主要是复习了，我把前面讲的杂题，dp题，和相关算法，比如整体二分，cdq分治，都写了一下，感觉收获还是比较大的。

总结：

对于dp题，首先肯定是想一个暴力，比正解复杂度高很多也没有关系，然后一层一层地优化，具体优化方法有：数据结构优化，看每一维地上下界之类的，看总状态数一共有多少。然后如果设一个数组表示不出来，可以用一个辅助数组来转移。对于dp的技巧，主要还是要多刷题才能掌握。