Contest and VP 记录

NKL丶 · 2022-07-25 15:40:12 · 个人记录

\mathfrak{Different \quad Color}：

\color{blue}\text{已完成}

\color{red}\text{未完成}

\color{gray}\text{已完成，待完善}

\color{red}\texttt{ARC 125} （VP）

赛时：\color{blue}\text{ABCD}

赛后：\color{red}\text{EF}

A：\texttt{Dial Up}

题意：给出一个长度为 N 只含 0、1 的序列 a 和一个长度为 M 目标序列 T，现有 1 个空序列 b，进行若干次操作，每次可以做出如下选择：

• 1、将 a_1 移至序列 a 的末尾
• 2、将 a_N 移至序列 a 的开头
• 3、将 a_1 添至序列 b 的末尾

问要使序列 b 与序列 T 相同的最小操作次数（若不能做到则输出 -1 ）。（1 \leq N,M \leq 2 \times 10^5）

分析：对于目标序列 T，我们按位匹配。考虑到序列内只有 0、1，不难发现，除了在第一次失配时我们需要通过移动多次使重新匹配，其余我们都只需要进行一次操作 3，或者额外进行一次操作 1 或 2 使当前位重新匹配。

因此我们只需要考虑 a_1 取反后对应的数在原数列最靠左或最靠右的位置，随后用 \mathcal{O}(M) 的时间复杂度完成计算。

B：\texttt{Squares}

题意：给出一个整数 N，对于一个数对 (X,Y) （0 \leq X,Y \leq N），若 \sqrt{X^2-Y} 为整数，则称数对 (X,Y) 是合法的。

问合法数对的数量，结果对质数取模。(1 \leq N \leq 10^{12})

分析：若数对 (X,Y) 是合法的，不妨令 \sqrt{X^2-Y} = K，则易知 (X+K)(X-K)=Y。

我们设 X+K=s、X-K=d，显然有 d \leq \sqrt{N} \leq s，所以枚举 d 进行统计即可。

C：\texttt{LIS to Original Sequence}

题意：给出一个长度为 K 的上升序列 A，构造出一个长度为 N 的字典序最小的排列，使得 A 是该排列的LIS（若原排列有多个LIS且 A 为其中之一也是合法的）。（1 \leq K \leq N \leq 2 \times 10^5，1 \leq A_i \leq N）

分析：考虑贪心。

不妨令 A 的补集为 B ，对于每个 A_i，我们都在 B 中寻找未被填入的小于当前 A_i 的数（若没有则跳过），在最终序列的 A_i 后加入这个数，可以证明此时是符合题意的字典序最小的方案。

注意特殊处理 A_K，倒序输出所有尚未加入最终序列的数字。（包括在 B 中的数）

D：\texttt{Unique Subsequence}

题意：给出一个长度为 N 的序列 A，求只出现过一次的子序列的数量，结果对质数取模。（1 \leq N \leq 2 \times 10^5，1 \leq A_i \leq N）

分析：

我们通过观察可知，对于第 x 位而言，合法的以它为结尾的子序列都可以从先前某些合法序列推出。

所以考虑 DP，设 f_x 表示到了第 x 位时以 A_x 结尾的子序列的数量。

通过分析性质，可以发现对于第 i 位而言，若在它之前 A_i 已经重复出现过，不妨令其位置为 lst，那么之前以 A_{lst} 结尾的所有子序列均不合法。

则可以得出转移方程： f_x = \sum\limits^{x-1}_{i=lst}f_i，因此记录下所有数最近一次出现的位置，使用树状数组维护区间和，同时单点修改清除 f_{lst} 的数据即可。

\color{blue}\texttt{CF 1699(div 2)} （VP）

赛时：\color{blue}\text{ABC}

赛后：\color{blue}\text{DE}

A：\texttt{The Third Three Number Problem}

题意：给定一整数 n，找出任意一组数 (a,b,c)，使得 (a\ xor\ b)+(a\ xor\ c)+(b\ xor\ c)=n，若无解输出 -1。（1\leq n,a,b,c \leq 10^9）

分析：我们按位考虑。对于每一位而言，我们枚举可能的 01 情况，可以得到如下的结果

tips:a,b,c不分先后顺序
a,b,c    result
0,0,0->    00
0,0,1->    10
0,1,1->    10
1,1,1->    00

可以发现，对于由低到高第 i 位而言，它只能对 i+1 位有贡献，所以假如 n 的第 0 位为 1（即 n 是奇数）即无解。

因此我们二进制下逐位分解 n，若此位为 1 则将答案中这一位设为 0,0,1 的形式，反之则设为 1,1,1 的形式即可。

B：\texttt{Almost Ternary Matrix}

题意：给定整数 n,m，求一个 01 数组，使得每一元素周围有且仅有 2 个数与其不同。（1\leq n,m \leq 50）

分析：规律题，通过观察可得最终的数组一定可以仅通过如下单元组形成：

0，1
1，0

加上一些旋转或者对称的操作即可。

C：\texttt{The Third Problem}

题意：给定一个从0开始的排列 S，定义两个排列是相似的，当且仅当二者所有的子序列的补集的最小值相等。

问与 S 相似的排列数量，结果对质数取模。（1 \leq |S| \leq10^5）

分析：我们按照区间来考虑这个问题，假设区间 S_l \sim S_r 是我们目前已处理的合法区间。即数字 0-k 均在区间内，则我们现在考虑原排列中 k+1 的位置。

• 若数字 k+1 在区间内，则此时相似的排列中 k+1 可选的位置共有 r-l+1-k 种情况。
• 反之则更新目前的区间。

容易发现这是乘法原理，第一种情况对答案的贡献即为 r-l+1-k ，第二种对答案的贡献为1。

D：\texttt{Almost Triple Deletions}（赛后调出）

题意：给定一个数列 S，现对其进行若干次操作，每次操作将相邻两个不相等的数从数列中删去，其余数字相对次序不变，问在操作过后，若数列里仅剩同一种数字，数列长度最大为多少。（1 \leq S_i \leq |S| \leq 5 \times 10^3）

分析：首先，对于一个序列 l，倘若其能被完全删去，不难发现如下性质：

• 序列内众数的出现次数不应超过 \frac{|l|}{2}。

我们发现 S 的长度较小，考虑 \mathcal{O}(N^2) 的线性dp。

定义 f[i] 表示最终数列以第 i 位为结尾时的数列长度，易知枚举断点时仅能从开头或者与 S_i 相同的位转移，同时需要满足断点与当前点之间可以完全删去。

此时复杂度为 \mathcal{O}(N^2)，发现若枚举断点时暴力判断是否合法，则会使复杂度乘上一个 N，因此我们可以进行预处理，提前处理每段序列是否能被删去即可。

E：\texttt{Three Days Grace}（赛后写出）

题意：给出一个大小为 n 的多重集 S，现对其进行若干次操作，每次操作可选择其中一个元素 S_i，将其分解为 p \times q 的形式，然后将 S_i 弹出，加入 p 和 q。问最终多重集内元素的极差的最小值。（1 \leq n \leq 10^6,1 \leq S_i \leq m\leq 5 \times 10^6）

分析：首先易知多重集内的重复元素对答案无影响，可先去重。

由于极差与元素的最大值、最小值有关，我们每次枚举最小值，调整最大值来进行计算。

设 f_{minn,i} 表示当目前最小值为 minn 时将 i 分解后可得最大因子的最小值，不难发现我们最终的答案就是 \max\limits_{minn \leq m} \max\limits_{i \in S} f_{minn,i}。

我们倒序枚举 minn，然后进行转移。

不难发现，当我们从 minn+1 转移到 minn 时，对于所有的 f_i，只会有是 minn 的倍数的位置发生改变，即此时有 f'_{minn,i}=\min\limits_{minn^x|i}f_{i/minn^x}\qquad(minn \mid i)。

所以总体的复杂度为调和级数 \mathcal{O}(m \log m)。

\color{blue}\texttt{CF 1678(div 2)}（VP）

赛时：\color{blue}\text{ABC}

赛后：\color{blue}\text{DEF}

A：\texttt{Tokitsukaze and All Zero Sequence}

题意：给定一个长度为 n 的序列 S，现可对其进行若干次操作，每次操作可选择序列内任意两个数 S_i,S_j，若两者相同则将其中一个数改为 0，否则将其中较大数改为较小数，问将整个数列变为 0 的最小操作数。（1 \leq S_i,n \leq 100）

分析：记 cnt_i 表示 i 在序列 S 的出现次数。

首先不难发现若 cnt_0>0，则答案为 n-cnt_0，证明显然。

然后对于原序列而已，若 \exists i \in S,cnt_i \geq 2，则答案为 n。 反之则为 n+1。

B：\texttt{Tokitsukaze and Good 01-String}

题意：对于满足如下性质的 01 串 a，我们称其为好串：

现给出一个 01 串 S ，可以将其中若干位取反，问要使 S 变为好串的最小取反位数和在这种操作下最终好串 01 段的段数。（1 \leq |S| \leq 2 \times 10^5）

分析：首先取反位数显然，对于所有的奇数位 S_{2n-1}，若 S_{2n-1} \neq S_{2n}，则这两位之中一定有一位需要取反，对答案贡献 +1。

C：\texttt{Tokitsukaze and Strange Inequality}

题意：给出一个长度为 n 的排列 p，若四元组 [a,b,c,d] 满足

• 1 \leq a<b<c<d \leq n
• p_a<p_c\ and\ p_b>p_d

则称四元组 [a,b,c,d] 是合法的。问原排列中合法四元组的数量。（1 \leq p_i \leq n \leq 5 \times 10^3）

分析：我们从朴素的做法考虑。

四重循环枚举，暴力统计答案，这样的复杂度为 \mathcal{O}(N^4)，显然无法通过。

考虑具有传递性的信息，发现可以优化枚举方式，改为仅枚举 b,c ，然后查看 [1,b) 以及 (c,n] 的符合题意的方案数。

对原排列进行预处理，记 pre_{i,j} 表示 [1,i] 内小于 j 的数，记 cnt_{i,j} 表示 [i,n] 内小于 j 的数，那么对于此时枚举的 b,c ，由乘法原理可知，此时对答案的贡献即为 pre_{b,p_c} \cdot cnt_{c,p_b}，总体复杂度为 \mathcal{O}(N^2)。

D：\texttt{Tokitsukaze and Meeting}（赛后写出）

题意：给出一个 n 行 m 列的矩阵，最初全部为空。现给出一个 01 序列 S，逐位将序列内的数放至矩阵的 (1,1) 位置，并将矩阵内所有其余数后移一位（特别的，每一行第 m 列的数移至下一行的第 1 列），问加入 S 的每一位时，矩阵中“好的行和列”的数量为多少。

我们定义一行或一列是好的，当且仅当这一行/列有至少一个数为 1。（1 \leq \sum n \times m \leq 10^6）

分析：我们将行和列分别考虑。

对于列来说，我们发现编号对 m 取模相同的数在加入数字时永远在同一列，所以开一个桶记录每一列是否已经有 1 出现即可。

但是行的计算与列不同，因为这里的计算是逐行转移，而列只需考虑与 m 取模的结果即可。

通过观察，发现对于每个元素 S_i，其在矩阵中某行的可能的状态只有 m 种（即 S_i 在第 1 列、第 2 列…第 m 列），因此考虑类似队列的区间移动，从头开始对 S 进行扫描，每次将第 i 位加入，将第 i-m 位弹出，记录此时区间内 1 的数目，再考虑对答案的贡献，时间复杂度为扫描每一位的 \mathcal{O}(n \times m)。

E：\texttt{Tokitsukaze and Two Colorful Tapes}（赛后写出）

题意：给出两个长度为 n 的排列 c_1,c_2，现对不同的数字 i 定义一个权值 a_i，问 \sum\limits_{i=1}^n \left | a_{c_{1_i}} - a_{c_{2_i}} \right | 的最大值。

分析：考虑将这一问题转化为图上问题。

对于第 i 位 的 c_{1_i} 和 c_{2_i}，我们视作一条从 c_{1_i} 连向 c_{2_i} 的边，边权为顶点的权值差，显然最终会形成若干个环，而对于每个环而言，显然当点权依次按照最小值和最大值排列时环的权值和最大，因此开两个指针 Le,Ri，用并查集判环，每次移动指针即可。

注意到若环的长度为奇数，那么最后一个点的权值无论是什么都不会有影响（因为一定满足 a_{1} < a_{lst} < a_{lst-1} 或者 a_{lst-1} < a_{lst} <a_1），因此将最后一步的指针移动省去，改为直接将 \left | a_1 - a_{lst-1} \right | 加入对答案的贡献。

F：\texttt{Tokitsukaze and Permutations}（赛后写出）

题意：对于一个长度为 n 的排列 p，我们定义序列 v，并且 v_i = \sum\limits_{j=1}^i [p_j>p_i]，即逆序对的数量。

