专栏文章
题解:P13270 【模板】最小表示法
P13270题解参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miowe2o6
- 此快照首次捕获于
- 2025/12/03 02:14 3 个月前
- 此快照最后确认于
- 2025/12/03 02:14 3 个月前
前置芝士
正文
好,我们来看一下题,这题很明显不能暴力,那考虑双指针,做法是先用两个第一串拼起来,也就是破环为链,再从中找第一串。
看一下代码。
CPP#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;
}
/*
*/
双倍经验
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...