一些 trick（14）| 奇数位反转

MatrixGroup · 2024-11-13 12:01:28 · 个人记录

例题 1. CF1615F

对于两个长度为 n 的 01 串 s,t ，你可以对 s 进行两种操作：把相邻两个 0 变成 1 或把相邻两个 1 变成 0 ，定义 s 到 t 的距离为最少操作次数使得 s 变成 t ，如过没法变则距离为 0 。

现在你有两个不完整的字符串，可以把其中的 ? 变成 0 或 1 ，求所有情况所得到的两个 01 串的距离之和，模 P=10^9+7。

多测，\sum n\le 2000。

考虑奇数位的 01 反转，这样操作变成了交换相邻位。这样两个字符串可达当且仅当 1 个数相同，距离就是每个“第 k 个 1”的下标绝对值的差之和。容易使用组合数计算每个下标 i,j 的贡献，因为是范德蒙德卷积形式。即可做到 O(n^2+\log P)。

例题 2. QOJ #9565

给定一个长度为 n 的 012 串 s，你可以把所有 2 替换成 01，删除相邻的两个 0 或两个 1，求最终最短可能串。

多测，\sum n\le 5\times10^5。

考虑奇数位的 01 反转，这样操作变成了删除相邻 01，显然最终一定操作成全一样（否则还能删），故长度为 01 个数之差。把 2 换成 01 使得个数差最小是容易的，时间复杂度 O(n)。

已经加入 一些 trick。