ARC 做题记录（2024.3）
honglan0301
·
·
个人记录
whk 期间不太想碰电脑，在学校选些有意思/巧妙而又不太困难的东西来想。
3.10~3.31。
3.10
------------
$\small\color{green}\text{【赛时】ARC173C (2008)}$：
- 使用了复杂做法。首先特判对 $p_1,p_n$ 分别求出答案。
- 对于其他位置 $i$，我们从小到大扫值域，套路地转成 $01$ 序列，记作 $b$。判掉 $b_{i-1}=b_{i+1}$ 的情况（此时答案为 $3$），然后维护 $[i+1,n]$ 和 $[1,i-1]$ 的前缀/后缀 01/10 段长度即可，用线段树做到 $O(n\log n)$。
------------
$\small\color{green}\text{【赛时】ARC173D (2598)}$：
- 把 $\text{(,)}$ 转成 $1,-1$，那么首先有结论：有解当且仅当存在一个边权和为 $0$ 的合法回路，证明平凡（选前缀和最小的位置作为起始点即可）。
- 然后用强连通分量环基性质，合法回路显然是简单环的线性组合。先构造出一组边权和任意的方案，那么有解要求简单环能够拼出 $-\sum w_i$（不妨假设 $\sum w_i>0$）。由于 $\sum w_i$ 已经是一组线性组合，故不额外要求环长 $\gcd$ 满足约束，只需存在负环即可，spfa 做到 $O(nm)$。
------------
$\small\color{red}\text{【赛时】ARC173E (2869)}$：
- 寄了。待补 $n\equiv 2\pmod 4$。
## 3.11
$\small\color{green}\text{ARC113E (2789)}$：
- 手玩样例，考虑分讨。首先判掉全 $\texttt{a/b}$ 等特殊情况，然后：
1. 当 $s_n=\texttt{a}$ 时：此时显然不会操作 $\texttt{b}$（因为能够保证最终串里面 $\texttt{b}$ 都在前缀里），于是只需让末尾剩余的 $\texttt{a}$ 最多——那么贪心地把 $len>2$ 的 $\texttt{a}$ 连续段换到最后即可。
2. 当 $s_n=\text{b}$ 时：
(1)：当 $\sum [s_i=\texttt{a}]\equiv 0\pmod 2$ 时：此时保留所有 $\texttt{b}$ 即可。
(2)：当 $\sum [s_i=\texttt{a}]\equiv 1\pmod 2$ 时：
- 若后缀 $\texttt{b}$ 个数 $\leq 2$，则同 (1) 地处理，最终串形如 $\texttt{bbbbbabb}$。
- 否则先把一个 $\texttt{a}$ 换到最后，然后同 $1$ 地处理，注意把 $len\geq 2$ 的连续段换到最后较优，因为 1 中操作会舍弃掉其余连续段。
- 和 fry 讨论认为每步正确性均容易证明。
------------
$\small\color{green}\text{ARC112E (2659)}$：
- 想到枚举不被操作的数（形如一段区间，如果没有则枚举分界点，显然左侧每个数最后一次操作需为“移到第一个”，右侧为“移到最后一个”），然后限制转化为 $(a,b,m)$，表示有 $a$ 个需以 $1$ 操作归位的数，$b$ 个需以 $2$ 操作归位的数，当前剩余 $m$ 次操作。
- 考虑 dp，显然每类数内部的顺序唯一确定，于是 $f_{a,b,m}=(2a+2b)f_{a,b,m-1}+f_{a-1,b,m-1}+f_{a,b-1,m-1}$。
- 利用 CF506E 的套路，把 dp 转移放到 $n^2$ 个点的 DAG 上。注意到每个 $(a,b)$ 处自环的权值仅与 $a+b$ 有关，而所有非自环的边恰好会让 $a+b$ 减小 $1$，于是每条 $(a,b)\rightarrow (0,0)$ 的路径本质相同。
- 对 $(x,a-x)\rightarrow(0,0)$ 路径上自环的贡献预处理：$g_{a,m}=2ag_{a,m-1}+g_{a-1,m}$，那么就有 $f_{a,b,m}=C_{a+b}^{a}g_{a+b,m-a-b}$。
------------
$\small\color{green}\text{ARC110E (2973)}$：
- 首先想到 P9151 套路，新串每个字符都是原串的一段区间，于是先考虑解决判定“一个串能否变为某个字符”的问题。
- 然后手玩，fry 玩出来以下很优秀的性质：1212 不能变为单个字符，但 12123 可以变成 3；一个串最多只能变成一种字符；串内字符的顺序不影响结果。
- 那么考虑找不变量，和 fry 玩了大约 1h 后发现操作其实是选两个相邻的不等数，用异或和替换掉它们——不变量就是序列异或和。那么有关键结论：一个串 $s[1\dots n],n>1$ 能够变成单个字符当且仅当 $\bigoplus\limits_{i=1}^n \neq 0$ 且 $s$ 中不止有一种字符，最终字符即为 $\bigoplus\limits_{i=1}^n$。
- 继续 P9151 套路，考虑判定 $a_{1},a_2,\dots,a_n$ 能否变成 $b_1,b_2,\dots,b_m$，容易发现假如 $a$ 中不止有一种元素，那么贪心地匹配 $b_1,b_2,\dots,b_{m-1}$ 并对 $b_{m}$ 调整是优的。
- 那么 dp，$f_i$ 表示恰好匹配到 $a_{1},a_2,\dots,a_i$ 的 $b$ 串数量，转移和统计答案平凡。
------------
$\small\color{red}\text{ARC110F (2719)}$：
- 令人费解的脑瘫抽象题。没有训练意义。
## 3.12~3.14
$\small\color{green}\text{ARC114E (2514)}$：
- 最简单的一集。首先套路地把“随机选可选的线”转化成“随机选一个排列，跳过不能选的线”（容易发现两者等价）。
- 然后套路地拆贡献，每条线产生贡献都要求另一些线在它后面，那么 $ans=\sum \frac{n!}{qq_i}$，$qq$ 分类讨论易求。
$\small\color{green}\text{ARC117E (3166)}$：
- 很想尝试优化指数级暴力，但是全错了。
- 然后想到考虑前缀和序列 $s_{0\dots 2n}$。一个前缀和序列合法要求 $s_0=s_{2n}=0,|s_i-s_{i-1}|=1,\sum C_{cnt}^2=k$。那么用 CF840C 套路，按值域插数，对若干个连续段 dp。
- 记 $f_{T,i,j,p}$ 表示插完了 $[T,n]$ 的数，此时有 $i$ 个连续段，连续段总长为 $j$，目前 $\sum C_{cnt}^2=p$ 的方案数。转移时枚举 $T$ 的个数 $num$，并对 $T$ 分类讨论：
- 1. 当 $T\geq 0$ 时。显然每个连续段左右都必须可以插数（$s_{0}=s_{2n}=0$），那么 $f_{T,num-i+2,j+num,p+C_{num}^2}\gets f_{i,j,p}\times C_{num-1}^i$。
2. 否则 $T<0$。序列两端不能再插数，那么 $f_{T,num-i+2,j+num,p+C_{num}^2}\gets f_{i,j,p}\times C_{num-1}^{i-2}$。
- 显然 $ans=\sum\limits_{T\leq 0} f_{T,1,2n+1,k}$。总时间复杂度 $O(n^6)$，过了。题解采用了对正负数分别 dp 的方法，让时间复杂度消去一个 $n$，太过巧妙，我想不到。
$\small\color{red}\text{ARC114F (3545)}$：
- 和 fry 想出了假做法。待补。
$\small\color{green}\text{ARC114D (2723)}$：
- 套路地考虑异或差分。然后变成代价是距离的单点匹配，$O(n^2)$ dp 平凡。
$\small\color{green}\text{ARC118D (2448)}$：
- 套路地求出原根，在离散对数意义下要求即要求 $a_i-a_{i-1}\equiv a'/-a'/b'/-b' \pmod{p-1}$。显然若 $\gcd(a',b',p-1)\neq 1$ 则无解，否则走 S 形即可构造。
$\small\color{green}\text{ARC119D (2713)}$：
- fry 告诉我要建图。
- 然后染色相当于删点，显然每个连通块最后有且仅有一个点不被删。求答案平凡，构造时在生成树上以钦定不被删的点为根，从下到上删叶子即可。
$\small\color{red}\text{ARC119E (2502)}$：
- 只会三维数点，能过但没意义。
- 待补。
------------
## 3.17
$\small\color{green}\text{【赛时】ARC174A-E (<2400)}$：简单。
------------
## 3.18-3.22
$\small\color{green}\text{ARC111E (2541)}$：
- 当 $Ci-Bi\geq D-1$ 时显然不行，于是记可能的上界 $lim$，拆贡献 $\sum\limits_{i=0}^{lim} [\lfloor\frac{A+C_i}{D}\rfloor-\lfloor\frac{A-1+B_i}{D}\rfloor]=\sum \lfloor\frac{A+C_i}{D}\rfloor-\sum \lfloor\frac{A-1+B_i}{D}\rfloor$，是万欧板子。
$\small\color{red}\text{ARC104F (3213)}$：
- PKUWC D1T2 【对笛卡尔树形态 dp】 / 【缩减值域相关状态数】 两套路的简单应用。为了不算重，可以容斥/枚举最右侧 $\max$。
$\small\color{green}\text{ARC115F (3336)}$：
- 定义两点间距离为路径 $\max$，那么对每个点预处理出距他最近的 $h$ 更小的点 $to_i$，用堆贪心跳可以做到 $O(nk\log k)$。
- 考虑优化，记 $g_i=\text{dis}(i,to_i)-h_i$，那么由于 $\sum h_i$ 不增，按 $g_i$ 排序后扫一遍（每次跳到 $g$ 更大的位置为止）即可 $O(nk)$。
------------
## 3.24
$\small\color{green}\text{【赛时】ARC175A-D (<2400)}$：简单。
$\small\color{red}\text{【赛时】ARC175E (3223)}$：
- 神秘构造，会不了一点。待补。
## 3.26-3.28
$\small\color{green}\text{ARC120E (2653)}$：
- 二分答案，需要快速判定。考虑令 $f_{i,j}$ 表示在时刻 $j$ 时可能的 $\max a_i$。容易归纳证明其分 $O(1)$ 段，每段是斜率为 $1/-1$ 的线段，维护段即可 $O(n\log k)$。
$\small\color{orange}\text{ARC121D (2784)}$：
- 和 goodier 一起想。我们的逻辑是 $\color{green}\rightarrow$ ①每次必须吃两颗糖时大小配对最优 $\color{green}\rightarrow$ ②当 $a_i$ 全正时枚举前缀做两两配对最优 $\color{green}\rightarrow$ ③当 $a_i$ 有负有正时先将正负配对最优 $\color{green}\rightarrow$ ④AC.
- 以上每一步都很自然，但题解全是非常神秘的“补0”，属于是属于是了，感觉不太人类。
$\small\color{green}\text{ARC121E (2645)}$：
- 即求 $p_i$ 不是 $i$ 的祖先的排列数量。
- “不是 $i$ 的祖先”太难刻画了，因此从反面考虑容斥，钦定一些 $p_i$ 是 $i$ 的祖先，从下往上 dp。令 $f_{i,j}$ 表示 $i$ 子树内有 $j$ 个被钦定的 $p_i$ 的方案数（容易发现这代表子树里有 $sz_i-j$ 条可以任意拼接的链），转移平凡，$ans=\sum f_{1,j}\times (-1)^j$。