2020-12-13~2021-01-13¶

CF1453F¶

题意¶

给定一个数列 $a_1,a_2, \cdots, a_n$，玩家需要从位置 $1$ 走到位置 $n$，在第 $i$ 个位置可以向后走 $[1,a_i]$ 步，如果 $a_i=0$ 就失败了，必须走到 $n$ 才算成功，问至少将几个 $a_i$ 重新设置为 $0$ 才能使得玩家从 $1$ 到 $n$ 的路径是唯一的，保证初始状态存在一种走到 $n$ 的方案。($2 \le n \le 3000$)

题解¶

首先有一个性质，如果玩家可以从 $1$ 走到 $n$，那么他必然可以经过任意一个点（其中某一步少走即可）。

因此，如果有多个 $j$ 满足 $j + a_j \ge i$ 那么必然有多种方式到达 $i$，从而对任意 $i$，至多有一个 $j$ 满足 $j + a_j \ge i$。

设 $f_{i,j}$ 是到达点 $i$ ，上一个点是 $k$，$k+a_k \le j$ 情况下的最少需要改变的数量，初始情况 $f_{1,1} = 0$，转移比较巧妙，对于每个 $i$，从 $i$ 到 $1$ 逆序枚举 $j$，同时维护一个变量 $\textit{cnt}$ 表示之前所有 $j + a_j \ge i$ 的数量，那么有转移： $$ f_{j,i-1} + \textit{cnt} \to f_{i,j+a_j}, f_{i,j+a_j+1}, \cdots, f_{i,n} $$ 只需转移到 $f_{i,j+a_j}$ 最后从 $i$ 到 $n$ 求一个前缀最小值即可，时间复杂度为 $O(n^2)$。

最终答案即为 $f_{n,n}$。

CF1455E¶

题意¶

给定二维平面上四个点，可以将它们水平或竖直移动，将它们移动到一个正方形的四角最少需要移动多少距离。

题解¶

全排列枚举四个点和四个角（左上、左下、右上、右下）的对应关系，那么左上左下的两个点（和右上右下的两个点）最终移动到的点的横坐标一定位于它们两者中间，此时可以算出水平边的边长范围；同样左上右上的两个点（和左下右下的两个点）最终移动到的点的纵坐标一定位于它们两者中间，此时可以算出竖直边的边长范围。如果两者有交集，则不需要额外移动；否则其中两个点需要额外移动中间差着的距离（这里可以使用 $\min(|\max_1-\min_2|,|\max_2-\min_1|)$ 来快速求得）。

上述过程的形象化图片可以参考这篇题解。

CF1455F¶

题意¶

$t$ 组数据，给定一个长度为 $n$ 的字符串，字符集为前 $k$ 个小写字母，依次选择原来第 $i$ 个字符选择如下操作：

按字典序循环左移一位。
按字典序循环右移一位。
和左侧字符交换。（如果有）
和右侧字符交换。（如果有）
不进行任何改动。

求最终得到的字典序最小的字符串。($1 \le t \le 1000$，$1 \le n \le 500$，$2 \le k \le 26$)

题解¶

数据范围比较小，直接设 $f_i$ 是前 $i$ 个字符都操作过后得到的长度为 $i$ 的字符串，使用 string 存储，考虑如下的转移：

直接通过循环位移或是不进行改动让当前这一位更小：$f_i + \min s_{i+1} \to f_{i+1}$。
向左移动一位：$f_{i}[1 \cdots i-1] + s_{i+1} + f_i[i] \to f_{i+1}$。
向右移动一位，下一位选择变为最小：$f_i + \min s_{i+2} + s_{i+1} \to f_{i+1}$。
向右移动一位，下一位向左移动一位：$f_{i}[1 \cdots i-1] + s_{i+2} + f_i[i] + s_{i+1}\to f_{i+1}$。

最终答案为 $f_n$，时间复杂度为 $O(n^2)$，这题很巧妙地使用 string 当作状态避开了各种复杂的讨论，官方题解指出因为每个状态变化的字符量为 $O(1)$，还可以使用主席树+哈希在 $O(n \log n)$ 时间内解决。（网上还有更快但是也更复杂的 $O(n)$ 做法）

CF1455G¶

题意¶

有一个变量 $x$，初始值为 $0$，给定 $n$ 行代码，由如下两种形式组成：

