2023年 9月做题记录

edisnimorF / 2023-09-05 / 原文

CF1860F Evaluate RBS

考虑一个三元组的 $(a,b,c)$ 在特定 $(x,y)$ 下的权值 $ax+by$ 的含义：发现它是向量 $(a,b)$ 和向量 $(x,y)$ 的点积．

由于有 $\vec x \cdot \vec y=|\vec x||\vec y|\cos \langle \vec x,\vec y \rangle$．在 $(x,y)$ 变化的过程中，$|(x,y)|$ 对于所有三元组是相同的．那么只有夹角会影响三元组的权值比较结果．而夹角和 $(x,y)$ 的辐角，也就是 $x/y$ 相关．那么有做法：使 $t=x/y$ 从小变大，在不同的 $t$ 下判定最优情况是否可以构造合法的括号序列即可．

实现方法：预处理出每对可能的交换对应的 $t$．按 $t$ 从小到大依次执行它们．存在一个性质：当前 $t$ 需要重排（涉及交换）的位置构成一个区间．可以通过画图模拟：

考虑 $t\rightarrow t'$ 时若交换 $a,b$，那么肯定有交换 $a,b$；$b,c$．

判定是否存在合法的括号序列可以判断前缀和没有 $<0$ 的位置．那么我们维护前缀和中 $<0$ 位置的个数．每次暴力重构一个区间的前缀和，并更新那个系数，最后观察其是否 $=0$．

CF1685B Linguistics

首先判断，$s$ 中 $A$ 的数量应当等于 $a+c+d$，$B$ 的数量应当等于 $b+c+d$．

发现我们只需要在 $s$ 中找出 $c$ 个 $AB$ 和 $d$ 个 $BA$ 后自然可以满足要求：剩下的 $A$ 和 $B$ 暴力拆分就行了．

然后我们可以考虑 $s$ 中每一个极长的 $AB$ 交替出现的段落，其可以分成一下四种情况：

$ABA\cdots BA$
$ABA\cdots AB$
$BAB\cdots BA$
$BAB\cdots AB$

设一个这样的段落 $t$ 长度为 $l$．

当 $t$ 的两边字符相同的时候．也就是上面的情况 $1$ 和 $4$．可以发现其在最优利用的情况下，拆分 $AB$ 和 $BA$ 的数量之和一直为 $\lfloor l/2\rfloor$．
当 $t$ 以 $A$ 开头，以 $B$ 结尾．也就是上面的情况 $2$．当其仅用来拆分成 $AB$ 时，拆出来的数量为 $l/2$．否则拆分出的 $AB$ 和 $BA$ 的数量和为 $l/2-1$．
当 $t$ 以 $B$ 开头，以 $A$ 结尾．情况于上面类似．

考虑先凑出所有的 $AB$，再去凑 $BA$．首先肯定用第 $2$ 类串．然后再用 $1,4$ 类串，然后在用第 $3$ 类串．在使用第 $2$ 类串的时候需要从短的串开始用起，可以减少 $BA$ 串可能的浪费．在使用 $3$ 类串的时候从长的串开始用起，减少自己的浪费．

CF140C New Year Snowmen

每次贪心选数量最多的 $3$ 个．模拟选择过程直到不能选择位置．

正确性证明：感性理解一下，操作时尽量保留不同大小雪球种类数较多较好，而贪心选最多数量的 $3$ 种，保留的种类数是最多的．

CF79D Password

考虑原序列的差分序列．最终状态的差分序列是可以确定的．而其中为 $1$ 的位置不超过 $20$ 个．考虑逆推：使用最少的操作步骤使得从最终的差分序列恢复到全 $0$ 的差分序列．我们可以考虑设计状压 DP．

如何转移？考察操作在差分数组上的作用：在 $i$ 位置取反，在 $i+k$ 位置取反．不妨分类讨论：

$i$ 位置和 $i+k$ 位置都是 $1$．可以视作 $i$ 移动到了 $i+k$，然后两个 $1$ 抵消了．
$i$ 位置和 $i+k$ 位置都是 $0$．无意义的操作．
$i$ 位置和 $i+k$ 位置一个是 $0$，一个是 $1$．这时可以视作 $i$ 或 $i+k$ 位置的一个 $1$ 跑到了对面去．

那么可以这样转移：选择当前两个差分数组中为 $1$ 的部分，试图让它们抵消．代价可以通过最短路预处理．

CF1684D Trap

首先使用全部的跳跃肯定比不用完更优．假设不使用完，我们在最后的几个位置使用跳跃答案肯定更优．