现给出对排列 p 进行 k 次冒泡排序后的 v 序列（其中部分位为-1，表示可填任意数），问最初的排列 p 可能的情况有多少种，结果对质数取模。（1 \leq n \leq 10^6,0 \leq k < n,-1 \leq v_i < i）

分析：首先通过观察可知，对于一个合法的序列 v 有如下的性质：

• 对于 \forall v_i \in v，若 v_i \neq -1,则 v_i <i。
• 对于 \forall i \in (n-k,n],v_i = 0。
• 每进行一次冒泡排序相当于将整个序列 v 左移一位，即 v_i = \max(f_{i+1}-1,0)。
• 对于一个不存在-1的序列 v，其一定有且仅有一种排列 p 满足条件。

考虑对于给出的序列 v' 进行还原，可知：

• 若 v'_i = -1，由上面第一条性质可知，此时对答案贡献为 i。
• 若 v'_i = 0，由性质二和三可知，此时 v_i \in [0,p]，对答案贡献为 p+1。
• 若 v'_i>k，则显然 v_i 是固定的，对答案贡献为1。

由此根据乘法原理直接计数就行了。

\color{blue}\texttt{CF 1714(div 3)}

赛时：\text{\color{blue}{ABCE}}

赛后：\text{\color{blue}{DFG}}

A：\texttt{Everyone Loves to Sleep}

题意：给出 n 个时刻，问 H 时 M 分后第一个时刻是什么。（所有时间表示均为 24 小时制）（1 \leq n \leq 10, 0 \leq H < 24, 0 \leq M < 60）

分析：考虑只用分钟表示，那么所有的时刻我们可以用 24 \times 60 = 1440 个数字全部表示出来。

将所有时刻与目标时刻相减，将所有的数取最小值即可。（若有负数则需加回 1440）

B：\texttt{Remove Prefix}

题意：给出一个长度为 n 的序列 a，删去最小的前缀，使得最后剩下的序列每一个数都没有重复出现。(1 \leq a_i \leq n \leq 2 \times 10^5)

分析：从后往前扫描数组，记录每个数出现的次数，显然每个数只能出现一次，因此若当前的数之前出现过，那么便退出扫描即可。

C：\texttt{Minimum Varied Number}

题意：给出一个数 s，输出一个最小的数 \overline{x_1x_2x_3\ldots x_n}，使得 \sum\limits^{n}_{i=1}x_i=s。（1 \le s \le 45）

分析：考虑从大到小从后往前填数即可。

D：\texttt{Color with Occurrences}（赛后调出）

赛场上被 hack 了

题意：给出一个文本串 t 和 n 个模式串 s_1,s_2,\ldots,s_n，现用模式串匹配整个文本串（每个模式串可多次使用，位置可以重叠）。问匹配整个串的最小操作次数和操作方案。（若不能则输出 -1）（1\le n,|s_i| \le 10,1 \le |t| \le 100）

分析：法一：考虑 dp，先预处理出文本串中任一两位是否可以被一次匹配，然后记 f_x 表示完全覆盖前 x 位的最小操作次数。那么便可以从后往前枚举断点转移，复杂度为 \mathcal{O}(N^2)。（注意 dp 过程中还需要记录方案）

法二：考虑图论，先从末位往前依次向前一位连一条边权为 0 的有向边，然后对于每个能匹配的位置，从匹配位置向模式串末尾对应位置连一条边权为 1 的有向边，那么原问题便转化为了一个从 1 到 |t|+1 的最短路问题，乱搞即可。

E：\texttt{Add Modulo 10}

题意：给出 n 个数的序列 a，对于里面任意一个数 a_i，可以对其进行若干次操作，每次操作使得其变为 a_i + a_i \bmod 10，问能否将序列 a 内所有数通过上述操作使其全部相同。（1 \le n \le 2 \times 10^5,0 \le a_i \le 10^9）

分析：通过观察，我们不难发现，对于任一数 x，若其满足 x \bmod 5 =0，则最终只能表示成 x'\cdot 10 的形式，因此记录最终的数字即可。

对于其余的个位数，手推一下便能知道，最终经过若干次操作后一定会形成 2、4、8、6、2……的循环节，且 x/10 的奇偶性是不变的，因此随便钦定一个数作为最终的个位数，记录奇偶性即可。

F：\texttt{Build a Tree and That Is It}（赛后写出）

题意：给出四个数 n,d_{12},d_{23},d_{13}，试构造一棵大小为 n 的树，使得 1 号节点到 2 号节点的距离为 d_{12}，2 号节点到 3 号节点的距离为 d_{23}，1 号节点到 3 号节点的距离为 d_{13}，若不能则输出 -1。（3 \le n \le 2 \times 10^5,1 \le d_{12},d_{13},d_{23} < n）

分析：考虑一般情况（如图）

显然三个部分会有一个汇点，且三个顶点到汇点的距离均可以计算出来。

因此直接计算顶点到汇点的距离，依次新建节点输出即可。

G：\texttt{Path Prefixes}（赛后写出）

题意：给出一棵以 1 号节点为根的大小为 n 的数，每一条边都有两个权值 a,b。对于 \forall i \in [2,n]，定义 S_{ai}=\sum\limits_{x \in v}a_v,S_{bi}=\sum\limits_{x \in v}b_v，其中 v 为从 1 号节点到 i 号节点的所有边的集合，即 S 为从 1 到 i 路径上的边权和。

定义 R_u 表示从 1 到 u 的路径上，最大的不超过 S_{au} 的 S_{b} 对应的节点深度。现对于 \forall u \in [2,n]，求出其 R_u 的值。（1 \le n \le 2 \times 10^5,1 \le a_i,b_i \le 10 ^9）

分析：从根节点开始跑 dfs，直接记录下当前的 S_{au} 以及整条路径的 S_{bv}，然后从整条路径的 S_{bv} 中二分查找即可。

\color{red}\texttt{CF 1704(div 1+div 2)}

赛时：\color{blue}\text{ABC}

赛后：\text{\color{blue}DEF\color{red}GH}

A：\texttt{Two 0-1 Sequences}

题意：给出两个 01 串 a 和 b，现对 a 进行若干次操作，每次操作使得 a_2=\max(a_1,a_2) \ or \min(a_1,a_2)，并删去 a_1，问是否能使得最终 a 与 b 相同。（1 \le |b| \le |a| \le 50）

分析：考虑到是逐位操作，并且显然到了最后一次操作后最后几位都不会改变，因此考虑最后 |b|-1 位是否能匹配，若可以则考虑第一位的匹配问题即可。

B：\texttt{Luke is a Foodie}

题意：给出一个长度为 n 的序列 a 和一个常数 x，对于一个子序列 a_l,a_{l+1},\ldots,a_{r-1},a_r，若 \max(a_l,a_{l+1},\ldots,a_{r-1},a_r)-\min(a_l,a_{l+1},\ldots,a_{r-1},a_r)\le 2\cdot x，则称这个子序列是合法的。

问将整个序列划分为合法子序列的最小数目。（1 \le n \le 2 \times 10^5,1 \le a_i,x \le 10^9）

分析：从左到右扫描，依次记录当前区间的最大最小值，若不合题意则新增区间即可。

C：\texttt{Virus}

题意：给出一个长度为 n 的环，环上有 m 个黑点，现有如下流程：

• 指定一个白点，使其不会变为黑点，效果永久有效。
• 所有黑点两旁的点变为黑点（被操作一指定的点除外）。

问在进行足够多轮操作后，环上的黑点最少有多少。（1 \le B_i \le n \le 10^9,1 \le m \le \min(n,10^5)）

分析：考虑记录所有的白点连通块，按照长度从大到小排序，每次堵住两端即可。

D：\texttt{Magical Array}（赛后写出）

题意：有一个序列 b 和 n 个序列 c_1,c_2,\ldots,c_n，一开始所有的 c_i=b，现秘密指定一个序列 c_k，并对所有的序列进行至少一次操作，对于一个序列 c_i，若 i \ne k，则每次操作选定两个位置 l,r(1 <l <r<|b|)，将 c_{i_l},c_{i_r} 减一，将 c_{i_{l-1}},c_i{_{r+1}} 加一；若 i=k，则对于 l,r(1<l<r<|b|-1)，c_{i_l},c_{i_r} 减一，将 c_{i_{l-1}},c_i{_{r+2}} 加一。所有操作基于不会出现负数的情况。

现给出经过了若干次操作后的 c_1,c_2,\ldots,c_n，推断出 k 以及在 c_k 上的操作次数。（3 \le n \le 10^5,7 \le |b|\le 3 \times 10^5,0 \le b_i \le 10^6,0 \le c_{i,j} \le 3 \times 10^{11}）

分析：通过观察，发现除了特殊序列，其余数列每次操作位置和始终为 0（l+r-(l-1+r+1)=0）。

因此记录 S_i =\sum C_i \cdot i，发现每次操作除特殊序列外其余数列 S 不变，而特殊序列 S 会加 1，因此直接排序即可。

E：\texttt{Count Seconds}（赛后写出）

题意：给出一个 n 个点 m 条边的有向无环图，每个点有点权 a_i，现有如下流程：每一个时刻开始时，所有当前边权 >0 的点边权 -1，然后令所有与这些点 \{X\} 指向的点 X \rightarrow Y 的点权 +1，问所有点点权为 0 时的最早时刻，结果对质数取模。（1 \le n,m \le 1000,0 \le a_i \le 10^9）

分析：若每个节点点权均 >0，此时显然直接进行拓扑排序便能求出答案。那么我们来考虑某些节点点权为 0 时的情况。通过观察我们可以发现：每一个时刻结束时，至少会减少 1 个点权为 0 的点。那么我们可以先暴力做前 n 轮，然后此时便能保证每一个节点点权 >0，进行拓扑排序即可。

F：\texttt{Colouring Game}（赛后写出）

题意：有一排长度为 n 的格子，每个格子涂上了红色或者蓝色，现有两人（红方、蓝方）分别操作（红方先手），每次操作选择一对相邻的格子，要求两个格子至少有一个是自己所对应颜色的，然后将两个格子均涂成白色。双方轮流操作，无法操作的人失败，问在两人均采用最优策略的情况下哪一方能获胜。（2 \le n \le 5 \times 10^5）

分析：首先我们可以发现：若双方颜色块数量不一样，显然少的一方输。然后我们通过观察可知，双方的最优策略一定是：若存在相邻的异色的格子，则选择这一对，将其染成白色，否则每次只会消去一个同颜色的块。同时我们又会发现对于前一种选择对于双方颜色块的差值没有影响，因此我们考虑记 SG_x 表示一段长度为 x 的红蓝交错串的 SG 值，则显然有 SG_0 = SG_1 =0，同时有 SG_n=\operatorname{mex}_{i=1}^{n-1}SG_{i-1} \oplus SG_{n-i-1}。

但是我们会发现直接求出 SG_n 的复杂度是 \mathcal{O}(n^2) 的，不可接受，但是我们又会发现此时的序列除了某些特定位置以外，具有一个长度为 34 的循环节，因此可以打表出循环节然后加上特殊位置的特判即可。

\color{red}\texttt{CF 1716(div 2)}

赛时：\text{\color{blue}{ABD}}

赛后：\text{\color{blue}{CE}\color{red}{F}}

A：\texttt{2-3 Moves}

题意：给出一个数 n 和一个初始为 0 的数 x，现对 x 进行若干次操作，每次操作使得 x 变为 x \pm 2 或 x \pm 3（x 可以为负），问使 x=n 的最小操作次数。（1 \le n \le 10^9）

分析：显然每次加 3 是最快的，而对于模 3 不等于 0 的数，我们发现只需要多进行一次操作即可（1 除外），因此可以 \mathcal{O}(1) 解决这个问题。

B：\texttt{Permutation Chain}

题意：对于一个长度为 n 的排列 p，我们定义 S= \sum\limits_{i=1}^{n}[p_i=i]。

现给出一个长度为 n 的排列 p=\{1,2,\ldots,n\}，对其进行尽可能多次的交换（不妨设为 k 次），使得其 S_1,S_2,\ldots,S_k 严格下降。（2 \le n \le 100）

分析：手玩一下即可发现 k=n，然后每次交换从未被操作过的数中选一个，从已被操作过的数中选一个（没有就再选一个未被操作过的数），两者交换后输出即可。

C：\texttt{Robot in a Hallway}（赛后写出）

题意：给出一个 2\times n 的矩阵 c，每个位上均有一个数值 c_{i,j}，现有一个人在 0 时刻从 (1,1) 出发，每次可向四个方向走或停留在原地，要求每个格只能被经过一次，且有 t>c_{i,j}（t 为当前时刻），问走完整个矩阵的最小时间。（2 \le n \le 2 \times 10^5,0 \le c_{i,j} \le 10^9 且 c_{1,1}=0）

