B4101

2021CHD · 2025-01-02 11:19:26 · 题解

题目大意

问字符串 S 是否可以被划分为 n(n>1) 个非空子串 S_1,S_2,\dots,S_n，满足对于所有 1\le i\le n，有 S_i=S_{n-i+1} 或 S_i=\text{rev}(S_{n-i+1})，若可以，求出 n 的最大值。

其中 \text{rev}(T) 表示将字符串 T 反转得到的结果。

题解

首先可以将 n>1 的限制解除再求出 n 的最大值，如果最大值是 1，就是无解，否则就是有解。

第一个显然的观察是 |S_i|=|S_{n-i+1}|。

首先可以考虑到，其实题目中给出的 S_i=\text{rev}(S_{n-i+1}) 的条件其实是无用的，原因见下图。

所有的 S_i=\text{rev}(S_{n+1-i}) 就可以表示成 |S_i| 对相等的字符串，而在这个过程中，n 不会减小。

（另外，如果 n 是奇数，那 S_{\frac{n+1}{2}} 始终和自身相等，所以不用考虑 S_{\frac{n+1}{2}}=\text{rev}\left(S_{\frac{n+1}{2}}\right) 这种情况）

所以现在只需考虑对所有的 i 都满足 S_i=S_{n-i+1} 的情况。

容易想到一个贪心：每次从两边贪心地选取最短的一个合法的串，直接把这个串选上并计入答案。如果选中的两个串有重叠部分，说明只能把最后一个串放在中间，答案就会是奇数。

实现是容易的，但是很多人可能忽略了一个问题：为什么这样是对的呢？

考虑一个位置，如果在这个位置上有两种可转移的串，下面这两张图说明了选短的串一定由于选长的串：

此时 n 会增加，而且选择二包含了选择一，所以选择二更优。

具体地，如果选择一的长度为 L_1，选择二的长度为 L_2>\frac{L_1}{2}，那一定有一种长为 (L_1-1)\bmod(L_1-L_2)+1 的选择。

另外，如果选择 1 是选择最中心的整个串，那显然不可能比选择 2 更优。

所以我们可以放心地说这个贪心是对的。

贴上代码和 AC 记录。

#include<cstdio>
#include<cstring>
using namespace std;
int n,i,j,ll,len,ans;
char s[11000];
main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    ll=1;
    for(i=1;i<=len;i++)
    {
        for(j=ll;j<=i;j++)
        if(s[j]!=s[len-i+j-ll+1])
        break;
        if(j>i)
        {
            ll=i+1;
            if(i*2<=len)
            ans=ans+2;
            else
            ans++;
        }
        if(ll*2-1>len)
        break;
    }
    if(ans==1)
    printf("NO");
    else
    printf("YES\n%d",ans);
}

后记

随便开了一道题，发现是黄的，花了几分钟做了出来，感觉是一道好题。

打开题解区，发现上面写着“算法分析：好像没有。”

……

于是我决定把证明补上。