CF1852D Miriany and Matchstick 题解

考虑一个朴素 dp，设 $f_{i,0/1}$ 表示考虑到前 $i$ 位，且第 $i$ 位填入 A/B 可能的相邻不同对数构成的集合，朴素转移时间复杂度 $O(n^2)$。试分析 dp 性质，观察发现所有 dp 中得到的集合为区间内抠去至多一个点，下面给出证明。 我们首先来观察转移过程是怎样的。第一种是第二行中 $i-1$ 填入的字母与第一行中 $i$ 填入的字母相同的情况，此时根据我们填入的字母与其相同与否，集合会整体平移 $0$ 或 $2$；第二种是不同的情况，此时无论我们如何填入字母，集合都会整体平移 $1$。由于我们只关心集合的相对位置关系，我们可以将转移视为将 $f_{i-1,0/1}$ 固定不动，将 $f_{i-1,1/0}$ 平移 $1$ 以及 $-1$，分别进行取或操作，得到 $f_{i}$。 首先容易发现，$f_i$ 的两个集合两侧端点的差的绝对值分别不超过 $2$。这是由于这两个集合是由一个固定的集合或上另外一个集合平移 $1/-1$ 得到的。现在，我们可以归纳说明一个更强的结论：$f_i$ 的两个集合中至多存在一个集合中存在且恰存在一个空位。 显然 $1$ 满足条件。假设 $i-1$ 满足此条件。由于区间过小时的情况比较神秘，我们在此只讨论 $r-l+1\ge5$ 的情况。对于区间更小的情况打表可证。在这种情况下，最坏是 $f_{i-1,x}$ 为 $[l,r]$ 抠去 $p(p\in(l,r))$，$f_{i-1,1-x}$ 为 $[l+2,r-2]$。此时，若 $i$ 不满足此条件，则存在一个 $p$ 使得 $[l+2,r-2]$ 无论平移 $1$ 还是 $-1$ 都无法覆盖到，而这显然无解。 故证毕。证得比原结论更强的结论，故原结论也证毕。 时间复杂度 $O(n)$。