分析：我们发现，满足题意的方案一定是这样的：先按列 S 型走若干列，然后在某个位置顺时针或逆时针一路走。

那么我们先进行预处理，记录 R_i 表示顺时针行走 i 至 n 列的最小时间，L_i 表示逆时针行走 i 至 n 列的最小时间，然后模拟行走过程，一边循环一边更新答案即可。

D：\texttt{Chip Move}

题意：给出一个整数 k，对于一个数 r，定义 f_r 代表 r=a_1 \cdot k + a_2 \cdot(k+1)+...a_u\cdot(k+u-1) \quad (a_1,a_2,\ldots,a_u \ge 1) 的方案数，结果对质数取模。

现有一整数 n，求出对于 \forall i \in [1,n]，其 f_i 的值。（1 \le k \le n \le 2 \times 10^5）

分析：我们发现，倘若没有 a_i \ge 1 的限制，这个问题可以转化为一个完全背包的模型。

然后我们再来考虑加上这一限制后的处理。显然此时状态转移只能从上一轮新增的情况得来，所以每一次要减去上一轮的方案数，在最后输出时再加回来。

E：\texttt{Swap and Maximum Block}（赛后写出）

题意：给出一个长度为 2^n 的序列 a，现对其进行若干次操作。每次操作给出一个数 k，将整个序列按照每 2^{k+1} 分为若干段，对于每一段，将前后半部分交换，同时询问整个序列的最大子段和。（1 \le k <n \le 18,-10^9 \le a_i \le 10^9）

分析：首先我们可以发现，对于所有的交换操作，我们交换的次序对最终的答案无影响，并且同一个 k 出现两次的话会抵消，那么我们可以考虑对于所有交换的情况进行预处理。

由于这里维护的是一个最大子段和，所以我们可以考虑使用一个类似线段树的数据结构维护这一信息，记录下一个区间的前缀和最大值、后缀和最大值，区间最大子段和，然后在交换的时候合并信息即可。

\texttt{\color{blue}{CF 1711(div 2)}}（VP）

赛时：\text{\color{blue}{ABCDE}}

A：\texttt{Perfect Permutation}

题意：定义一个长度为 n 的排列 a 的权值 p= \sum\limits_{i=1}^{n}[i \mid a_i]，现给出 n，构造一个长度为 n 的权值最小的排列。（1 \le n \le 10^5）

分析：显然有 1 \mid a_1 =True，则考虑其他位互质的情况。

通过观察可知，若我们将排列 P={1,2,3,\ldots,n} 的第 1 位放至最后，其他位提前，即整个排列变为 P'={2,3,4,\ldots,n,1}，此时对于 2 \le i \le n，均有 i \perp P'_i，此时 p=1 为最小值。

B：\texttt{Party}

题意：给出一个有 n 个点，m 条无向边的图（不一定连通），每个点都有其点权 a_i，现从中选出若干个点，若 (i,j) \in S(\text{S为选择的点的集合})，且存在一条边 i \leftrightarrow j，则这条边也会被选择。现要求选出的边为偶数时未被选择的点权和的最小值。（1 \le n \le 10^5,0 \le m \le \min(10^5,\frac{n(n-1)}{2}),0 \le a_i \le 10^4）

分析：首先，若 m \bmod 2 =0，此时最优方案显然是选择所有的点。

然后若 m \bmod 2 =1，此时显然会有点的度为奇数。此时枚举度数为奇数的点，用其权值更新答案。

然后考虑删掉边，直接枚举每一条边，计算这条边连接的两个端点的点权和即可。

C：\texttt{Color the Picture}

题意：给出一个 n 行 m 列的网格，现有 k 种颜料，每种颜料限涂 a_i 格，用所有的颜料填满整个网格后，要求对于网格的每一位 C_{i,j}，其环形相邻的四个位中有至少三个位颜色与其相同，问是否可以做到。（3 \le n,m,a_i \le 10^9,1\le k \le 10^5）

分析：首先通过观察易知对于每种颜色而言，其如果要涂入网格，必须要涂至少两行或者两列，且所有的颜色必须统一按列涂或者统一按行涂。

这里以按列涂色为例，按行涂色同理。

若 m \bmod 2 =0，此时直接判断能涂入的列数是否大于 m 即可。

否则，若有一种颜色满足其能填至少三列，并且此时的 Sum \ge m，那么显然是符合题意的。

若上述情况均不满足，那么即为无法做到。

D：\texttt{Rain}

题意：有一个无限长度的数轴，数轴上每一个整点初始数值 a_i 均为 0。现有 n 次加法操作，每次操作给出两个数 x_i,p_i，使得所有的 a_j \leftarrow a_j+\max(0,p_i-|x_i-j|)，对于一个状态 S（即某一时刻的数轴），若存在一个 i 满足 S_i>m 则称这个状态是不合法的。

问每次单独取消第 i 次加法操作后最终状态是否合法。（1\le n \le 2 \times 10^5,1 \le m,x_i,p_i \le 10^9）

分析：我们发现，对于每次加法操作，其最终形成的最高点一定会有 x_i，证明显然。

那么对于最终状态的查询，我们就转化为了对每个最高点的查询，考虑到每一次加的是两个等差数列，我们对其进行差分即可。

E：\texttt{XOR Triangle}

题意：我们定义一个三元组 (a,b,c) 是合法的，当且仅当 0 \le a,b,c \le n，且三个数两两异或后的值可以组成一个非退化三角形的三条边。

现给出一个用二进制表示的数 S_2，求出符合题意的三元组数量，结果对质数取模。（1 \le |S| \le 2 \times 10^5）

分析：数位 dp 练手题。

我们不妨只考虑 a \oplus b + a \oplus c > b \oplus c 的情况，其余情况同理。

通过画出真值表我们可以发现对于每一位而言（设其为 x,y,z），有 x \oplus y + x \oplus z \ge y \oplus z，对于 x \oplus y + x \oplus z > y \oplus z 的情况，当且仅当 x!=y\ and\ y=z，此时其余位置便没有限制了。

因此记录下当前第 i 位下 x,y,z 的值以及 x,y,z 是否存在限制 Limit_x,Limit_y,Limit_z，按照上面的方法跑 dfs 即可。

\color{red}\texttt{ABC 264}

赛时：\color{blue}\text{ABCD}

赛后：\text{\color{blue}{E}\color{red}{FGEx}}

A：\texttt{"atcoder".substr()}

题意：给出两个数 L 和 R，输出字符串 \texttt{atcoder} 的第 L 到第 R 位。（从 1 开始计算位数）

分析：直接输出即可。

B：\texttt{Nice Grid}

题意：输出如图所示 15 \times 15 的矩形的 (i,j) 位上的颜色。（1\le i,j \le 15）

0->Black 1->White

000000000000000
011111111111110
010000000000010
010111111111010
010100000001010
010101111101010
010101000101010
010101010101010
010101000101010
010101111101010
010100000001010
010111111111010
010000000000010
011111111111110
000000000000000

分析：通过分析矩阵可知，每一行从左往右均是一段循环的 01 然后一段连续的 0/1 最后又是一段循环的 10。

分奇偶性讨论即可。

C：\texttt{Matrix Reducing}

题意：给出一个 N_1 \times M_1 的矩阵 A 和一个 N_2 \times M_2 的目标矩阵 B。对 A 进行若干次操作，每次操作删去某一行或者某一列，问能否通过操作使得 A 与 B 相同。（1 \le N_2 \le N_1 \le 10,1 \le M_2 \le M_2 \le 10,1 \le a_{i,j},b_{i,j} \le 10^9）

分析：由于矩阵大小较小，考虑直接二进制枚举 A 最后剩下的行/列。

每次枚举二进制状态 f_1,f_2，先判断其 1 的位数是否符合题意，然后用两个指针扫描一次即可。

D：\texttt{"redocta".swap(i,i+1)}

题意：给出字符串 \texttt{atcoder} 的任意一种排列，现对其进行若干次操作，每次操作交换任意相邻两位上的字符，问使得给定排列变为 \texttt{atcoder} 的最小操作次数。

分析：原题可转化为求逆序对，又因为字符串长度较小，对其进行序号化后直接冒泡排序模拟即可。

E：\texttt{Blackout 2}（赛后调出）

题意：给出 N 个白点和 M 个黑点，最初有 E 条边连接不同的点（整个图不一定连通），现有 Q 次操作，每次操作给出一个数 k，删去第 k 条边，问每次删边后与黑点连接的白点数量。（1 \le N,M,N+M \le 2 \times 10^5,1 \le Q \le E \le 5 \times 10^5）

分析：从正面考虑显然不好做，因此考虑将询问离线下来，向删去了 Q 条边的图中从后往前加入删去的边即可。

对于每个点，我们用并查集记录每个节点所属连通块的白点和黑点数量，然后在询问的时候合并并查集即可。

\texttt{\color{blue}{CF 1712(div 2)}}

赛时：\text{\color{blue}{A}\color{grey}{B}\color{blue}{CD}}

赛后：\text{\color{blue}{EF}\color{red}{}}

A：\texttt{Wonderful Permutation}

题意：给出一个长度为 n 的排列 p 和一个数 k，现对其进行若干次操作，每次操作选择两个位置 i,j，交换 p_i,p_j，问要使得 \sum _{i=1}^{k}p_i 最小的最少操作次数。（1 \le k,p_i \le n \le 100）

分析：显然 S 最小时 p_1,p-2,..,p_k 为 1 到 k 的排列，直接统计原排列 1 到 k 位在 [1,k] 的数的数量即可。

B：\texttt{Woeful Permutation}

题意：给出一个数 n，构造一个长度为 n 的排列 p，使得 \sum_{i=1}^{n} \operatorname{lcm}(p_i,i) 最小。（1 \le n \le 10^5）

分析：从第 n 位开始往前配对，即 (p_{n-1},p_n)=(n,n-1)，一直往前考虑，此时 S 的值最大。

证明较为复杂。

C：\texttt{Sort Zero}

题意：给出一个长度为 n 的序列 a，现对其进行若干次操作，每次操作指定一个数 x，令所有 a_i=x 的位置 a_i=0。

问将整个序列修改为不降序列的最小操作次数。（1 \le a_i \le n \le 10^5）

分析：我们先来考虑单点修改的情况（即修改时仅修改第 i 位），此时显然从后往前扫描，遇到一处 a_i>a_{i+1} 的位置便退出循环并输出 i。

这里是群体修改，我们发现若仅仅考虑第一个出现逆序的位置还不够，因为将前面的位置修改时会对后面造成影响，所以记录每一个数最后出现的位置以及不同数字种类的前缀和，同上面的扫描，只不过这次返回 a_i 最后一次出现位置的前缀和即可。

D：\texttt{Empty Graph}

题意：给出一个长度为 n 的序列 a，先对其进行至多 k 次操作，每次操作指定两个数 i,x(1 \le i \le n,1 \le x \le 10^9)，然后令 a_i=x。然后得到一个新的序列 a'。用其建一个完全图 G，其中 dist(i,j)=\min\{a'_i,a'_{i+1},\ldots,a'_{j}\}。

问新的完全图的直径。（两点间最短路的最大值） （2 \le n \le 10^5,1 \le k \le 10^5,1 \le a_i \le 10^9）

分析：先对整个序列排序，通过观察，显然我们会将 a 序列的前 k 小的数全部替换为 10^9，这样才能保证我们完全图的边不劣。然后观察完全图的边权的构建方式，发现答案一定是某两下标相邻的点的最短路，即 dist(i,i+1) 或者是 dist(i,k+1)+dist(i+1,k+1)=2 \times a_{k+1}。

因此直接按照相邻位置从左往右扫描即可。

E：\texttt{LCM Sum}（赛后写出）

题意：给出两个正整数 l,r，求满足 \operatorname{lcm}(i,j,k) \ge i+j+k 并且 l \le i < j < k \le r 的三元组 (i,j,k) 的数量。（1 \le l \le r \le 2 \times 10^5，10^5 组询问）

分析：由于符合题意得三元组数量较难求，考虑正难则反，用总的方案数减去不合法的方案数。设 len=r-l+1，则总方案数显然为 \frac{len \times (len-1) \times (len-2)}{6}。

然后我们考虑如何求不合法的三元组数量，即满足 \operatorname{lcm}(i,j,k)<i+j+k 的三元组数量。由于 i<j<k，则显然 \operatorname{lcm}(i,j,k)<i+j+k<3 \cdot k。又因为 k \mid \operatorname{lcm}(i,j,k)，所以 \operatorname{lcm}(i,j,k)=k 或者 \operatorname{lcm}(i,j,k)=2 \cdot k。

