题解：P13270 【模板】最小表示法

Officer · 2025-07-14 13:08:47 · 题解

题目传送门

前置芝士

最小表示法

正文

好，我们来看一下题，这题很明显不能暴力，那考虑双指针，做法是先用两个第一串拼起来，也就是破环为链，再从中找第一串。

看一下代码。

#include<bits/stdc++.h>
using namespace std;
const int N=1e8+5;
char a[N];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        a[i+n]=a[i];
    }
    int l=1,r=2;
    while(r<=n)
    {
        int k=0;
        while(k<n&&a[k+l]==a[k+r])
        {
            k++;
        }
        if(k==n)
        {
            break;
        }
        if(a[k+l]>a[k+r])
        {
            l+=k+1;
        }
        else
        {
            r+=k+1;
        }
        if(l==r)
        {
            r++;
        }
        if(l>r)
        {
            swap(l,r);
        }
    }
    for(int i=l;i<l+n;i++)
    {
        cout<<a[i];
    }
    return 0;
}
/*
*/

双倍经验

P1368 工艺

P10476 Necklace