题解：P15041 [UOI 2022 II Stage] 字母环

ycy25 · 2026-01-26 12:44:22 · 题解

思路

我们可以先将给定字符串复制一份接到原字符串后面，使原字符串从环变成链。这样我们解决了原字符串是个环的问题。

我们还需找出最长的按字母顺序的字符串。用打擂法，每次遇到不连续的字母都将当前记录的长度并与当前最大值比较即可。

代码

#include<cstdio>
char s[20001];
int main()
{
    int n;
    scanf("%d",&n);
    scanf("%s",s+1);
    for(int i=1;i<=n;i++)s[i+n]=s[i];
    int len=1,ans=1;
    for(int i=2;i<=2*n;i++)
    {
        if(s[i]-s[i-1]==1)len++;
        else
        {
            ans=(ans>len?ans:len);
            len=1;
        }
    }
    printf("%d",ans);
    return 0;
}