先考虑第二种，及 \operatorname{lcm}(i,j,k)=2 \cdot k 的情况。此时通过手玩可知当且仅当 (i,j,k) 为 (3,4,6) 或者 (6,10,15) 的倍数时能满足；然后我们考虑第一种，此时显然 i,j 均为 k 的约数，那么我们可以将询问离线下来，记录 1 到 2 \times 10^5 每个数的约数，然后用树状数组统计每个约数的贡献，最后区间查询即可。

F：\texttt{Triameter}（赛后写出）

题意：给出一棵 N 个节点的树，每条边的边权为 1，现有 q 次操作（操作不会保留），每次操作将所有叶子节点两两连一条长度为 x 的边，问新的图的直径。（3 \le N \le 10^6,1 \le q \le 10,1 \le x \le n）

分析：我们令 f_i 表示 i 号节点到最近叶子节点的距离，那么最终的直径一定为 dist(u,v)（对于原树而言）或者是 f_u+f_v+x，因此我们可以记录下对于每个 f_i=x 的 i，然后合并每颗子树的信息，二分答案独立完成每个询问即可。

\texttt{\color{blue}CF 1715(div 2)}

赛时：\text{\color{blue}ABC}

赛后：\text{\color{blue}{DEF}}

A：\texttt{Crossmarket}

题意：给出一个 N \times M 的矩阵，现有两个点，分别位于 (1,1) 和 (N,1)。现两个点先后走至其异侧顶角，若后点走至前点到过的点，则此时连续一段的花费为 1，问最小花费。（1 \le N,M \le 10^5）

分析：考虑显然在最优情况下，花费为 1 的一段一定为一列/一行，所以直接判断是某一列花费 1 或者在某一行花费 1 即可。

B：\texttt{Beautiful Array}

题意：给出四个数 n,k,b,s，问是否能构造一个长度为 n 的序列 a，使得 \sum\limits^{n}_{i=1}a_i = s 并且 \sum\limits^{n}_{i=1} \lfloor \frac{a_i}{k} \rfloor = b。（1 \le n \le 10^5,1 \le k \le 10^9,0 \le b,s \le 10^{18}）

分析：通过观察可知，我们完全可以构造出一种序列，使得只有某一位满足 \lfloor \frac{a_i}{k} \rfloor \ge 1，那么此时有 \forall 1 \le i \le n,0 \le a_i \bmod k \le k-1，由此计算出 s 的上下限，然后从大到小填入余数即可。

C：\texttt{Monoblock}

题意：定义一段序列 a 的权值 s=1+\sum\limits^{n-1}_{i=1}[a_i \neq a_{i+1}]，即序列内连续权值段数。现有一个长度为 n 的序列 a，有 m 次操作，每次操作将 a_{pos} 改为 x，问此时 a 的所有子序列的权值和。（1 \le n,m \le 10^5,1 \le a_i,x \le 10^9）

分析：我们将求序列权值和改为求不同满足 a_i \neq a_{i+1} 的位置的贡献。那么每一次修改后都可以通过乘法原理枚举越过 i 和 i+1 的位置的区间数来求出其贡献修改值。

D：\texttt{2+ doors}（赛后调出）

题意：给出一个数 n 和 q 个限制，构造一个字典序最小的长度为 n 的序列 a，满足每一个限制：a_x \mid a_y = z。（1 \le x,y \le n \le 10^5,0 \le q \le 2 \times 10^5,0 \le z < 2^{30}）

分析：我们考虑按位计算。首先我们将所有能填 1 的位先填上 1，然后枚举每一个条件，留下条件中某一个的这一位为 1，另一个即为 0。

E：\texttt{Long Way Home}（赛后写出）

题意：有一个 n 个点 m 条带权无向边的图，现可加入至多 k 条边，若某条新边连接编号为 u 和 v 的点，那么这条边的边权为 (u-v)^2。现独立询问从 1 号节点到所有节点的最短路。（2 \le n \le 10^5,1 \le m \le 10^5,1 \le k \le 20）

分析：我们考虑增量法，即从 k=1 的情况入手。

当 k=1 时，此时显然到某个顶点的最短路方案为 \text{旧边}\rightarrow\text{新边}\rightarrow\text{旧边}，那么我们可以先做一次单源最短路，得到第一步的最短路。然后考虑新边，此时显然可以这样更新：dis'_u \leftarrow \min\limits_{v}(dis_v+(v-u)^2)，将 \min 去掉，那么便能开始推导：

此时等式右侧是一个可以斜率优化的式子，但是注意到此时的 v 是没有与 u 的大小关系限制的，因此要先将所有的决策点先加入，再进行转移，那么第二步也完成了。

最后从所有的状态（包括新加入的状态）再跑一边最短路即可。

此时我们解决了 k=1 的情况，那么对于 k>1 的情况，我们只需要跑 k 轮重复的操作，同时一直更新即可。

F：\texttt{Crop Squares}（赛后写出）

题意：交互题。在一个坐标系中，有一个 1 \times 1 的正方形，边与坐标轴平行且其左下角顶点位置 0 \le x \le n-1,0 \le y \le m-1，现进行最多 5 次询问，每次询问构造一个多边形（要求每个顶点的坐标 | x |,|y| \le 10^4），会得到多边形与正方形的相交面积，求出正方形的准确位置。（误差不超过 10^{-6}）（1 \le n,m \le 100）

分析：一道有意思的构造题。

我们需要构造如下图所示的锯齿状的多边形（图选自 \text{ExplodingKonjac} 的博客）

可以发现，对于上面图示情况而言，对于正方形与多边形的重合面积，不同的 y 值得到的面积也是不同的，而正方形的左右平移不影响重合面积。那么我们便可以得出正方形的 y 值。

而对于 x 值，只需要将上面的图形顺时针旋转 90^{\circ} 即可。

\texttt{\color{red}CF 1720(div 2)}

赛时：\text{\color{blue}ABC}

赛后：\text{\color{red}DE}

A：\texttt{Burenka Plays with Fractions}

题意：给出两个分数 \frac{a}{b} 和 \frac{c}{d}，对其进行若干次操作，每次操作使得 a,b,c,d 中任意一个数乘上随便一个数（显然 c,d 不能为 0）。现求最小的操作次数，使得两个分数数值上相等。（0 \le a,c \le 10^9,1 \le b,d \le 10^9）

分析：显然，当 \frac{a}{b} \leftarrow \frac{a \times b \times c}{b \times a \times d} 时，两个数数值上时相等的，那么我们直接考虑是否能通过约分使得乘上的数减少即可。

B：\texttt{Burenka Plays with Fractions}

题意：给出一个长度为 n 的序列 a，求出一个数对 (l,r)(1 \le l < r \le n)，使得 \max(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) - \min(a_{1}, a_{2}, \ldots, a_{l-1}, a_{r+1}, a_{r+2}, \ldots, a_{n}) + \max(a_{l}, \ldots, a_{r}) - \min(a_{l}, \ldots, a_{r}) 最小。（4 \le n \le 10^5,1 \le a_i \le 10^9）

分析：通过观察可知，原式子可转化为求序列内最大值+次大值-最小值-次小值，直接记录即可。

C：\texttt{Corners}

题意：给出一个 N \times M 的 01 矩阵 a，现先后填入最多数目的 2 \times 2 的 L 型“挡板”。盖上挡板时目标位置至少有一个 1，而且盖上后盖住的位置均改为 0。（2 \le n,m \le 500）

分析：令矩阵内 1 的个数为 cnt。首先若有两个相邻位置的 0（八个方向），那么我们可以做到每次放入 L 时只消去一个 1，答案为 cnt。若有单独的 0，那么答案为 cnt-1，否则答案为 cnt-2。

\texttt{\color{red}ARC 106}（VP）

赛时：\text{\color{blue}ABCD}

赛后：\text{\color{red}{EF}}

A：\texttt{106}

题意：给出一个数 N，求出正整数对 (X,Y)，使得 3^X+5^Y=N。若不能输出 -1.（1 \le N \le 10^{18}）

分析：先记录下 N 以内 3 的幂次方的数字，然后枚举做减法查看 N-5^Y 是否为 3 的幂次方即可。

B：\texttt{Values}

题意：给出两个有 N 个点 M 条边的无向图 G_1,G_2，两个图的连边均相同，然后给出两个图上每个点的点权（分别为 a_i,b_i）。现对 G_1 进行若干次操作，每次操作选择一条边，重新分配这条边所连接的点的点权（要求和不变），问能否使得 G_1 与 G_2 完全相同。（1 \le N \le 2 \times 10^5,0 \le M \le 2 \times 10^5,-10^9 \le a_i,b_i \le 10^9）

分析：通过观察可知，对于同一连通块，对其中的边进行操作不会改变该连通块内的点权和，所以用并查集找出每个连通块，然后看同一连通块内 a 的和与 b 的和是否相同即可。

C：\texttt{Solutions}

题意：对于区间调度问题，先有两种解决方案：1、按照区间右端点排序判断是否选择，结果为 ans_1；2、按照区间左端点排序判断是否选择，结果为 ans_2。现给出两个整数 N,M，问是否能构造出 N 个区间，使得 ans_1-ans_2=M。（1 \le N \le 2 \times 10^5,-N \le M \le N，构造出来的区间端点不能重合且为正整数）

分析：显然 ans_1 为最优方案，所以 M \ge 0；当 M=N 时，考虑到 ans_2\ge 1，而 ans_1 \le N 因此无法构造。当 M=N-1 时，若 N=1 则显然可以，反之手推一下即可发现无法构造。对于剩下的情况，我们可以构造出 M+1 个互不干扰的小区间，然后再构造 N-M-1 个完全包含已有区间的大区间即可。

D：\texttt{Powers}

题意：给出一个长度为 N 的序列 S 和一个数 K，对于所有 1 \le X \le K，求出 \sum\limits^{N-1}_{i=1}\sum\limits^{N}_{j=i+1}(S_i+S_j)^X，结果对质数取模。（2 \le N \le 2 \times 10^5,1 \le K \le 300,1 \le S_i \le 10^8）

分析：首先原问题有位置的限制，考虑求出 \sum\limits^{N}_{i=1}\sum\limits^{N}_{j=1}(S_i+S_j)^X，然后减去 \sum\limits^{N}_{i=1}(2 \cdot S_i)^X 后除以二即可。

然后我们推导式子

此时很明显 \sum\limits^{N}_{i=1}\frac{S_i^k}{k!} 和 \sum\limits^{N}_{j=1}\frac{S_j^{X-k}}{(X-k)!} 都可以预处理求出，于是问题就可以解决了。

\texttt{\color{red}ABC 266}

赛时：\text{\color{blue}ABCDE}

赛后：\text{\color{red}FGEx}

A：\texttt{Middle Letter}

题意：给出一个长度为奇数的字符串 S，输出其最中间的字母。（1 \le \mid S \mid 99）

分析：直接输出即可。

B：\texttt{Modulo Number}

题意：给出一个整数 N，求一个位于 [0,998244353) 的整数 x，使得 998244353 \mid N-x。（-10^{18} \le N \le 10^{18}）

分析：显然要求的数与 N 取模 998244353 的结果同余，所以直接取模而且加上偏移量即可。

C：\texttt{Convex Quadrilateral}

题意：给出一个四边形的四个顶点坐标，判断这个四边形是否为凸四边形。（1 \le X_1,X_2,X_3,X_4,Y_1,Y_2,Y_3,Y_4 \le 100）

分析：模板题，直接套板子即可。

D：\texttt{Snuke Panic (1D)}

题意：有一个从 0 到 4 的数轴，现有 N 个价值为 A_i 的点，每个点在第 T_i 时刻出现在数轴上 X_i 位置。你最初（第 0 时刻）位于数轴上 0 的位置，每个时刻可以移动一个单位距离或者停留在原地，若到达一个位置后在那个时刻有点出现便可获得这个点，问最终你能获得的点的价值和的最大值。（1 \le N \le 10^5,0 < T_1 < T_2 < \ldots < T_N \le 10^5,1 \le A_i \le 10^9）

分析：考虑 dp。记 f_{i,j} 表示第 i 时刻结束时处于第 j 的位置的最大值，那么显然可以直接按照时间转移，考虑移动花费的时间即可。

E：\texttt{Throwing the Die}

题意：有一个六个面的均匀骰子，你可以掷至多 N 次，最终的分数为你结束时骰子正面向上的数，问最终分数的期望值最大是多少。（1 \le N \le 100）

分析：令 f_i 表示掷 i 次时的最大期望值，那么我们在考虑第 i+1 次投掷时，显然只有这一次掷出来的结果大于目前期望值我们才接受，那么便可以得出：

直接递推即可。

\texttt{\color{red}CF 1721(div 2)}（VP）

赛时：\text{\color{blue}ABCD}

赛后：\text{\color{blue}E\color{red}F}

A：\texttt{Image}

题意：给出一个由小写字母组成的 2 \times 2 的矩阵 S，现对其进行若干次操作，每次操作将至多两个相同的字母改成任意一种字母，问将整个矩阵所有的字符变为相同字符的最小操作次数。