set $y$ $v$，将 $x$ 设为 $y$，或支付 $v$ 使 $x$ 的值不变。
if $y$ $\cdots$ end，如果 $x=y$ 就进入这个代码块，否则跳过。保证 if 和 end 一一对应。

必须保证任意时刻 $x$ 不为 $s$，求最小花费。($1 \le n \le 2 \cdot 10^5$，$0 \le y \le 2 \cdot 10^5$，$1 \le v \le 10^9$)

题解¶

设 $f_{i,j}$ 为执行完第 $i$ 行，$x=j$ 的最小花费，对于 set 语句，有：

\[ f_{i,j} = \begin{cases} \min \limits _{k=0} ^ {2 \cdot 10^5} f_{i-1,k}, &j=y \newline f_{i-1,j} + v, &j \ne y \end{cases} \]

一开始仅有 $f_{0,0} = 0$，其它均为 $+ \infty$，而每一行至多增加一个新的有意义的状态，因此总状态数是 $O(n)$ 的，只需维护一个全局的增量和全局最小值即可。

对于 if 语句，相当于一个新的子问题，初始状态为 $f_{i,y} = f_{i-1,y}$，其它均为 $+ \infty$。

对于 end 语句，需要将子问题和原问题进行合并，设 $p,q$ 分别为 if 前和 if 内最后一行的行数，有： $$ f_{i,j} = \begin{cases} f_{q,j}, &j=y \newline \min(f_{p,j},f_{q,j}), &j \ne y \end{cases} $$ 使用 map 存状态，multiset 存全局最小值，使用启发式合并，时间复杂度为 $O(n \log ^2 n)$。

CF1458A¶

题意¶

给定 $a_1,a_2,\cdots,a_n$ 和 $b_1,b_2,\cdots, b_m$，求 $\gcd(a_1+b_1,\cdots,a_n+b_1), \gcd(a_1+b_2,\cdots,a_n+b_2), \cdots, \gcd(a_1+b_m,\cdots,a_n+b_m)$。($1 \leq n, m \leq 2 \cdot 10^5$)

题解¶

利用 $\gcd$ 的结合律以及 $\gcd(x,y) = \gcd(x, y-x)$： $$ \begin{aligned} &\gcd(a_1+b_i,\cdots,a_{n-1}+b_i,a_n+b_i) \newline &=\gcd(a_1+b_i,\cdots,\gcd(a_{n-1}+b_i,a_n+b_i)) \newline &=\gcd(a_1+b_i,\cdots,\gcd(a_{n-1}+b_i,a_n+b_i - (a_{n-1}+b_i))) \newline &=\gcd(a_1+b_i,\cdots,\gcd(a_{n-1}+b_i,a_n-a_{n-1})) \newline &=\gcd(a_1+b_i,\cdots,a_{n-1}+b_i,a_n-a_{n-1}) \newline &=\gcd(a_1+b_i, a_2-a_1\cdots,a_{n-1}-a_{n-2},a_n-a_{n-1}) \newline \end{aligned} $$ 从而只需要求 $a$ 差分数组的 $\gcd$ ，再和 $a_1+b_i$ 求 $\gcd$ 即可。

CF1458C¶

题意¶

给定一个 $n \times n$ 的方阵，每一行每一列都是一个 $1$ 到 $n$ 的排列，进行 $m$ 次下列六种操作之一：

所有行循环左移。
所有行循环右移。
所有列循环上移。
所有列循环下移。
所有行从左到右由 $p_1,p_2,\cdots,p_n$ 变为 $q_1,q_2,\cdots,q_n$，其中 $p_{q_i} = i$ 对任意 $1 \leq i \leq n$ 成立。
所有列从上到下由 $p_1,p_2,\cdots,p_n$ 变为 $q_1,q_2,\cdots,q_n$，其中 $p_{q_i} = i$ 对任意 $1 \leq i \leq n$ 成立。

显然每种操作后每一行每一列依旧是一个 $1$ 到 $n$ 的排列，问最后得到的方阵是什么。($1 \leq n \leq 1000, 1 \leq m \leq 10^5$)

题解¶

如果只有前四种操作，只需维护随便一个点的位置即可还原整个方阵，因为方阵整体的相对位置都是不变的。

