Skip to main content

最小表示法

参考资料​

例题​

洛谷 P13270 【模板】最小表示法​

洛谷 P13270 【模板】最小表示法

若长度为 nn 的字符串 ss 中可以选择一个位置 ii，使得 si⋯sns1⋯si−1‾=t\overline{s_i\cdots s_ns_1\cdots s_{i-1}}=t，则称 ss 与 tt 循环同构。字符串 ss 的最小表示为与 ss 循环同构的所有字符串中字典序最小的字符串。

给定一个长度为 nn 的字符串 ss，请求出 ss 的最小表示。

Code (1)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	string s;
	cin>>n>>s;
	s+=s;
	int i=0,j=1,k=0;
	while(k<n&&i<n&&j<n)
	{
		if(s[i+k]==s[j+k]){k++;continue;}
		if(s[i+k]>s[j+k])i+=k+1;
		else j+=k+1;
		if(i==j)j++;
		k=0;
	}
	cout<<s.substr(min(i,j),n)<<'\n';
	return 0;
}

洛谷 P1368 工艺​

洛谷 P1368 工艺

小敏和小燕是一对好朋友。

他们正在玩一种神奇的游戏，叫 Minecraft。

他们现在要做一个由方块构成的长条工艺品。但是方块现在是乱的，而且由于机器的要求，他们只能做到把这个工艺品最左边的方块放到最右边。

他们想，在仅这一个操作下，最漂亮的工艺品能多漂亮。

两个工艺品美观的比较方法是，从头开始比较，如果第 ii 个位置上方块不一样那么谁的瑕疵度小，那么谁就更漂亮，如果一样那么继续比较第 i+1i+1 个方块。如果全都一样，那么这两个工艺品就一样漂亮。

Code (1)
#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int> a(n<<1);
	for(int p=0;p<n;p++)
	{
		cin>>a[p];
		a[p+n]=a[p];
	}
	int i=0,j=1,k=0;
	while(k<n&&i<n&&j<n)
	{
		if(a[i+k]==a[j+k]){k++;continue;}
		if(a[i+k]>a[j+k])i+=k+1;
		else j+=k+1;
		if(i==j)j++;
		k=0;
	}
	for(int p=0;p<n;p++)cout<<a[p+min(i,j)]<<' ';
	return 0;
}