分析：我们枚举整个矩阵最终一致的字符，计算更新的最小次数然后更新答案即可。

B：\texttt{Deadly Laser}

题意：有一个 n \times m 的全是白点的矩阵，现在令矩阵内所有与 (S_x,S_y) 的曼哈顿距离 \le d 的点都变成黑点，问从 (1,1) 只走白点到达 (n,m) 的最小步数。（若不能到达输出 -1）（2 \le n,m \le 1000,0 \le d \le n+m）

分析：首先很显然的一点，若存在到达 (n,m) 的路径，那么结果一定为 n+m-2。

那么我们来考虑无法到达的情况，显然只用考虑第 S_x 行和第 S_y 列的情况：

• 其余情况均可到达 (n,m)。

C：\texttt{Min-Max Array Transformation}

题意：给出两个长度为 n 的不降序列 A,B，构造一个非负序列 D，令 A_i \leftarrow A_i + D_i，并将序列 A 重新排序为不降序列，使得 A 与 B 完全一致。独立询问对于每个位置 i，其可能的 D_{\min} 和 D_{\max} 分别是多少。（1 \le n \le 2 \times 10^5,1 \le A_i,B_i \le 10^9,A_i \le A_{i+1},B_i \le B_{i+1}，数据保证存在合法的序列 D）

分析：首先通过观察，我们可以发现一个性质：若 A_i \le B_{i-1}，那么显然我们可以令 A_i+D_i=B_{i-1},A_{i-1}+D_{i-1}=B_i，并且这一性质具有传递性。

对于 D_{i}^{\min}，由于询问是独立的，我们只需要找到序列 B 中第一个 \ge A_i 的位置（不妨为 l_i），然后 D_{i}^{\min} \leftarrow B_j - A_i 即可。

对于 D_{i}^{\max}，我们用上刚刚提到的性质，求出对于每个位置其能够“交换”的位置的最右端（不妨为 r_i），然后 D_{i}^{\max} \leftarrow B_{l_{r_i}}-A_i 即可。

D：\texttt{Maximum AND}

题意：定义函数 f(a,b)，表示对于两个序列 a,b，其 (a_1 \oplus b_1)\&(a_2 \oplus b_2)\&\ldots\&(a_n \oplus b_n) 的结果。现给出两个长度为 n 的序列 a,b，任意调换序列 b 的元素顺序，问 f(a,b) 的最大值。（1 \le n \le 10^5,0 \le a_i,b_i < 2^{30}）

分析：我们从高位向低位考虑。设目前已知的答案为 ans，我们考虑当前第 i 位是否能取 1，先令 ans 的这一位为 1，先得出所有 a_i 与 b_i 与 ans 进行与运算的结果，显然需要令所有最小的结果与另一个序列最大的结果匹配（即两者异或的结果为 ans），那么这时候我们可以保证能够构造出合法的匹配方案，ans 的这一位取 1，反之则取 0。

E：\texttt{Prefix Function Queries}（赛后写出）

题意：给出一个字符串 s，现独立给出 q 个字符串 t，求出将 t 拼到 s 后面后最后 |t| 个前缀的 border 长度。（1 \le |s| \le 10^6,1 \le q \le 10^5,1 \le |t| \le 10）

分析：我们发现 |t| 较小，因此可以考虑保留原有字符串 s 的大部分信息，建立 KMP 自动机，对于每个新串直接暴力修改，修改已有的 KMP 自动机，然后在新串上跑 KMP 即可。

\texttt{\color{red}ARC 147}

赛时：\text{\color{blue}AB}

赛后：\text{\color{blue}CDE\color{red}F}

A：\texttt{Max Mod Min}

题意：给定一个长度为 n 的序列 A，现对其进行若干次操作，每次操作将序列内最大的数 A_{\max} 取出，将其改为 A_{\max} \mod A_{\min}（若结果为 0 则删去这个数），问最终的操作次数。（2 \le n \le 2\times 10^5,1 \le A_i \le 10^9）

分析：建一个大根堆一个小根堆，直接模拟即可。

B：\texttt{Swap to Sort}

题意：给定一个长度为 N 的排列 P，现有两种操作：

• 操作 A：选择一个 1 \le i \le n-1，交换 P_i,P_{i+1}

• 操作 B：选择一个 1 \le i \le n-2，交换 P_i,P_{i+2}

现要构造一种操作方案（总长度不超过 10^5），使得操作 A 的数量尽可能少，且操作完毕后整个排列是递增的。（2 \le N \le 400）

分析：显然操作 B 不能改变一个数位置的奇偶性，同时容易观察到若一个数的奇偶性和它位置的奇偶性不匹配，那么一定会成对出现，此时只需要一个操作 A 便能解决（前提是两数相邻）。因此，先枚举不匹配的位置，用操作 B 将其移至第一个奇偶性不同的不匹配的位置，用一次操作 A。然后我们得到了奇偶性匹配的排列，此时直接冒泡排序即可。

C：\texttt{Min Diff Sum}（赛后写出）

题意：给出 N 个区间，现从每个区间中选出一个点 L_i \le x_i \le R_i，求 \sum\limits_{i=1}^{N-1}\sum\limits_{j=i+1}^{N}|x_i-x_j| 的最小值。（2 \le N \le 3 \times 10^5,1 \le L_i \le R_i \le 10^7）

分析：令 L_{\max}=M,R_{\min}=m，当 M \le m 时，显然我们可以从所有区间中选出一个 M \le X \le m 作为重合点，且此时答案为 0。然后我们来考虑 M>m 的情况。此时我们容易发现由于我们 M 和 m 的定义，在最优情况下，对于所有的 i，我们均有 m \le x_i \le M，那么我们考虑 m 到 M 的贡献，此时显然其贡献为 (M-m)\times tot（tot 表示目前剩余的区间数），然后我们得到一个减少了 2 个区间的子问题。因此我们便可以得到整个问题的最终答案：\sum\limits_{i=1}^{N}\max(0,L_i-R_i) \times (N-2 \times i +1)（L 按照从大到小排列，R 按照从小到大排列）

D：\texttt{Sets Scores}（赛后写出）

题意：给出一个整数 N，我们定义一个长度为 N 的集合序列 S=(S_1,S_2,\ldots,S_N)（集合内所有元素均满足 1 \le S_i \le M）是好序列，当且仅当对于任意 1 \le i \le N-1，均有 S_i 和 S_{i+1} 仅相差一个元素。同时定义好序列的权值为 \prod\limits_{x=1}^{M}\sum\limits_{i=1}^{N}\mid x \in S_i \mid，问所有长度为 N 的好序列的权值和，结果对质数取模。（1 \le N,M \le 2 \times 10^5）

分析：直接考虑如何构造好序列来算出权值显然不可取，我们不妨假定 S_1 已确定，同时我们已知相邻两个集合相差的元素 X_1,X_2,\ldots,X_{N-1}，那么此时整个序列我们都是已知的，那么对于 S_1 而言每一种元素是否选取都能得到一个可能的好序列，即产生了 2^M 种可能的好序列。而我们令 A_x 表示 x \in S_1 时的 \sum\limits_{i=1}^{N}\mid x \in S_i \mid，B_x 表示 x \notin S_1 时的 \sum\limits_{i=1}^{N}\mid x \in S_i \mid，那么 S 对答案的贡献就能表示为 (A_1+B_1)\cdot(A_2+B_2)\cdot...\cdot(A_M+B_M)，而这个数是等于 N^M 的，因为 A_i+B_i=N。然后我们考虑 X 的取值，此时 X 显然共有 M^{N-1} 种取法，所以答案为 N^M \times M^{N-1}。

E：\texttt{Examination}（赛后写出）

题意：给出 N 对数 A_i,B_i，现对 A 进行若干次交换操作，使得所有的 A_i 均 \ge B_i。问最终未被操作过的数的最大数目。（1\le N \le 3 \times 10^5,1 \le A_i,B_i \le 10^9）

分析：定义 sum_t = \sum \limits_{i=1}^{N}\mid A_i \le t \mid - \mid B_i \le t \mid。先对所有的数进行离散化。显然若所有的 B_i 均 \le A_i，那么答案显然为 N。因此我们考虑记录下所有 B_i>A_i 的位置，对于这些位置里的每一个数，我们需要贪心地找到最小的 sum_t > 0 的位置 t，然后我们找到满足 B_i \le t 并且 t< A_i 的位置与其交换，同时我们可以观察得出此时如果有多个选择，我们一定会选择 A_i 最大的数，那么我们考虑一个优先队列记录下待解决的数，然后逐一枚举满足 sum_t>0 的位置然后匹配即可。

\texttt{\color{blue}CF 1694 (div 2)}（VP）

赛时：\text{\color{blue}ABCDE}

赛后：\text{\color{blue}F}

A：\texttt{Creep}

题意：给定两个数 a,b，构造一个含有 a 个 0，b 个 1 的 01 串 S，使得 \max\limits_{i=1}^{n} \mid i-\sum\limits^{i}_{j=1}S_j \mid最小。（1 \le a,b \le 100）

分析：通过观察可知，显然最优的方案为 01 交替摆放，因此我们尽量 01 摆放，而对于多出来的 0 或 1 我们再统一输出即可。

B：\texttt{Paranoid String}

题意：定义一个 01 序列 T 是好序列，当且仅当其能进行如下操作 |T|-1 次：

• 将序列中出现的某一处 01 改为 1。
• 将序列中出现的某一处 10 改为 0。

现有一个长度为 n 的 01 串 S，问 S 中属于好序列的子序列数量。（1 \le n \le 2 \times 10^5）

分析：首先要先观察出一个性质：若一个串是好序列，当且仅当 |S|=1 或者 S_{|S|}=S_{|S|-1}，证明显然。

因此我们可以固定右端点，从左往右看是否满足 S_i=S_{i-1}，若满足则此时左端点只能取 i，反之左端点可取 [1,i]，直接统计即可。

C：\texttt{Directional Increase}

题意：一个长度为 n 的序列 a，一开始所有的值均为 0。给出一个长度为 n 的目标序列 b，现有一个光标位于 1 号位置，对其进行若干次操作（不妨令此时光标的位置为 pos）：

• a_{pos} \leftarrow a_{pos}+1,pos \leftarrow pos+1\quad(pos < n)
• a_{pos} \leftarrow a_{pos}-1,pos \leftarrow pos-1\quad(pos > 1)

要求在操作完毕后光标要回到 1 号位置，问是否能使得序列 a 与目标序列 b 完全相等。（1 \le n \le 2\times 10^5,-10^9 \le a_i \le 10^9）

分析：我们可以发现，整个序列最末尾的 0 不会对答案有任何影响。而且从结果上来看，我们可以大致将我们必须的操作理解成如下形式：选择某一对数 1 \le l<r\le n，让 a_l \leftarrow a_l+1,a_r \leftarrow a_r -1，虽然最后还会有一些限制，但显然无论我们怎么操作，我们整个数组元素总和是不变的（且必须保证为 0，否则无法令操作完毕后光标返回 1 号位置）。然后我们再来考虑不合题意的方案的特点，显然有 \forall 1 \le i < n,\sum\limits_{j=1}^{i}b_j > 0，且 \sum\limits_{i=1}^{n}b_i=0（除去末尾 0 的情况下），而其余情况都是合法的。

D：\texttt{Fake Plastic Trees}

题意：有一棵含 n 个节点的树，根为 1 号节点。每个节点都有一个权值 V_i（初始值为 0），同时给定两个序列 l,r。现对这棵树进行若干次操作，每次操作选择一条从 1 号节点开始的路径 b_1, b_2, \ldots, b_k，然后指定一个非下降序列 c(0 \leq c_1 \leq c_2 \leq \ldots \leq c_k)，令所有 v_{b_i}\leftarrow V_{b_i} + c_i，问使得 \forall 1 \le i \le n,l_i \le V_i \le r_i 的最小操作次数。（2 \le n \le 2\times 10^5,1 \le l_i \le r_i \le 10^9，数据保证有解）

分析：考虑树形 DP。记 f_i 表示最优操作下的 V_i，ans 表示最终的操作总数。

对于每一个节点 u，我们有：

• u$ 为叶子节点：$ans \leftarrow ans+1,f_u=r_u
• u$ 不为叶子节点：记 $sum=\sum\limits_{v \in son_u}f_v$，若 $sum \ge l_u$，此时我们不需要额外操作，直接让 $f_u \leftarrow sum$；若 $sum < l_u$，此时我们需要额外操作，让 $ans \leftarrow ans+1,f_u=r_u

可以证明此时我们的决策是最优的，直接输出 ans 即可。

E：\texttt{Keshi in Search of AmShZ}

题意：有一个 n 个点 m 条边的有向图，现要从 1 号节点走到 n 号节点。每一个时刻可以如下操作：

