CF1965C Folding Strip 题解

369Pai · 2024-05-20 16:02:02 · 题解

手玩发现，不能再折叠的充要条件是剩下的串是一个 01 交替的字符串。

必要性显然，充分性考虑如下操作：从左往右扫描，遇到相邻相同的字符，就在之间折叠一次。

证明一下合法性：首先对于长度 > 2 的连续段，其可以视为长度 \le 2 的，奇偶性相同的连续段。

然后对这样缩过的串考虑从左往右，依次在长度为 2 连续段中间折叠，对于一次折叠，短的一半直接对应长的一半，长的一半多出来部分，可能对应空，可能对应若干次折叠后更长的。

即对于折叠之后的串，相同字母所在位置的奇偶性一定相同（否则会再次折叠），这也说明剩下的是一个 01 交替的串。

假设对原串所有相邻相同位置都进行折叠，会得到唯一一个（翻转视作同一个）01 交替的串。这是因为对于任意一种确定折叠位置集合，但折叠方向不同的折叠方式，都可以从内到外不停展开，得到形如“先向左折，再向右折，再向左折……”这样左右交替折的形式。

接下来证明，这个 01 交替的串是长度最短的。

对于一个由初始字符串 s 若干次折叠得到的字符串 t，如果在 t 的基础上继续折叠得到 t'，那么可以使用与上一段类似的展开方法，通过直接对 s 折叠，得到相同的字符串 t'。

而进行若干次折叠之后的串不长于原串，所以对于任意存在相邻相同位置的串，其都可以再进行折叠，得到唯一的，01 交替的，长度不长于它的串。

实现：模拟对原串所有相邻相同位置都进行折叠的过程，维护 l,r，表示相对的左右边界位置，以及 j 表示相对的当前位置，k\in\{1,-1\} 表示方向。每次遇到相邻相同位置，改变方向；否则 j'\leftarrow j+k，更新 l,r。

int l = 1 , r = 0;
for(int i = 0 , j = 0 , k = 1 ; i < n ; i++)
{
    if(i && s[i] == s[i - 1])k *= -1;
    else 
    {
        j += k;
        l = min(l , j);
        r = max(r , j);
    }
}

时间复杂度 \mathcal{O}(n)。