在一个位置 $i$ 进行跳跃，对答案的减小量 $\Delta_i$ 为 $a_i-(n-i)$．考虑按 $\Delta_i$ 排序之后取最大的前 $k$ 个．但是我们发现，似乎如果我在 $i$ 位置跳跃后继续在 $j(j>i)$ 位置跳跃，$\Delta_i$的计算中不需要考虑 $j$ 位置额外增加的代价．
但其实对于任意一种选择 $k$ 个跳跃位置的方案，$\sum\Delta_i$ 中少计算的减小量是一样多的．

P3506 [POI2010] MOT-Monotonicity 2

非常神奇的题目．

有一个结论：对于每个位置，只需要保留到它为止最长能匹配的长度转移．然后就可以进行树状数组优化转移．

证明：
设 $f_i$ 表示一个位置匹配的最长长度．我们需要说明对于任意一个位置 $i$，$f_i$ 都可以由某个 $j(j<i)$ 的 $f_j$ 转移而来的．

考虑反证法，我们记 $n$ 是第一个不满足上述性质的位置．我们设其从 $m$ 位置的非最长匹配序列转移来．那么有 $f_m\ge f_n$．设 $f_m$ 代表的序列为 $b_1,b_2,\cdots b_{f_m}$．有 $b_{f_m}=a_m$．

$a_m=a_n$．

这是我们可以直接从 $b_{f_m-1}$ 对应的位置转移到 $n$．记这个位置为 $j$．由于 $n$ 是第一个不满足性质的位置，所以一定有 $f_j=f_m-1$．矛盾．
$a_m<a_n$．
1. $b_{f_n-1}<a_n$．这时可以从 $b_{f_n-1}$ 对应的位置转移到 $n$．同之前所说的原因矛盾．
2. $b_{f_n-1}\ge a_n$．我们在 $b$ 中向后找到一个满足 $b_j<a_n$ 的位置 $j$．显然这个位置一定是可以找到的，因为 $b_{f_m}=a_m<a_n$．我们从 $b_j$ 对应的位置转移到 $n$．显然 $j\ge f_n$．那么答案还会更优，显然矛盾．
$a_m>a_n$．

同上一样．

P7386 「EZEC-6」0-1 Trie

设计 $f_{i,j,0/1}$ 表示包含 $i$ 个 $1$，$j$ 个 $0$，以 $0/1$ 为根的 Trie 树节点个数．

存在转移：

\[\begin{aligned} f_{i,j,0}&=f_{i-1,j-1,0}+f_{i-1,j,1}+1\\ f_{i,j,1}&=f_{i,j-1,0}+1 \end{aligned} \]

将 $f_{i,j,1}$ 用 $f_{i,j-1,0}+1$ 带入后，可以得到 $f_{i,j,0}$ 的递推式：

\[f_{i,j,0}=f_{i-1,j-1,0}+f_{i-1,j-1}+2 \]

记 $g_{i,j}=f_{i,j}+2$．有

\[g_{i,j}=g_{i-1,j}+g_{i-1,j-1} \]

它符合组合数的递推式．启示我们最后的答案可以通过组合数表达．

CF1796D Maximum Subarray

提供一种时间复杂度与 $k$ 无关的线性做法．

假设 $x$ 为正数．先将所有 $a_i$ 都 $-x$．$k$ 个 $+x$ 的位置就可以表示成 $+2x$．我们肯定会贪心地将 $k$ 个 $2x$ 尽可能地加到我们选择的子区间中区．

假设我们选择的子区间为 $[l,r]$，我们不妨假设将后 $\min(r-l+1,k)$ 个位置 $+2x$．不妨设 $p=r-\min(r-l+1,k)$．这样看的话可以将子区间分成两段：$[l,p],[r-p+1,r]$．枚举 $p$，考虑如何求出对于当前 $p$ 最优的子区间．

$p$ 前面的部分可以使用最大子段和的贪心．记 $s_i=\sum_{j\le i}a_j$，$p$ 后面的部分的决策可以写成：

\[\min_{p<j\le p+k}(s_j+2xj)-(s_p-2xp) \]

由于 $j$ 对于任意 $p$ 的取值区间是固定的，那么可以单调队列优化转移．

当 $x$ 为负数时，考虑使 $-x\rightarrow x,n-k\rightarrow k$．即可以同 $x$ 为正数时一样讨论．

CF1553D Backspace

不妨从后往前考虑：
设当前匹配了 $T$ 的 $p$ 位置之后的部分，现在尝试去匹配 $T_p$．

