CF1852D Miriany and Matchstick 题解

Schi2oid · 2023-08-07 13:23:37 · 题解

考虑一个朴素 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)。