CF1383

Div.1 vp.

A - String Transformation 1

若初始时存在 $A_i>B_i$ 就无解.

否则贪心,不难发现每种字符最多被改掉一次,从小到大枚举字符 $c$ ,考虑对串 $A$ 中的字符 $c$ 修改,

$A_i=B_i=c$ 的位置是不用改的,对于其他 $A_i=c$ 的位置,全部改成满足 $A_i=c,B_i\neq c$ 中最小的 $B_i$ 即可.

code

B - GameGame

从高往低考虑每个二进制位,若到某一位时,有奇数个 $a_i$ 在这一位上为 $1$ ,就能分出胜负了,

记有 $t$ 个 $a_i$ 在这一位上为 $1$ ,若 $t\bmod 4=1$ ,则先取 $1$ 就必胜了, 若 $t\bmod 4=3$ ,再讨论下 $n$ 的奇偶性即可.

若每一位都不能分出胜负,则最后为平局.

code

C - String Transformation 2

建一个有 $|\sum|$ 个点的有向图,对于每个 $i$ ,从 $A_i$ 向 $B_i$ 连边.
问题转化为只加 $k$ 条边,使得每个 $A_i$ 仍能到 $B_i$ ,最小化这个 $k$ ,即操作次数.

图上每个弱连通分量的答案是独立的,对于一个大小为 $s$ 的弱连通分量,有高论,答案为 $2s-1-|{\rm LDAG}|$ .
其中 $|{\rm LDAG}|$ 表示这个弱连通分量中,导出子图是 DAG 的最大子点集大小.

下面是简要证明.

考虑将边逐次加入到图中,并维护每个点 $x$ 所属的某个合法 DAG 子图大小 $siz(x)$ ,记 $sum=\sum siz(x)$.
初始时 $siz(x)=1,sum=s$ ,加入一条边 $u\to v$ 时:

若 $u,v$ 已经弱连通,为了保证不出现环,将 $v$ 从 $u$ 的 DAG 子图中删掉,弱连通分量个数不变,而 $sum$ 减少 $1$ .
否则,可以将两者的 DAG 子图合并,弱连通分量个数减少 $1$ , 而 $sum$ 不变.

最后弱连通分量的个数为 $1$ ,说明有 $s-1$ 条边用于减少弱连通分量个数, $k+1-s$ 条边用于减少 $sum$ .
这说明最后的 $sum$ 为 $2s-1-k$ ,而最大的 $sum$ 就是 $|{\rm LDAG}|$ ,此时 $k$ 最小,为 $2s-1-|{\rm LDAG}|$ .

求每个弱连通分量的 $|{\rm LDAG}|$ 可以用状压 dp 求出每个子点集 $S$ 的导出子图是否为 DAG .
一个 DAG 一定存在拓扑序,按拓扑序顺序加点,若 $S$ 合法,且 $x$ 出边指向的所有顶点与 $S$ 没有交,则 $S\cup \lbrace{x\rbrace}$ 也合法.

code