随笔题解 Ct. 3
今天 ACM 实验室的一场原题大赛。
把其中一些觉得稍微有点意思的题跳了出来写一写题解。
今日题源 :
- A: 1426A (*800)
- B1: 1560F1 (*1900)
- B2: 1560F2 (*2100)
- C: 1509B (*1100)
- D: 1295E (*2200)
- E: 1608B (*1200)
- F: 1612D (*1600)
- G: 1624D (*1400)
- H: 1495C (*2300)
- I: 771A (*1500)
- J: 583A (*1000)
差点就 AK 了。以及被三队暴打。
C. TMT Document
给定一个长度为 $n$ 且只包含 $\texttt{T}$ 和 $\texttt{M}$ 两种字符的字符串 $S$。保证 $3\mid n$。现在需要把 $S$ 分割成若干个互不相交的子序列，且每个子序列都是 $\texttt{TMT}$（$\texttt{Towa Maji Tenshi}$）。试判断是否可能。
多组数据。$3\leqslant n\lt 10^5$。$\sum n\leqslant 10^5$。
$\texttt{1s/256MB}$。
其实……只要把前 $\frac{n}{3}$ 个 $\texttt{T}$ 和后 $\frac{n}{3}$ 个 $\texttt{T}$ 匹配，然后每对 $\texttt{T}$ 中间再塞一个 $\texttt{M}$ 就可以了。
但是考场被牛客还是哪里的一道 $\texttt{red}$ 题带偏了，写了好几发没过于是暂时搁置了。
最后回头重新看这道题的时候感觉当时的自己就是个**。
D. Permutation Separation
给定一个长度为 $n$ 的 $1\sim n$ 的排列 $p$ 和另外一个长度为 $n$ 的序列 $a$。
首先选定 $1\leqslant k\lt n$，将 $p$ 分割成 $S_L=\{p_1,p_2,\dots,p_k\}$ 和 $S_R=\{p_{k+1},p_{k+2},\dots,p_n\}$ 两个集合。然后执行如下操作若干次（可以是 $0$ 次）：
选定 $1\leqslant i\leqslant n$，支付 $a_i$ 的代价将 $p_i$ 其移动到另外一个集合——即，如果 $p_i\in S_L$，将 $p_i$ 从 $S_L$ 中删去并加入 $S_R$；反之亦然。
目标是不存在 $x\in S_L$ 和 $y\in S_R$ 使得 $x\gt y$。试求达成目标需要支付的最小代价。
值得注意的是，如果操作后 $S_L=\varnothing$ 或 $S_R=\varnothing$，算作目标被达成。
$2\leqslant n\leqslant 2\times 10^5$，$1\leqslant p_i\leqslant n$，$1\leqslant a_i\leqslant 10^9$。
$\texttt{2s/256MB}$。
虽然这是不符合题目要求的，但是让我们首先考虑一下 $k=0$ 时的情况。
定义 $f(i)$ 表示，在当前的 $k$ 的取值下，通过若干次操作将 $S_L$ 变为 $\{1,2,\dots,i\}$ 的最小代价。特殊地，$f(0)$ 表示将 $S_L$ 变为 $\varnothing$ 的最小代价。
不难得出
其中 $q$ 表示 $p$ 的逆排列。
如果现在将 $k$ 的值增加 $1$，考虑 $f(i)$ 会如何变化。
（以下的 $k$ 的值都是增加后的）
$f(p_k),f(p_k+1),\dots,f(n)$ 会减少 $a_k$，因为现在 $p_k$ 已经在 $S_L$ 中了。
相对地，$f(0),f(1),\dots,f(p_k-1)$ 会增加 $a_k$，因为现在 $p_k$ 已经不在 $S_R$ 中了。
那么对于当前 $k$ 的取值，答案显然是
最终答案就是 $k$ 的所有取值对应答案的 $\min$。这可以很容易地通过线段树维护区间加 + 区间 $\min$ 求解。
F. X-Magic Pair
给定 $(a,b)$ 和 $x$。执行如下两种操作之一若干次（可以是 $0$ 次）：
- 将 $a$ 变为 $|a-b|$。
- 将 $b$ 变为 $|a-b|$。
试求能否把 $a$ 或者 $b$ 变为 $x$。
多组数据。$1\leqslant a,b,x\leqslant 10^{18}$。
$\texttt{2s/512MB}$。
不失一般性，令 $a\leqslant b$。
令当前状态为 $(a_0,b_0)$。那么可以到达的状态有
- $(a_0,b_0)$
- $(b_0-a_0,b_0)$
- $(a_0,b_0-a_0)$
- $(b_0-2a_0,b_0-a_0)$
- $(a_0,b_0-2a_0)$
- $(b_0-3a_0,b_0-2a_0)$
脑补一下可以得出：如果令 $b_0=p\cdot a_0+q$，其中 $0\leqslant q\lt a_0$，那么 $a_0$ 和所有的 $p^\prime\cdot a_0+q$ 都会出现，其中 $0\leqslant p^\prime\leqslant p$。
但是如果持续操作到 $b\lt a$，那么事情会发生变化。
但是根据类欧几里得算法的相关结论，这个变化次数一定不会超过 $O(\log b)$。