• 从当前位置随机选择一条未被封锁的边并行走它。
• 指定某一条边并将其封锁。

通过这些操作，问无论如何都能到达 n 号节点至多需要多少时间。（2\le n \le 2\times 10^5,1 \le m \le 2 \times 10^5）

分析：显然我们可以将原问题理解为先封路再移动，同时我们要保证封路后从 1 开始不能走到环或死路。我们不妨先考虑整个图为有向无环图的情况：不难发现，其实“随机走一条”可以等同于“走最差的一条”，因此我们记录 f_x 表示 x 到 n 的最短路，那么可以通过 dp 求出每个节点 x 的 f_x，令将 x 号节点所有出边所连的节点 v 的 f_v 降序排序得到 d_1,d_2,\ldots,d_k,便可以枚举封锁的出边数量，得到f_x=\min\limits_{1 \le v \le k}d_v+v，在反图上跑 dp 即可。

那假设我们的图中有环，那么我们可以借鉴类似于 Dijsktra 的思路：即我们初始令 f_n=0，其余的位置均为正无穷。然后我们定义 d_u 表示仅用已确定的路径时的 f_u。可以发现，所有的 d_u 中最小的那个一定是已确定的（类似于 Dijsktra），因此用小根堆维护当前所有的 d，然后跑 Dijsktra 即可。

F：\texttt{Decinc Dividing}（赛后写出）

题意：定义一个序列 a 是好的，仅当可以通过删除 a 的一个单调递减子序列（可以为空）使得 a 单调递增。现给定一个 1\sim n 的排列 p，求出 p 有多少子段是好的。（1 \le n \le 2 \times 10^5）

分析：考虑 DP。记 f_{i,0/1} 表示第 i 个元素在当前递增序列/递减序列时递减序列/递增序列的最后一个元素的最大值/最小值。初始时有 f_{i,0}=-\infty,f_{i,1}=\infty,f_{1,0}=\infty,f_{1,1}=-\infty，那么在转移的时候我们直接分类讨论更新 f 数组，然后对于一个子序列 p_{l \sim r}，若我们在 DP 完后有 f_{r,0} \ne \infty 或者 f_{r,1} \ne - \infty，说明这个子序列是合法的。

此时我们我们枚举区间两个端点然后判断是 \mathcal{O}(N^3)，但可以发现我们固定左端点后移动右端点可以优化为 \mathcal{O}(N^2)。

考虑更进一步，我们从大到小枚举左端点，然后要么我们能在有限次操作内做到 f_{k,0/1} 与原来的相同，此时往后的转移已在之前的操作中完成，直接继承之前的右端点即可；要么我们发现无法继续更新了，这时直接更新右端点即可。

可以证明在这种优化下我们的时间复杂度能进一步降至线性：在某个 i 之前找到最右的 j 满足 p_j>p_{j+1}，这时 p_j 和 p_{j+1} 不能同时处于递增序列中，因此此时 f_{i_0} \in \{p_j,p_{j+1},-\infty \}；要么如果不存在这样的 j，那么 f_{i,0}=\infty，因此 f_{i,0} 最多有 4 种取值，同理 f_{i,1} 最多有 4 种取值，那么 f_i 最多只会被修改 7 次，总复杂度为线性。

\texttt{\color{blue}CF 1670(div 2)}（VP）

赛时：\text{\color{blue}ABCDEF}

A：\texttt{Prof. Slim}

题意：给出一个长度为 n 的序列 a，现对其进行若干次操作，每次操作选择两个符号不同的数，交换它们的符号。问能否通过若干次操作使得整个序列单调不下降。（1 \le n \le 10^5,0 < |a_i| \le 10^9）

分析：显然交换操作不会改变序列内正数和负数的数量，那么不妨设 sum 为序列内负数的数量，显然最终序列内前 sum 位均为负数，后 n-sum+1 位均为正数。因此直接修改整个序列的数的符号然后判断即可。

B：\texttt{Dorms War}

题意：给定长度为 n 的小写字母组成的字符串 s，给定 k 个特殊字符。每次可以删掉 s 中所有特殊字符之前相邻的一个元素，当最后存留下来的特殊字符前都没有相邻元素时，再删除就会报错。问最多进行多少次删除操作可以不报错。（2 \le |s| \le 10^5,1 \le k \le 26）

分析：显然每一个特殊字符对答案可能的贡献为其与上一个特殊字符的位置差（第一个的贡献为其位置），因此我们记录下每个特殊字母的位置 pos_1,pos_2,\ldots,pos_k，那么答案即为 \max\{pos_1,\max\limits_{1<i \le k}\{pos_i-pos_{i-1}\}\}。

C：\texttt{Where is the Pizza?}

题意：给定两个 1 \sim n 的排列 a,b 和一个待补全的排列 c，已知 \forall 1 \le i \le n,c_i=a_i 或 c_i=b_i，问补全排列 c 的方案数，结果对质数取模。（1 \le n \le 10^5，数据保证至少有一种方案）

分析：考虑将这个问题转化为图论问题。对于所有的 i，连一条 a_i \rightarrow b_i 的边，这样就能形成若干个环。对于每一个环，如果其大小为 1 或者环上有数字已经确定，那么这个环上所有的数字均已确定，对答案的贡献为 \times 1，反之这个环对答案的贡献为 \times 2。

D：\texttt{Very Suspicious}

题意：有一个无穷大的平面蜂巢，它由无数个正六边形拼接形成。现可以在这个平面蜂巢画直线，满足这条直线平行于某个正六边形的某条边。直线和六边形的边能够围成正三角形。要求每个正三角形内部不能有其它的直线和边存在，问构造至少 n 个正三角形至少需要多少条直线。（1 \le n \le 10^9）

分析：我们可以发现，每有两条直线相交与一点便能增加两个新的正三角形，因此我们可以将原问题转化为求直线间两两交点的数量，若能做到便可以二分答案求解原问题。

通过观察可知，整个平面内的直线只有三种斜率，不妨令这三种斜率的直线条数分别为 x,y,z\quad(x+y+z=n)，那么交点个数为 x \cdot y + x \cdot z + y \cdot z，现在我们想最大化这个值，那么易发现应该令 x,y,z 尽量相近即可，因此原问题得解。

E：\texttt{Hemose on the Tree}

题意：给出一棵共有 2^p 个节点的树，现要求构造一种方案：包括给出这棵树的根、每个点的点权、每条边的边权（要求点权和边权要构成一个 1 \sim 2^{p+1}-1 的排列）。要求对于构造出的树，从根节点开始到所有的点及边的路径的权值异或和的最大值最小。（1 \le p \le 17）

分析：通过观察样例，我们会发现其最大异或和为 2^p，因此我们不妨假设最终这个最大异或和为 2^p。然后我们考虑如何证明这个东西：我们将所有的 2^{p+1}-1 个数按照 \bmod 2^p 的余数分为 2^p 组，显然 2^p 单独归为一组，那么我们令根节点的点权为 2^p。而我们可以发现：对于所有 >2^p 的数，其在异或 2^p 后显然会 <2^p，而如果再异或上与这个数同组的另一个数（即 x-2^p），那么当前结果又会变为 2^p。

由此我们得出一个思路：我们令根节点的点权为 2^p，然后往下搜索，设当前已遍历 c 个节点，若当前异或和为 0，则令下一条边的边权为 c，其所连的点的点权为 c+2^p，反之则令边权为 c+2^p，点权为 c，这样就能保证每条路径的最大异或和为 2^p 了。

通过分析上述流程，我们发现整个构造的过程与树的结构无关，因此我们直接令根节点为 1，然后跑一遍 dfs 即可。

F：\texttt{Jee, You See?}

题意：给定 4 个整数 n,l,r,z，求满足以下条件的长度为 n 的序列 a 的个数：

• l \le a_1 + a_2 + \dots a_n \le r
• a_1 \oplus a_2 \oplus \dots \oplus a_n = z

结果对质数取模。（1 \le n \le 1000,1 \le l \le r \le 10^{18},1 \le z \le 10^{18}）

分析：设 Q(x) 表示满足 1 \le \sum\limits_{i=1}^{n}a_i \le x 且 a_1 \oplus a_2 \oplus \ldots \oplus a_n =z 的序列数，那么结果可以表示为 Q(r)-Q(l-1)。因此我们重点考虑如何求出 Q(x)。

我们每次将 n 个数的同一位统一放置。记 f_{i,j} 表示由低至高前 i 位已经放置好且后面至多可进位至这一位 j 次时的方案数。设 j 表示 i+1 位从 0 \sim i 位进位的位数，now 表示当前位置最多放 1 的数量，t 表示第 i 位放的 1 的个数，则有 f_{i,\min(now-t,n)}\leftarrow f_{i,\min(now-t,n)}+f_{i+1,j}\times \dbinom{n}{t}。

注意到对于 now，因为可以向上一位进 j 位，如果当前限制位为 1，我们选择的 1 个数可以增加 1，令 \operatorname{get}(x, i) 表示 x 从低往高数二进制的第 i 位，则 now=2\times j+\operatorname{get}(x, i)，及我们的 now 应与 \operatorname{get}(x, i) 奇偶性相同。

\texttt{\color{red}ABC 269}

赛时：\text{\color{blue}ABCDE}

赛后：\text{\color{blue}F\color{red}GEx}

A：\texttt{Anyway Takahashi}

题意：给定四个整数 a,b,c,d，输出 (a+b) \times (c-d) 后输出 Takahashi。（-100 \le a,b,c,d \le 100）

分析：直接输出即可。

B：\texttt{Rectangle Detection}

题意：一个 10 \times 10 的由 . 组成的字符矩形，现对其进行修改，将某个子矩形内所有的点改为 #。给出操作后的矩形，求出子矩形的端点坐标。

分析：一边输入一边判断即可。

C：\texttt{Submask}

题意：给定一个数 n，输出所有的 x \mid x\ and n=x。（0 \le n <2^{60}，n 的二进制表示中 1 的数量不超过 15）

分析：直接类似于子集 DP 的不断令 i \leftarrow (i-1)\ and x 即可。

D：\texttt{Do use hexagon grid}

题意：有一个平面蜂巢，其中有 n 个黑点，问黑色连通块的数量。（1 \le n \le 1000,|X_i|,|Y_i| \le 1000）

分析：对于所有的点加一个偏移量，然后直接跑 DFS 即可。

E：\texttt{Last Rook}

题意：交互题。一个 N \times N 的棋盘上有 N-1 个互不威胁的车。显然棋盘上会有一个位置不会被攻击到，试在 20 次询问内找到这个位置，每次询问一个子矩阵，返回该子矩阵内车的个数。（2 \le N \le 1000）

分析：我们独立考虑行和列，则行和列各需要 10 次询问，显然为 \log n 的二分法。因此我们直接二分当前横/纵坐标的区间，若区间内车的个数 < mid-l+1，则说明未被攻击的位置在左半区间，否则则在右半区间。

F：\texttt{Numbered Checker}（赛后写出）

题意：给出一个 N \times M 的矩阵 a，将数字 1 \sim N \times M 按照从上往下，从左往右的顺序依次填入，然后对于所有 1 \le i \le N,1 \le j \le M,(i+j) \mod 2 =0，令 a_{i,j}=0。现有 Q 次询问，每次询问给出一个子矩阵，求该子矩阵内的元素总和。（1 \le N,M \le 10^9,1 \le Q \le 2 \times 10^5）

分析：数学题，定义 S_{x,y}=\sum\limits_{i=1}^{x}\sum\limits_{j=1}^{y}a_{i,j}，则可将原问题转化为 S_{rx,ry}-S_{lx-1,ry}-S_{rx,ly-1}+S_{lx-1,ly-1}，推一下 S_{x,y} 的求法即可。

\texttt{\color{red}ARC 107}（VP）

赛时：\text{\color{blue}ABCDE}

赛后：\text{\color{red}F}

A：\texttt{Simple Math}

题意：给定三个整数 A,B,C，求 \sum\limits_{a=1}^{A}\sum\limits_{b=1}^{B}\sum\limits_{c=1}^{C}abc，结果对质数取模。（1 \le A,B,C \le 10^9）

分析：通过移一下式子可得到 \sum\limits_{a=1}^{A}a\sum\limits_{b=1}^{B}b\sum\limits_{c=1}^{C}c，直接计算即可。

B：\texttt{Quadruple}

题意：给出两个整数 N,K，求符合如下条件的四元组 (a,b,c,d) 的个数（1 \le N \le 10^5,-2(N-1)\le K \le 2(N-1)）：

• 1 \le a,b,c,d \le N
• a+b-c-d = K

分析：将第二个限制分组，即改为满足 (a-c)+(b-d)=K 的数量。显然可以先枚举前半部分，算出两个部分中 a,b 取值的上下限，根据乘法原理对答案贡献即可。

C：\texttt{Shuffle Permutation}