对于全部六种操作，可以将 $i$ 行 $j$ 列的元素 $a_{i,j}$ 视为三维空间中的一个点 $(i,j,a_{i,j})$，那么六种操作分别对应六种线性变换，将 $m$ 种操作的方阵乘起来，然后左乘行向量 $[i,j,a_{i,j},1]$ 即可得到该点的新位置 $[i',j',a'_{i,j},1]$。

这里将将所有值减去 $1$，方便模运算操作，所有运算均在模 $n$ 意义下：

所有行循环左移，所有点的 $j$ 变为 $(j-1) \bmod n$，对应方阵 $$ \begin{pmatrix} 1&0&0&0 \newline 0&1&0&0 \newline 0&0&1&0 \newline 0&n-1&0&1 \newline \end{pmatrix} $$
所有行循环右移，所有点的 $j$ 变为 $(j+1) \bmod n$，对应方阵 $$ \begin{pmatrix} 1&0&0&0 \newline 0&1&0&0 \newline 0&0&1&0 \newline 0&1&0&1 \newline \end{pmatrix} $$
所有列循环上移，所有点的 $i$ 变为 $(i-1) \bmod n$，对应方阵

$$ \begin{pmatrix} 1&0&0&0 \newline 0&1&0&0 \newline 0&0&1&0 \newline n-1&0&0&1 \newline \end{pmatrix} $$

所有列循环下移，所有点的 $i$ 变为 $(i+1) \bmod n$，对应方阵 $$ \begin{pmatrix} 1&0&0&0 \newline 0&1&0&0 \newline 0&0&1&0 \newline 1&0&0&1 \newline \end{pmatrix} $$
所有行从左到右由 $p_1,p_2,\cdots,p_n$ 变为 $q_1,q_2,\cdots,q_n$，其中 $p_{q_i} = i$ 对任意 $1 \leq i \leq n$ 成立，所有点的 $j$ 和 $a_{i,j}$ 互换，对应方阵 $$ \begin{pmatrix} 1&0&0&0 \newline 0&0&1&0 \newline 0&1&0&0 \newline 0&0&0&1 \newline \end{pmatrix} $$
所有列从上到下由 $p_1,p_2,\cdots,p_n$ 变为 $q_1,q_2,\cdots,q_n$，其中 $p_{q_i} = i$ 对任意 $1 \leq i \leq n$ 成立，所有点的 $i$ 和 $a_{i,j}$ 互换，对应方阵 $$ \begin{pmatrix} 0&0&1&0 \newline 0&1&0&0 \newline 1&0&0&0 \newline 0&0&0&1 \newline \end{pmatrix} $$

时间复杂度 $O(64m+n^2)$。

CF1461E¶

题意¶

一个饮水机，在 $t$ 天的时间内，每天一开始可以选择是否加 $y$ 升水，这一天会固定消耗 $x$ 升水，初始水量为 $k$，问是否存在一种方案使得水量任意时刻处于 $[l,r]$ 升内。($1 \le l \le k \le r \le 10^{18}; 1 \le t \le 10^{18}; 1 \le x \le 10^6; 1 \le y \le 10^{18}$)

题解¶

如果 $y \le x$，那么水量会一直不增且加水不会超上限，因此能加水就加水。当然第一天可能加水会超出限制，特判掉这个情况，之后算一下天数够不够即可。
如果 $y > x$，观察到 $x$ 的数据范围与众不同，可以从这里下手：最优情况一定是让水量减少到不能减少然后再加一次水，每次加水相当于改变水量模 $x$ 的值，因此如果出现循环那么就可以持续无限天，反之如果某一次加水超出上限就无法继续了。可以使用 map 记录，最多 ${10}^6$ 天就可以得到答案。需要注意的是，有可能最终不能无限循环，但是持续的天数 $\ge t$，那么也是可以的，需要每次循环减掉天数来判断。

CF1461F¶

题意¶

给定一个长度为 $n$ 的十进制串和 $\{+,-,\times\}$ 的一个子集 $S$，在 $n-1$ 个空隙加入 $S$ 中的符号使得最终表达式结果最大，从左往右运算，乘号优先级最高，加减法优先级相同。($1 \le n \le 10^5$)

题解¶

$|S| = 1$，没有选择。
$S = \{+,-\}$，全放加号即可。
$S = \{\times,-\}$，仔细想想可以发现最优方案是在第一个 $0$ 前面放减号，其它位置全部放乘号。
$\{+,\times \} \subseteq S$，首先 $0$ 左右必然是加号，先按 $0$ 分段；每一段的前缀 $1$ 和后缀 $1$ 也必然左右都是加号，对于中间的部分，有如下结论，如果 $$ \prod_{i=1}^na_i \ge 2n $$ 则最优方案是全部放乘号，证明见这里。

因此如果上式不成立，那么中间部分不为 $1$ 的数只有 $O(\log n)$ 个，可以使用如下的 dp：

设 $f_i$ 是只考虑前 $i$ 个数，且 $a_i$ 和 $a_{i+1}$ 符号为加号的最大值。
如果 $a_{i+1} = 1$，那么有 $f_i+1 \to f_{i+1}$。
如果一段数中间的符号均为乘号，那么其首尾必然都不是 $1$，因此有 $$ f_i + \prod_{k=i+1}^j a_k \to f_j $$ 其中 $j>i,a_j > 1$。
时间复杂度为 $O(n \log n)$。

CF1463F¶

题意¶

求元素个数最多的集合 $S$，满足：

$S \subseteq \{1, 2, \cdots, n\}$。
$S$ 中任意两个元素之差的绝对值不为 $x$ 也不为 $y$。

($1 \le n \le 10^9$，$1 \le x, y \le 22$)

题解¶

结论题，需要证明以下两个结论：

设 $p=x+y$，如果集合 $\{a_1,a_2, \cdots, a_m\}$ ($a_m - a_1 \le p$) 合法，那么集合 $\{a_1,a_2, \cdots, a_m, a_1 + p,a_2 + p, \cdots, a_m + p\} \cap \{1, 2, \dots, n\}$ 也合法。假设不合法，即存在 $a_i + p - a_j = x(y)$，从而有 $|a_i-a_j| = y(x)$，这与之前的集合合法矛盾。
存在一种最优方案可以分割为数段，每一段每个元素之差为 $p$，当然最后一段只有 $n \bmod p$ 个元素。大致感觉一下，可以把 $n$ 分成 $2\lfloor \dfrac{n}{p}\rfloor + 1$ 段，奇数段长度为 $n \bmod p$，偶数段长度为 $p - n \bmod p$，任意相邻两段之和为 $p$，然后就可以调整使得最优解符合上述条件。具体可以看题解证明，太复杂我爬了。

然后我们就可以设 $f_{i,j}$ 表示选到了第 $i$ 个数，前 $\max(x,y)$ 个数选择的状态为 $j$ 时集合数量最大值，然后进行状压 dp 即可，第 $i$ 个数的贡献为 $\lfloor \dfrac{n}{p}\rfloor + [i \le n \bmod p]$。

可以发现状压 dp 时不需要要记录前 $x+y$ 个数，因为它们差值够大，一定是合法的，这样复杂度降为 $O(\max(x,y)2^{\max(x,y)})$。

CF1464C¶

题意¶

给定一个由小写字母组成字符串 $S$，能否通过下面的方法令它的权值 $f(S) = T$。

对于单个字母，从 $0$ 开始标号，按 $\text{a}$ 到 $\text{z}$ 的顺序，第 $i$ 个字母的权值为 $2^i$。
对于多个字母，你可以任意选定 $1 \le m < |S|$，令 $f(S) = -f(S[1, m]) + f(S[m + 1, |S|])$。

($2 \leq n \leq 10^5$，$-10^{15} \leq T \leq 10^{15}$)

题解¶

最后一个字母的符号必为正，倒数第二个字母的符号必为负，其它字母符号任意。证明如下：

从倒数第二个字符开始，所有负号都可以直接扔掉，相当于单个字符+后缀的组合。遇到第一个正号时，不要扔掉它右边的第一个负号，而是将它和右边的负号结合组成一个前缀，视作该前缀+剩余后缀的组合，从而前缀的最后一个字母的符号变为正，倒数第二个字母的符号变为负，转化为一个递归的子问题。最终 $-+$ 的组合也是合法的，因此得证。

将 $T$ 减去最后两个字符对应的权值，剩下的字母先全部赋为正，然后从高位贪心将其变为负，看最后能不能让差变为 $0$。（差必须是偶数，因为将一个正的数变为负改变的必然是偶数）

CF1464E¶

题意¶

给定一个 DAG，一开始每个点都没有石子，不断循环下述过程：

随机一个 $[1, n + 1]$ 的整数 $x$：
如果 $x \le n$，那么给 $x$ 号点增加一个石子。
如果 $x = n + 1$，那么 Alice 和 Bob 开始玩游戏，Alice 先手，每人轮流将一个点上的石子移动到它的一个后继点，不能移动的人输掉游戏。游戏结束后终止这个循环过程。

求 Alice 获胜的概率。($1 \leq n \leq 10^5$，$0 \leq m \leq 10^5$)

题解¶

这个 DAG 其实就相当于 SG 函数所定义的有向图（推石子），我们可以求出每个点的 SG 函数值。

这里有一个结论：$m$ 条边构成的 DAG，每个点的 SG 函数值不超过 $\sqrt{2(m+1)}$。

Alice 获胜相当于每个石子所在点的 SG 函数值异或起来不为 $0$，本题中根据上述结论不会该值小于 $M = 512$，从而设 $f_i$ 是当前每个石子所在点的 SG 函数值异或起来为 $0$ 的时 Alice 获胜的概率，设 $\textit{cnt}_i$ 是 SG 函数值为 $i$ 的点的个数，那么有： $$ f_i = \frac{1}{n+1}\left([i \ne 0] + \sum_{j=0}^{M}f_{i \oplus j}\textit{cnt}_{j} \right) $$ 高斯消元即可，最终答案为 $f_0$ （一开始没有石子，异或值为 $0$），时间复杂度为 $O(M^3)$。

CF1466G¶

题意¶

给定长度为 $n$ 的字符串 $t$，以及字符串 $s_0$，定义 $s_{i+1} = s_i t_i s_i$，其中 $0 \le i < n$。给出 $q$ 个询问，每个询问给定非负整数 $k$ 和字符串 $w$，求 $w$ 在 $s_k$ 中的出现次数对 $10^9+7$ 取模的结果。

($1 \leq n,q \leq 10^5$，$1 \leq |s_0| \leq 100$，$|t| = n$，$0 \leq k \leq n$，$\sum|w| \le 10^6$)

题解¶

设 $f(n, w)$ 为 $w$ 在 $s_n$ 中的出现次数，$g(n,w)$ 为 $w$ 在 $s_n$ 中出现且包含中间那个字符（即 $t_{n-1}$）的次数。

对于每个 $w$，设 $k$ 是最小的满足 $|s_k| \ge w$ 的非负整数，如果不存在这样的 $k$ 显然答案为 $0$，否则答案为： $$ f(n, w) = f(k, w) \cdot 2^{n - k} + \sum_{i = k + 1}^n g(i, w) \cdot 2^{n - i} $$ 其中 $f(k, w) \cdot 2^{n - k}$ 可以直接使用哈希来判断，考虑后面的和式如何快速处理。

注意到，当 $i > k$ 时，对于所有 $t_{i-1}$ 相同的 $i$，它们的 $g(i, w)$ 也相同。因为 $|s_k| \ge w$，所以如果要包含 $t_{i-1}$，对出现次数有贡献的字符串永远是 $s_kt_{i-1}s_k$。

从而对每个字母可以预处理系数（即 $2^{n-i}$）的前缀和，而对于 $g(i,w)$，只需判断当 $w$ 的每一位是 $t_{i-1}$ 时，剩余的前后缀是否与 $s_k$ 的对应长度的后前缀相等即可，可以使用哈希来完成。

$\sum|s_k|$ 的数量级和 $\sum|w|$ 相同，从而总复杂度为 $O(\sum|w|+26n)$。如果字符集更大，可以再套一个数据结构使得总复杂度为 $O((\sum|w|+n)\log n)$。

CF1469F¶

题意¶

有 $n$ 条白链，第 $i$ 个长度为 $l_i$。一开始的树只有一个白点，每次操作可以将一个链的一个点接到当前树上的一个白点，同时这两个点会变黑。每条链只能用一次。问进行任意次操作后，树上第 $k$ 深的白点深度最浅是多少，或判断树上白点数量不可能超过 $k$。($1 \le n \le 2 \cdot 10^5$，$2 \le k \le 10^9$)

题解¶

每次操作一定是优先选最长的链的中间的节点放到最浅的点上，可以线段树维护每个深度的白点各有多少个，每次操作后查询第 $k$ 深的值，维护一个最小值，直到放完所有链。