专栏文章

题解: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 条评论,欢迎与作者交流。

正在加载评论...