2024.9-2024.10 刷题笔记
CF2013D
题意
给定一个长度为 $n(n\le 2\cdot 10^5)$ 的序列 $a(1\le a_i\le 10^{12})$ 和一种操作：
- 选定任意 $i,j(i<j)$，使得 $a_i$ 减 $1$，$a_j$ 加 $1$
求任意次操作后可能的极差 $\max(a)-\min(a)$ 最小是多少。
做法
- 经典模型。最小化极差的方法是从右向左枚举每个数，使每个数尽可能向右填平右方的最小值。可以证明这样是最优的。
- 根据上述贪心策略，枚举过程中后缀始终会呈单调递增状，因此可以用单调栈来维护后缀中的段。
ARC166C
题意
给定一个 $n\times m(n,m\le 10^6)$ 的网格，可以进行任意次如下两种操作：
- 选择一个左边和上边还未染色的格子，将其左边和上边染色
- 选择一个右边和下边还未染色的格子，将其右边和下边染色
求最终可能得到的网格染色方案有多少种。
做法
- 考虑可能相互冲突的边，发现这些边组合起来都呈对角方向阶梯状。
- 根据上述观察，将所有边按照所在对角线分组。此时每组的染色方案之间互不干扰，且组内的方案数只与对角线长度有关。
- 预处理出所有长度对角线的染色方案数以及前缀积，再配合快速幂即可 $O(\log\max(n,m))$ 算出答案
AGC059B
题意
有 $n(n\le 2\cdot 10^5)$ 个不同颜色的小球围成一个环，每个小球的颜色为 $c_i$，现在可以任意重新排序这些小球，求使得满足“存在颜色为 $x,y$ 的相邻小球且 $x<y$”的颜色对 $(x,y)$ 最少的一组排序方案。
做法
- 假设共有 $m$ 种颜色的小球，容易发现只要递增排序就可以得到只有 $m$ 对颜色对的方案，而最优情况下颜色对可以只有 $m-1$ 对。
- 将所有颜色对视为边，$m$ 对颜色对的方案即一个环，$m-1$ 对颜色对的方案即一棵树。
- 构造一棵树的要求是所有结点对应颜色的小球至少要有结点的度数个，因此能构造出树的数据满足 $n\ge 2m-2$。
AGC057B
题意
给定一个长度为 $n(n\le 10^5)$ 的数组 $a$ 和一种操作：
- 选定 $i(1\le i\le n)$，将 $a_i$ 替换为 $[2a_i,2a_i+X]$ 中的任意一个数
求任意次操作后可能的极差 $\max(a)-\min(a)$ 最小是多少。
做法
- 将 $a_i$ 进行 $k$ 次操作可以得到的范围为 $[2^k a_i,2^k a_i+(2^k-1)X]$。
- 假设两个数相差 $d$，则将两个数分别进行一次操作，差可以变为 $d’=2d-X$。因此若 $d<X$，则两个数可以在若干次操作后相等，否则差距只增不减。由此可以分两种情况讨论：要么数组极差最终可以为 $0$，要么数组中至少有一个数不进行操作。
- 假设数组中最大的数为 $a_x$，则在第二种情况下 $a_x$ 一定不操作。证明：假设 $a_x$ 进行了操作，此时存在一个数 $a_y\le a_x$ 且 $a_y$ 不操作，这种方案一定不如 $a_y$ 再进行一次操作。
- 两种情况的讨论都可以从 $a_x$ 不操作的最优方案出发进行：若 $a_x$ 不操作时能达到的最小极差 $d_m<X$，则答案为 $0$；否则答案为 $d_m$。
- 对所有 $a_i<a_x$，求出 $a_i$ 经过操作后从 $a_x$ 两侧最接近 $a_x$ 的两个值 $a_{i1}\le a_x\le a_{i2}$，现在的任务是为所有 $a_i$ 挑选一个值使得极差最小。可以先将所有 $a_i$ 置为 $a_{i1}$，然后每次将最小的数向上滚动，在这个过程中记录最小极差即可。具体实现方法是将所有值对排序，按照排序顺序滚动。
CF2033F
题意
求斐波那契数列中第 $n(n\le 10^{18})$ 个 $k(k\le 10^6)$ 的倍数的位置。
做法
- 将整个斐波那契数列对 $k$ 取模以后，即求第 $n$ 个 $0$ 的位置。记取模后的数列为 $f(i)$，假设第一次出现 $0$ 的位置为 $x$，且 $f(x-1)=y$，则 $f(x+1)=f(x+2)=y$，因此发现数列有周期性质 $f(i+x)\equiv f(i)\cdot y\bmod k$。
- 由于斐波那契数列中相邻两个数辗转相减会得到 $1$，可知相邻的数互质，因此 $y$ 与 $k$ 互质，并且有 $f(i)=0$ 当且仅当 $f(i-x)=0$。这意味着 $0$ 以 $x$ 为周期出现。
- 由以上分析，本题答案为 $nx$。实际上 $x\in O(k)$，可以暴力找到，这是一个数学结论，也可以打表发现。
- 斐波那契数列有很多特殊的性质，这里举两例：
- 模 $k$ 意义下，$0$ 的周期上界为 $2k$，数列的周期（皮萨诺周期）上界为 $6k$
- 斐波那契数列最大公约数定理：$\gcd(f_i,f_j)=f_{\gcd(i,j)}$
QOJ9435
题意
有 $T(T\le 5000)$ 个询问，每个询问给定 $n(n\le 10^9)$，求由大小写英文字母构成、长度为 $n$ 且同时包含子序列“npcapc”和“NPCAPC”的字符串有多少种。
做法
- 若 $n$ 较小，通常考虑 DP：记 $dp(i,j,k)$ 表示长度为 $i$ 且包含“npcapc”的前缀 $j$ 和“NPCAPC”的前缀 $k$ 的字符串种类数。但此时 $n$ 较大，而转移方程又是简单的求和，可以考虑矩阵快速幂。
- 将后两维状态展开成一维，共有 $49$ 种状态，可以写出 $49\times 49$ 的状态转移矩阵。由于矩阵较大，传统的快速幂在多测下时间复杂度 $O(49^3T\log n)$ 会超时，需要预处理出转移矩阵的 $2^k$ 次幂，然后使用 $O(a^2)$ 的向量-矩阵乘法替代 $O(a^3)$ 的矩阵-矩阵乘法，时间复杂度 $O(49^2T\log n)$
QOJ9442
题意
有 $n(n\le 2\times 10^5)$ 盏灯，试图打开第 $i$ 盏灯需要花费 $t_i$ 时间，且只有 $\frac{a_i}{b_i}$ 的概率打开成功，剩下 $1-\frac{a_i}{b_i}$ 的概率会关闭所有已打开的灯。求使得所有灯打开需要的最小期望时间。
做法
- 假设已经排好最优的顺序，剩下的就是一个经典的概率问题模型。记开启前 $i$ 盏灯需要的期望时间为 $f_i$，则 $f_i=f_{i-1}+t_i+(1-\frac{a_i}{b_i})f_i$，整理得 $f_i=\frac{b_i}{a_i}(f_{i-1}+t_i)$。
- 问题只剩下如何排序可以使得答案最优。由于递推无后效性，可以比较交换相邻项前后的答案：假设对一种排序交换第 $i$ 项和第 $i+1$ 项，计算交换前后的 $f_{i+1}$，再令 $f_{i+1}<f_{i+1}’$，可以得到只与 $a_i,b_i,t_i,a_{i+1},b_{i+1},t_{i+1}$ 有关的交换欠优条件，根据该条件进行排序即可。
2024.9-2024.10 刷题笔记