题意：给出一个 N \times N 的矩阵，现对其进行若干次操作，每次操作选定某两行或者某两列，满足其对应的每一列/每一行的两个数之和 \le K，问交换后可能形成的矩阵有多少种，结果对质数取模。（1 \le N \le 50,1 \le K \le 2 \times N^2）

分析：首先不难看出来我们交换行的时候不会影响列交换时的判断，所以我们可以将行和列的情况分开讨论。

然后我们可以发现，若第 a 行与第 b 行可以交换，第 b 行与 第 j 行可以交换，那么这三行的可以随意排列其相对位置。这启发我们将可以交换的行/列归为一组，同时记录下每一组的大小，那么我们的答案即为 \sum\limits_{i=1}^{sum_{row}}Size_i\sum\limits_{j=1}^{sum_{col}}Size'_j。（sum_{row},sum_{col} 表示行和列的分组的数量，Size 表示该行/列的组的大小）

D：\texttt{Number of Multisets}

题意：给出两个整数 N,K，现将 K 分成 N 个数的和，满足每个数均可表示为 \frac{1}{2^i}（其中 i 为自然数），问符合题意的方案数，结果对质数取模。（1 \le K \le N \le 3000）

分析：考虑 DP，记 f_{n,k} 表示将 k 分为 n 个数相加的和的情况。对于分数的处理，我们不妨换一种思考方式，我们由原来的填入分数改为将前面所有位上的数 \times 2，同时将 k \times 2，那么我们就能保证我们每一次填入的数均为 1，避免了分数的处理。

因此，我们可以得到如下转移方程：f_{n,k}= \begin{cases} 0 , n < k \\ [n=0], k=0 \\ f_{n-1,k-1} +f_{n,k \times 2},otherwise \end{cases}

直接记忆化搜索即可。

E：\texttt{Mex Mat}

定义操作 \operatorname{Mex}(x,y) 有如下取值：

有一个 N\times N 的矩阵 a，满足 \forall 2 \le i,j \le N,a_{i,j}=\operatorname{Mex}(a_{i-1,j},a_{i,j-1})，现给出这个矩阵的第一行和第一列，问整个矩阵中 0,1,2 的数量。（1 \le N \le 5 \times 10^5,0 \le a_{i,j} \le 2）

分析：通过暴力打表可知，整个矩阵在按题意操作一定行/列后一定会出现循环，因此模拟前几行/前几列然后计算即可。

\texttt{\color{blue}CF 1754 (div 2)}

赛时：\text{\color{blue}ABCD}

赛后：\text{\color{blue}EF\color{red}}

A：\texttt{Technical Support}

题意：给出一个由 \texttt{Q} 和 \texttt{A} 组成的字符串 s，其中 \texttt{Q} 表示一个询问，而 \texttt{A} 表示一个回答。问所有的问题是否都得到回答。（|s|\le 100）

分析：考虑将 \texttt{Q} 记为 -1，将 \texttt{A} 记为 1，在输入的过程中进行累加即可。注意到有效的回答是一定得晚于询问的，因此当我们计算的和 > 0 的时候就要将这个和清零。

B：\texttt{Kevin and Permutation}

题意：给出一个 n，构造一个 1 \sim n 的排列 p，使得 \min\limits_{i=1}^{n-1}|p_i-p_{i+1}| 最大。（1 \le n \le 10^3）

分析：要想让题目中所求的值最大化，我们不难想出一种可能的构造方式：另相邻两项的差值尽可能相等，因此我们考虑将1 \sim n 的数分成 \left \lceil \frac{n}{2} \right \rceil 组，每一组放的是差值为 \left \lfloor \frac{n}{2} \right \rfloor 的两个数（若 n 为奇数则有一组为单独的 n），然后我们按顺序输出每个组即可。

C：\texttt{Make Nonzero Sum}

题意：定义一个序列 s_1,s_2,\cdots,s_{k-1},s_{k-2} 的权值为 \sum\limits_{i=1}^{k}(-1)^{i+1}s_i，现给出一个由 -1,0,1 组成的长度为 n 序列 a，问是否能够通过将 a 分成若干段，使得每一段的权值和为 0.若可以，则输出分组方案。（1 \le n \le 2 \times 10^5）

分析：有一个显然的结论：任何一个长度 >2 的序列都能分割成若干个长度不超过 2 的序列。因此，我们可以保证我们的操作仅和前一步有关。同时，我们会发现，若原问题有解，则一定存在一种分组方法，使得我们从左往右累加权值和的时候当前总和 |sum| \le 1，因此，考虑贪心，分类讨论取最优解，然后判断即可。

D：\texttt{Factorial Divisibility}

题意：给出一个长度为 n 的序列 a 和一个整数 x，问 \sum\limits_{i=1}^{n}a_i! 是否为 x! 的倍数。（1 \le n \le 5 \times 10^5,1 \le a_i \le x \le 5 \times 10^5）

分析：首先有 (x+1)\times (x!)=(x+1)!，因此我们可以考虑数组计数，统计每个数出现的次数，然后进行进位，判断最后是否有 <x 的数即可。

E：\texttt{Wish I Knew How to Sort}（赛后写出）

题意：给定一个长度为 n 的 01 串 s，现对其进行若干次操作，每次操作随机选择两个数 1 \le i < j \le n，然后判断是否满足 a_i >a_j，若满足则交换两个数。问将整个数组变为有序数组的期望操作数。（1 \le n \le 2\times 10^5，结果对质数取模）

分析：首先题目要求的数组有序可以转化为如下条件：使得最终整个数组前 g 位均为 0（其中 g 表示 s 中 0 的数量）。因此我们设 f_i 表示当 s 中前 g 位中有 i 位为 0 时的期望步数，那么我们所要求的就是 f_{cnt}（cnt 表示原串中前 g 位中 0 的数量。

考虑如何求出 f_i。我们发现，当前情况发生转移当且仅当前我们同时选中了前 g 位中的 1 以及后 n-g 位中的 0（而选中符合条件的数对的概率 p=\frac{(g-i)^2}{\frac{n \cdot (n-1)}{2}}），因此我们可以得到如下方程：

即 f_i=\frac{1}{p}+f_{i+1}。显然有 f_g=0，因此直接递推求出 f_{cnt} 即可。

F：\texttt{The Beach}（赛后写出）

题意：给出一个一个 n \times m 的沙滩的示意图，上面有若干障碍物和若干 1 \times 2 的椅子。现可旋转沙滩上的椅子（每一把椅子只能旋转一次），规定若将椅子旋转 90^{\circ} 所产生的的不满度为 p，将椅子旋转 180^{\circ} 所产生的不满度为 q，问是否能通过旋转已有的椅子使得沙滩上能放置新的椅子（即出现 1 \times 2 的空位），若可以，问总的不满度最小为多少。（1 \le n \times m \le 3 \times 10^5,1 \le p,q \le 10^9）

题意：将椅子旋转显然不好处理，因此我们不妨将椅子的旋转理解场上为空格的移动。对于一把椅子，我们从旋转前原有的空位向旋转后新产生的空位连一条权值为旋转产生的不满度的边，然后我们跑一遍最短路，便能得到将每个点变为空位所需的最小不满度，然后按照最终产生空位的方向计算答案即可。

\texttt{\color{red}ARC 128}（VP）

赛时：\text{\color{blue}ABC}

赛后：\text{\color{red}DEF}

A：\texttt{Gold and Silver}

题意：给出一个长度为 n 的序列 a，现有一个商人初始有 1 个钻石，每一天可以将钻石全部兑换为钻石粒或者将钻石粒兑换为钻石（也可以选择不兑换），且第 i 兑换的率均为 a_i（即可以用 a_i 个钻石粒换一个钻石或者用一个钻石换 a_i 个钻石粒）。现要最大化 n 天后钻石的数量，输出最终的方案。（1 \le n \le 2 \times 10^5,1 \le a_i \le 10^9）

分析：观察题目样例，我们可以得出一种最优策略：若存在 a_{i+1}>a_i，那么我们可以将第 i 天和第 i+1 天的操作取反，不难证明这样操作是正确的。

B：\texttt{Balls of Three Colors}

题意：给定三个数 a,b,c，现可进行若干次操作，每次操作选定两个数，令这两个数 -1，另一个数 +2。问是否能使得三个数中有两个数为 0，若可以，输出最少需要的操作步数。（1 \le a,b,c \le 10^8）

分析：观察可行的三元组的特征，我们会发现合法的三元组必须满足某两个数膜 3 的余数相同，而所需的步数为两者中较大的那个数。因此直接枚举三个数中的某两个数，判断后更新答案即可。

C：\texttt{Max Dot}

题意：给定三个整数 n,m,s 和一个长度为 n 的整数序列 a，要求构造一个长度为 n 的实数序列 v，满足：

• 0 \le v_1 \le v_2 \le v_3 \le \cdots \le v_n \le m
• \sum\limits_{i=1}^{n}v_i=s

求 \max\{\sum\limits_{i=1}^{n}v_i \cdot a_i\}。（1 \le n \le 50000,1 \le m \le 10^6,1 \le s \le \min(n \times m,10^6),1 \le a_i \le 0^6）

分析：考虑整个 v 序列，显然是由若干段连续的相同的递增的数字组成的，因此可以考虑分治解决问题。我们从后往前记录后缀和 sum_i 表示 i \sim n 的后缀和，那么我们显然想要贪心地取 \frac{sum_i}{n-i+1} 最大的位置，那么此时我们填入的 v 得到的权重一定是最大的，贪心填数即可。

\texttt{\color{red}ARC 120}（VP）

赛时：\text{\color{blue}ABCDE}

赛后：\text{\color{red}FF1}

A：\texttt{Max Add}

题意：给定一个长度为 n 的序列 a，对于所有 k = 1 \sim n，求 f(k)，其中 f(k) 表示进行 k 轮操作，第 i 轮操作令 a_i 加上当前整个序列内最大数（不妨令其为a_x），然后整个序列的总和。（1 \le n \le 2\times 10^5,1 \le a_i \le 10^9）

分析：考虑将最终答案拆分为序列内的数相加的形式。记 m=\max\limits_{i=1}^{n}a_i，显然在进行第 i 轮操作后，a_i 会成为整个序列内最大的数，因此我们可以将最终答案拆分成 (a_1+m)+(a_2+(a_1+m))+\cdots = n \cdot m + na_1+(n-1)a_2+\cdots，直接计算即可。

B：\texttt{Uniformly Distributed}

题意：给定一个 n \times m 的字符矩阵 s，矩阵内每个字符可能为 .，R，B。现将所有的 . 填入 R 或 B，要求从 (1,1) 到 (n,m) 的所有路径（每次移动仅能向右或向下）上 R 的总和相等，问合法填入方案数，结果对质数取模。（1 \le n,m \le 500）

分析：我们不妨从小的数据考虑，考虑最简单的 2 \times 2 的矩阵，我们发现合法的方案必定满足从右上到左下这条对角线上的字符相同，因此，我们可以进行扩展，记录下每条对角线的颜色出现情况，然后对每一条对角线进行讨论即可。

C：\texttt{Swaps 2}

题意：给定两个长度为 n 的序列 a,b，现在对序列 a 进行若干次交换操作，每次交换选择一个 1 \le i < n，令 a_i \leftarrow a_i -1,a_{i+1}\leftarrow a_{i+1}+1，然后交换 a_i 和 a_{i+1}。问能否使得序列 a 和 b 完全相等，若可以的话输出最小操作数。（2 \le n \le 2 \times 10^5,0 \le a_i, b_i \le 10^9）

分析：首先考虑合法性，我们考虑令 a_i \leftarrow a_i+i,b_i \leftarrow b_i+i，那么每一次操作可以转化为交换 a'_i 和 a'_{i+1}，然后看 a' 是否与 b' 相同即可。

对于最小操作数，我们将所有 b'_i 与最靠前的 a'_j 与其相同的位进行配对（不妨令匹配到的位置为 p_i），然后这一位的贡献可转化为 p_i-\sum\limits_{j=1}^{i-1}[p_j<p_i]，用树状数组维护即可。

D：\texttt{Bracket Score 2}

题意：给定一个长度为 2N 的序列 a，定义一个合法括号序列的权值为 \sum\limits_{i,j\text{是匹配位},i<j}|a_i-a_j|，构造一个长度为 2N 的括号序列，使得最终序列的权值最大。（1 \le N \le 2 \times 10^5,1 \le a_i \le 10^9）

分析：我们不难猜到最终序列的权值最大值为整个序列 a 中最大的 N 个数减去最小的 N 个数，然后显然里面的数相减的相对顺序是可以调换的，因此对两个部分的数分开进行括号匹配即可。

E：\texttt{1D Party}