当 $S_i\neq T_p$ 时，$S_i$ 必须按下 backspace．当 $S_i = T_p$ 时，显然这一位匹配是优的．考虑不使 $S_i$ 和 $T_p$ 匹配，则一定有 $S_j(j<i)$ 和 $T_p$ 匹配．在 $T_{p-1}$ 匹配位置之后到 $i-1$ 为止，$S$ 中需要删除的位置个数相同，而 $S_j$ 和 $T_p$ 匹配还需要要求保留 $j$ 位置．故可以贪心匹配．

P9575 「TAOI-2」喵了个喵 Ⅳ

鬼畜构造．

$n$ 为偶数．令 $x=1$．将 $n$ 分成大小相等的两半．
$a_i$ 为奇数．当 $n$ 为偶数时按上述构造．当 $n$ 为奇数时误解．考虑 $2 \nmid a_i$，故 $2 \nmid \gcd(a_i,x)$．由于两边分配的 $a_i$ 个数一定为一奇一偶，故 $\gcd$ 的和也一定是一奇一偶．不可能相等．

考虑正解．

我们将每个 $a_i$ 写成 $a'_i \times 2^{k_i}$，$x$ 写成 $x' \times 2^{k_x}$，并使得 $2 \nmid a'_i, x'$．那么 $\gcd(a_i, x)=\gcd(a'_i, x')2^{\min(k_i, k_x)}$．比较两边时，可以将所有 $\gcd(a_i, x)$ 都除以 $2^{\min(k_i(1 \le i \le n), k_x)}$．那么情况是，当 $\min$ 取到 $k_x$ 时，所有 $\gcd(a_i, x)$ 都为奇数，显然无解．故 $\min$ 取到 $\min(k_i)$．

不妨设 $b_i=a_i/2^{\min{k_i}}$．

当 $b_i$ 中存在奇数个奇数时，其加和势必为奇数，故无解．
当 $b_i$ 中存在偶数个奇数时，考虑构造 $x=2^{\min{k_i}+1}$．这是问题变成了有偶数个 $1$，和奇数个 $2$，是否可以将其分成加和相等的两半．显然是可以的．

CF1861F Four Suits

对于一个人 $x$ 答案怎么求？

考虑枚举其牌最多的花色 $i$．可以证明，贪心地分配给他最多的 $i$ 花色的牌是优的．假设 $x$ 将 $i$ 花色的牌分发出去一张与人交换，至多使得某个人最多的牌的数量少 $1$，而答案不会更优．

那么如何求出给 $x$ 分配 $i$，这种状态下其他人的最多的牌的数量的最小值呢？

首先二分答案 $\lambda$．考虑构建网络流模型判定答案是否合法．左部点和源点相连，边权为 $ned_i=K-\sum_{j=1}^{4}a_{i,j}$，代表除了 $x$ 以外的 $n-1$ 个人每个人还需要的卡片数量；右部四个点和汇点相连，边权为 $b'_i$，代表四种花色的剩余牌数．左部点 $i$ 和右部点 $j$ 的连边边权为 $\lambda-a_{i,j}$．我们需要判定这张图的最大流是否为 $\sum_{i \neq x}ned_i$．

由最大流等于最小割，我们尝试找到这张图的最小割．

暴力枚举右部点和汇点连边的割集 $S$，共有 $2^4=16$ 种．考虑在一种给定 $S$ 下左部点和源点，左部点和汇点的割集如何选择最优．发现对于左部点 $i$，当 $ned_i<\sum_{j\notin S}\lambda-a_{i,j}$ 时选择割掉和源点的连边 $ned_i$，否则割掉和所有未割掉右部点的连边．这个决策奇妙地对于每个 $i$ 是独立的．然后就有了一个 $O(n^2\log n)$ 的做法．

如何优化：关键在于减少求出最小割的时间．

回归那个决策割集方案的不等式上：

\[\begin{aligned} ned_i&<\sum_{j \notin S}\lambda-a_{i,j}\\ ned_i&<|S^c|\lambda-\sum_{j \notin S}a_{i,j}\\ ned_i+\sum_{j \notin S}a_{i,j}&<|S^c|\lambda \end{aligned} \]

发现我们只需要对于每个特定的 $S$，按 $ned_i+\sum_{j \notin S}a_{i,j}$ 排序即可．然后每次求最小割就可以二分快速找到一个分界点．

很有启发性的一道题，让我知道在二分图左右部某一部节点个数极小时可以暴力枚举那一部割集来求最小割．