2024.4 刷题笔记
CF1870E
题意
对长度为 $n(n\le 5000)$ 的数组 $a(a_i\in [0,n])$，选择若干不重合的子段分别计算 MEX 再异或起来，求该异或值的最大值。
做法
- 很容易想到朴素的 dp 做法：令 $dp(i,j)$ 表示考虑前 $i$ 个元素能否得到异或值 $j$，对于每个状态从前缀所有元素转移，时间复杂度 $O(n^3)$
- 考虑到 MEX 相同的段中只有极小子段用于转移有意义，可以发现极小子段只有 $O(n)$ 个，于是只要预处理出有意义的极小子段再 $O(n^2)$ 转移即可
CF1884D
题意
给定长度为 $n(n\le 10^6)$ 的数组 $a(1\le a_i\le n)$，求不存在 $x\in a$ 使得 $x|a_i$ 且 $x|a_j$ 且 $i<j$ 的 $(i,j)$ 对数。
做法
- 计算 $gcd(a_i,a_j)=x$ 的 $(i,j)$ 对数 $dp(x)$
- 对于所有没有因子在 $a$ 中的数 u，计算 $\sum_u dp(u)$，即为答案
CF1861E
题意
定义序列 $a$ 最多包含 $cost_a$ 个不重叠的子段，满足每个子段都是 $[1,k]$ 的排列。对于所有长度为 $n(n\le 4000)$ 且仅包含 $[1,k](k\le 4000)$ 的序列，求它们 $cost$ 的和。
做法
- 计算 cost 的策略是从左到右扫描长度为 $k$ 的窗口，将每次最先出现的 k 排列计入答案
- 考虑统计所有序列中每个位置上被计入答案的 k 排列个数。以 $i$ 位置结尾的 k 排列被计入答案的前提是以 $[i-k+1,i-1]$ 结尾的子段都没有被计入答案
- 定义 $dp_i$ 表示在 i 位置被计入答案的 k 排列个数，则按照上述策略，$dp_i=k^{i-k}\cdot k!-\sum_{j=i-k+1}^{i-1} dp_j\cdot (i-j)!$，即所有 i 位置为 k 排列的序列个数减去以 $[i-k+1,i-1]$ 结尾的子段被计入答案的序列个数
- 答案为 $\sum_{i=k}^{n} dp_i\cdot k^{n-i}$
CF895C
题意
给定长度为 $n(n\le 10^5)$ 的序列 $a(1\le a_i\le 70)$，求序列有多少个非空子集满足所有元素的积是一个完全平方数。
做法
- 乘积为完全平方数等价于所有质因子出现的次数都为偶数，而 $70$ 以内的质数非常少，可以进行状态压缩，转换为线性基经典问题，即求一组向量和为 0 的线性组合个数
- $n$ 个向量的集合 $s$ 中和为 0 的线性组合个数为 $2^{n-rank(s)}$，其中包含一个空集，需要去掉
CF1896D
题意
给定一个长度为 $n(n\le 10^5)$ 只包含 $1$ 和 $2$ 的数组以及 $q(q\le 10^5)$ 个询问，每个询问要么对数组单点修改，要么求是否存在和为 $s$ 的子数组。
做法
- 观察到：对于一个子数组，若其左边或右边为 $2$ 则可以删去使和减少 $2$，否则可以同时去掉两边的 $1$ 同样使和减少 $2$。因此只要和为 $sum$ 的子数组存在，和为 $sum-2,sum-4,…$ 的子数组就一定也存在
- 只需要找到与询问的 $sum$ 奇偶性相同且和最大的子数组即可判断。这可以通过维护所有为 $1$ 的位置来完成
CF1913D
题意
给定所有元素互不相同的、长度为 $n(n\le 3\cdot 10^5)$ 的序列 $p$ 和一种操作：
- 选择 $p$ 中一个子段，删除除了最小元素以外的所有元素
求进行任意次操作可以得到的所有结果序列的种类数。
做法
- 等价于求合法子序列个数，因此考虑动态规划：用 $dp_i$ 表示对前缀 $i$ 进行操作能得到且不删除第 $i$ 个元素的子序列个数
- 对于 $dp_i$ 考虑从左边哪些位置转移合法：
- 若 $p_i$ 左边没有更小的数，则 $[0,i)$ 都合法
- 否则，记 $l(i)$ 为 $p_i$ 左边第一个比 $p_i$ 小的元素的位置，合法的转移位置有 $[l(i),i)$ 以及 $l(l(i)),l(l(l(i))),…$
- 需要注意：情况 1 中位置 $0$ 合法，情况 2 中位置 $0$ 不合法
- 在从左到右扫描的过程中，记录 $dp_i$ 的前缀和以及通过 $l$ 关系形成的链上的 dp 值的前缀和，就可以做到 $O(1)$ 转移
- 最终找到所有满足“比自己右边所有元素都大”的 $p_i$ 的位置 $i$，对这些位置的 dp 值求和即为答案
CF1922D
题意
给定一排 $n(n\le 3\cdot 10^5)$ 个怪物，每个怪物的伤害和一次性最多能接受的伤害分别为 $a_i$ 和 $d_i$。每个回合，所有怪物会先对左边和右边第一个存活的怪物造成伤害，然后受到他们的伤害。问前 $n$ 个回合中分别有多少个怪物死亡。
做法
- 在某一回合中，若某怪物自己没有死亡，且相邻的两个怪物也没有死亡，则在下一回合中不需要考虑它。换句话说，每个回合只需要检查上个回合死亡的怪物的相邻怪物即可
- 整个过程中最多有 $n$ 个怪物死亡，每个怪物死亡时，下回合需要考虑其相邻的两个怪物；同时初始时需要考虑所有 $n$ 个怪物。因此总共需要考虑的次数为 $O(3n)$
- 用 set 维护当前活着的怪物可以方便地找到每个怪物的相邻怪物
CF1942D
题意
有一个包含 $n(n\le 10^3)$ 格的条带，可以任选格子涂上颜色。对于 $2^n$ 种选择中的一种，其对应的得分是 $a_{x_1,x_2}+a_{x_3,x_4}+…$，其中 $[x_1,x_2],[x_3,x_4],…$ 是最大连续涂色段。求得分最大的 $k(k\le 5\times 10^3)$ 种选择的得分。
做法
- 考虑动态规划，$dp_i$ 表示使用了前 $i$ 个格子的前 $k$ 大列表，则 $dp_i$ 可以从 $dp_{-1},dp_0,…,dp_{i-2}$ 处转移
- 按照上述想法如果直接暴力转移复杂度高达 $O(n^2k)$，需要优化。如果每个 $dp$ 列表都是降序的，新的 $dp_i$ 一定会从所有 $dp_j$ 的前缀转移来，且所有前缀的总长只有 $O(k)$ 级别。换句话说就是对这些列表进行归并，且只归并前 $k$ 个即可。这一过程可以借助优先队列实现，队列中的每个结点记录 $(idx,pos)$ 信息，代表从 $dp_{idx}$ 的第 $pos$ 大数进行转移
CF1957E
题意
回答 $t(t\le 10^5)$ 个询问，每次询问给出 $n(n\le 10^6)$，求 $\sum_{i=1}^{n}\sum_{j=1}^{i}\left(\frac{i!}{(i-j)!\cdot j} \text{ mod } j\right)$
做法
- 观察式子得 $\frac{i!}{(i-j)!\cdot j} \text{ mod } j=\frac{i\cdot (i-1)\cdot(i-2)\cdot\ldots\cdot(i-j+1)}{j}\text{ mod } j=(j-1)!\cdot\lfloor\frac{i}{j}\rfloor\text{ mod }j$
- 除了质数和 $4$ 以外，其他数 $j$ 都可以整除 $(j-1)!$，即满足 $(j-1)!\cdot\lfloor\frac{i}{j}\rfloor\text{ mod }j=0$
- 对于质数，由威尔逊定理，$(j-1)!\cdot\lfloor\frac{i}{j}\rfloor\text{ mod }j=(j-1)\cdot\lfloor\frac{i}{j}\rfloor\text{ mod }j$
- 用一个数组记录 $\sum_{j=1}^{i}\left(\frac{i!}{(i-j)!\cdot j} \text{ mod } j\right)$，枚举质数 $j$ 对数组的差分进行贡献，最终答案为数组的前缀和
威尔逊定理：对于质数 $p$，有 $(p-1)!+1\equiv 0\text{ mod }p$.
CF1954E
题意
已知序列 $a(a_i\le10^5)$ 代表 $n(n\le 10^5)$ 个怪物的生命值。每次链式攻击可以选择一个存活的怪物造成 $k$ 点伤害并传递：当一个怪物受到伤害时，相邻的存活的怪物也会受到同样的伤害。求对于所有 $k\in[1,\max(a)]$，最少要进行多少次链式攻击才能消灭所有怪物。
做法
- 对于固定的 $k$，显然答案即 $\sum_i \max(0,\lceil \frac{a_i}{k}\rceil-\lceil \frac{a_{i-1}}{k}\rceil)$
- 考虑数论分块，$\lceil \frac{a_i}{k}\rceil$ 的取值实际上只有 $O(\log a_i)$ 种。可以枚举 $a$ 的相邻元素计算对答案数组区间的贡献，因为 $\lceil \frac{a_i}{k}\rceil$ 和 $\lceil \frac{a_{i-1}}{k}\rceil$ 的取值一共也只有 $O(\log{\max(a_{i-1},a_i)})$ 种。即将 $k$ 的分布区间 $[1,\max(a)]$ 划分为 $O(\log{\max(a_{i-1},a_i)})$ 段分别计算贡献
- 数论分块通常是向下取整的，即根据 $\lfloor\frac{x}{i}\rfloor$ 的结果分块，但此处需要向上取整的分块，可以利用 $\lceil \frac{x}{i}\rceil=\lfloor\frac{x+i-1}{i}\rfloor=\lfloor\frac{x-1}{i}\rfloor+1$ 的性质转换为 $x-1$ 的向下取整分块
2024.4 刷题笔记