题意：给定一个全是偶数的长度为 N 的序列 a，分别代表 N 个人的初始位置。现进行若干轮移动，每轮每个人可移动至多一个单位长度，定义某一时刻是可以举办派对的，当且仅当对于此时的序列 a 中每一个数 a_i，都有至少一个其他的数与其相等。问能举办派对的最小时刻。（2 \le N \le 2 \times 10^5,0 \le a_1 <a_2 < \cdots < a_n \le 10^9）

分析：考虑每个数的移动情况，无非是向左移动至一个人处然后向右移动，或者向右移动后向左移动，因此分类讨论后递推即可。

\texttt{\red{CF 1493 (div 2)}}（VP）

赛时：\text{\color{blue}ABC}

赛后：\text{\color{blue}DE\color{red}F}

A：\texttt{Anti-knapsack}

题意：给定两个整数 n,k，从 1 到 n 中选择最多的不相同的数，使得选出的数中不存在元素总和为 k 的子集。（1 \le k \le n \le 10^3）

分析：显然结果为 [\lceil \frac{k}{2} \rceil,k) \cup (k,n]。

B：\texttt{Planet Lapituletti}

题意：给定两个整数 h,m 和一个 h 小时 m 分钟制的时刻 t，问从 t 开始（包含 t）最近的能够在镜子中形成合法时刻的时刻。（1 \le h,m \le 100）

分析：显然直接从原时刻开始向后枚举，镜像可以理解为将原数翻转（包括前导 0），同时交换时和分的数字，判断是否镜像后时刻是否满足 <h 和 <m 即可。

C：\texttt{K-beautiful Strings}

题意：给定一个长度为 n 的小写字母字符串 s 和一个数 k，问字典序大于等于 s 的长度为 n 的字典序最小的字符串，满足新字符串中每种字母的出现次数均为 k 的倍数。（1 \le k \le n \le 10^5）

分析：由于要字典序最小，尽可能只修改后几位。因此考虑倒序枚举 n \sim 1，表示从这一位开始字典序比原串大，显然第 i 位后面随意填。枚举第 i 位填的字母（比 s_i 大），用前缀和统计每种字母的出现次数，判断是否能用后 n-i 位调整即可。

D：\texttt{GCD of an Array}（赛后写出）

题意：给定一个长度为 n 的序列 a，有 q 次操作，每次操作使得 a_x \leftarrow a_x \times y，在每次操作后，输出 \operatorname{gcd}_{i=1}^{n}a_i，结果对质数取模。（1 \le n,q,a_i,y \le 2 \times 10^5）

分析：考虑乘上一个数后对答案的贡献。我们将乘上的数质因数分解，将其分解为 p_1 \times p_2 \times p_3 \times \cdots \times p_k 的形式，然后对于每一个 p_i，它对答案有贡献当且仅当其余数也有未贡献的 p_i，因此我们用多重集记录下未贡献的每一个质因数所在的位置，同时开一个数组 cnt 记录有多少位置未贡献。对于一个 p_i，若加入多重集后满足 cnt_{p_i}=n，则表示 p_i 参与贡献，暴力删除一次 1 \sim n 即可。

E：\texttt{Enormous XOR}（赛后写出）

题意：定义 f(l,r)=\bigoplus\limits_{i=l}^{r}i，其中 \oplus 表示按位异或，现给定两个数二进制表示下长度为 n 位的整数 l,r，求 \max\limits_{l \le i \le j \le r}f(i,j)。（1 \le n \le 10^6）

分析：由于 n 的范围较大，因此不好直接枚举或者 dp，考虑发掘性质。

显然有当 l,r 首位不相同时答案为 2^{n}-1，即 l=2^{n-1},r=2^{n-1}-1，然后对于一个偶数有 x \oplus (x+1)=1，由此可知 f(l,r) 可以理解为许多个 1 异或上某些特定的数。因此当 r 为奇数或者 l+1=r 时答案为 r，否则我们则将 r 异或 1，即此时答案为 r+1。

\texttt{\color{red}CF 1748 (div 2)}

赛时：\text{\color{blue}ABC}

赛后：\text{\color{blue}DE\color{red}F}

A：\texttt{The Ultimate Square}

题意：给定一个整数 n，有 n 个木块，第 i 个木块的规格为 1 \times \lceil \frac{i}{2} \rceil，问用这 n 个木块组成的最大的正方形的边长。（1 \le n \le 10^9）

分析：观察样例 + 手推可知答案为 \lceil \frac{n}{2} \rceil。

B：\texttt{Diverse Substrings}

题意：对于一个字符串 a，若 a 中每个字符的出现个数均不超过 a 中不同字符的个数，则称 a 是合法的。对于一个长度为 n 的由数字组成的字符串 s，问合法的子串有多少个。（1 \le n \le 10^5）

分析：由于字符串由数字组成，那么合法子串的长度不超过 10 \times 10 = 100，因此直接枚举长度 \le 100 的子串，看是否合法即可。

C：\texttt{Zero-Sum Prefixes}

题意：给定一个长度为 n 的序列 a，现可进行若干次操作，每次操作选定一个为 0 的位置 i，将 a_i 改为任意的一个数。问 \sum\limits_{i=1}^{n}[\sum\limits_{j=1}^{i}a_j=0] 的最大值。（1 \le n \le 2 \times 10^5,-10^9 \le a_i \le 10^9）

分析：通过观察我们可知一次操作可以理解为将第 i 位及以后的每个位的前缀和整体偏移一个数，因此我们可以按照 0 出现的位置将原序列分解为若干段，每个段显然可以独立考虑，直接记录下每一段的前缀和的众数即为该段的贡献。

D：\texttt{ConstructOR}（赛后写出）

题意：给定三个整数 a,b,d，求一个整数 x 使得 d \mid (a \oplus x) 且 d \mid (b \oplus x)，其中 \oplus 表示按位或运算，且 0 \le x < 2^{60}。（1 \le a,b,d \le 2^{30}）

分析：首先令 a \oplus x = x,b \oplus x = x，则显然会有 (a \oplus b) \oplus x= x，我们模拟二进制下的除法，就可以发现 x 应可以表示为若干个 d \times 2^i 的和，从低位向高位模拟即可。

E：\texttt{Yet Another Array Counting Problem}（赛后写出）

题意：定义一个长度为 n 的序列 x 在子段 [l,r] 上的最大最左值为最大值第一次出现的位置。现给定一个长度为 n 的序列 A，问有多少个长度为 n 的序列 B，满足 \forall 1 \le l<r \le n，两个序列在 [l,r] 上的最大最左值位置相同，且有 1 \le B_i \le m，答案对质数取模。（n \times m \le 10^6,2 \le n,m \le 2 \times 10^5）

分析：对原序列建立大根笛卡尔树，容易发现区间最大最左值即为对应区间节点中深度最浅的点，也就是两个序列的笛卡尔树形态相同，构建笛卡尔树后树形 dp 即可。

\texttt{\color{blue}{CF 1771 (div 2)}}（VP）

赛时：\text{\color{blue}ABCD}

赛后：\text{\color{blue}EF\color{red}}

A：\texttt{Hossam and Combinatorics}

题意：给定一个长度为 N 的序列 a，问有多少个整数对 \{i,j\}(1 \le i,j \le N,i \ne j)，使得 |a_i-a_j| 最大。（1 \le N,a_i \le 10^5）

分析：直接统计序列内最大值和最小值的出现次数，直接相乘即可（要特判整个序列都相等的情况）。

B：\texttt{Hossam and Friends}

题意：给出 n 个人和这些人中的 m 对互不认识的人的编号，问存在多少对 (a,b)(1 \le a \le b \le n)，满足编号从 a 到 b 内所有人都与其他人为朋友。（2 \le n \le 10^5,0 \le m \le 10^5）

分析：要找到符合题意的区间，可以固定右端点求可能的左端点位置。考虑预处理出第 i 个人不认识的人中编号最大的那个（不妨令其为 j，则应有 j < i），然后显然左端点只会跟随这些编号移动，依次统计即可。

C：\texttt{Hossam and Trainees}

题意：给出一个长度为 n 的序列 a，问是否存在至少一对数 (i,j)(1 \le i < j \le n)，使得 \operatorname{gcd}(a_i,a_j)>1。（2 \le n \le 10^5,1 \le a_i \le 10^9）

分析：考虑对所有数进行质因数分解，然后看是否存在重复的质因子即可。

D：\texttt{Hossam and (sub-)palindromic tree}

题意：给定一棵含有 n 个节点的树，树上每个顶点都有一个字母，问树上所有顶点两两之间路径形成的字符串中，回文子串的长度的最大值。（1 \le n \le 2 \times 10^5）

分析：考虑 dp，记 f_{i,j} 表示从 i 到 j 路径中回文子串的长度最大值，不妨令 i 为 j 的祖先，则 f_{i,j} 可以由 f_{son_i,fa_j} 得来，预处理后记忆化搜索即可。

E：\texttt{Hossam and a Letter}（赛后写出）

题意：给出一个 n \times m 的字符矩阵，每个位置上的字符为 #，. 或 m，求矩阵内最大的 H 的大小，满足其中不存在 #，且至多有一个 m。（1 \le n,m \le 400）

分析：考虑预处理每个点向上/向下最多能到达几个点，枚举 H 形的中间一横的位置统计答案即可。

F：\texttt{Hossam and Range Minimum Query}（赛后写出）

题意：给出一个长度为 n 的序列 v，有 m 次询问，每次询问给出 l,r，问 l \sim r 内最小的出现奇数次的数，强制在线。（1 \le n \le 2 \times 10^5,1 \le v_i \le 10^9）

分析：出现奇数次意味着异或出来的数 \neq 0，因此用主席树维护异或和，查询直接在主席树上二分即可。

但这样显然能构造出不同数异或和为 0 的数据，因此我们将每个点的权值异或上一个随机数即可，这时出现错误的概率为 \frac{1}{A}，其中 A 为值域，正确性可以得到保证。

\texttt{\color{red}{CF 1763 (div 2)}}（VP）

赛时：\text{\color{blue}ABCD}

赛后：\text{\color{blue}E\color{red}F}

A：\texttt{Absolute Maximization}

题意：给定一个长度为 n 的序列 a，先可对其进行若干次操作，每次操作选择三个数 i,j,b，交换 a_i 和 a_j 二进制下的第 b 位，问最终序列内最大值与最小值之差的最大值。

分析：可以直接记录下所有数中每一个二进制位上是否出现过 0 和 1，若都出现过则可以将这一位加入答案贡献中。

B：\texttt{Incinerate}

题意：给定 n 个怪物的血量和攻击力 h_i,p_i，以及玩家初始攻击力 k，现进行若干次攻击直到玩家攻击力 \le 0 或全部怪物死亡，每次攻击对全体怪物造成 k 点伤害，并使 k 减少等同于当前最低血量的怪物的攻击力，问最终是否能使得所有怪物死亡。（1 \le n,k \le 10^5,1 \le h_i,p_i \le 10^9,\sum k \le 10^7,\sum n \le 2 \times 10^5）

分析：注意到 n 和 k 的数目都很小，所以可以发现总的攻击次数不会很多，直接模拟即可。

C：\texttt{Another Array Problem}

题意：给定一个长度为 n 的序列 v，现对其进行若干次操作，每次操作选定一对下标 (i,j)(1 \le i < j \le n)，将 v_i \sim v_j 中所有元素替换为 |v_i-v_j|，问最终数组中所有元素的和的最大值。（1 \le n \le 2 \times 10^5,1 \le v_i \le 10^9）

分析：可以手玩发现当 n>3 时可以使整个序列变为序列中最大值，而当 n \le 3 时直接讨论即可。

D：\texttt{Valid Bitonic Permutations}

题意：对于一个长度为 n 的排列 p，若存在 1<k<n，满足 p_1 \sim p_k 单调递增，p_k \sim p_n 单调递减，则称这个排列是合法的，求长度为 n 且满足 p_i=x,p_j=y 的合法排列数量，结果对质数取模。（1 \le i < j \le n \le 100）

分析：考虑区间 DP,将 n \sim 1 的数依次填入，每次向区间两边延伸，特殊处理第 i 和第 j 位即可。

E：\texttt{Node Pairs}（赛后写出）

题意：在一个有向图中，一个节点对 (u,v) 如果满足 u \ne v，u 能到达 v 且 v 不能到达 u，则称其为单向节点对。如果一个有向图刚好存在 p 对节点 (u,v)（u<v 且二者能互相到达），则称这是一个 p 可达图，求节点最少的 p 可达图的节点数。同时，定义图 G 为在所有节点数最少的 p 可达图中，单向节点对数量最多的图，求出图 G 中单向节点对的个数。（0 \le p \le 2 \times 10^5 ）

分析：题目中单向节点对需满足在两个强连通分量内，而一个有 k 个顶点的强连通分量内有 \frac{k \cdot (k-1)}{2} 对互相到达的节点因此可以考虑完全背包求解。