求助最小表示法模板
查看原帖
求助最小表示法模板
64976
hewo楼主2021/10/5 21:20

看到第一篇题解,为什么要%n?

我试着写了不%n的,90pts,WA第7个点,求助大佬为什么。

代码

#include<bits/stdc++.h>

using namespace std;

const int MX=1*1000000+1000;
#define LL long long
#define inf 0x3f3f3f3f

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
    while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int n;
int s[MX];

inline int minget()
{
	int k=0,i=1,j=2;
	while(k<n&&i<=n&&j<=n)
	{
		if(s[i+k]==s[j+k]) k++;
		else if(s[i+k]>s[j+k])
		{
			i=i+k+1;
			k=0;
			if(i==j) i++;
		}
		else if(s[i+k]<s[j+k])
		{
			j=j+k+1;
			k=0;
			if(i==j) j++;
		}
	}
	return min(i,j);
}

int main(int argc, char const *argv[])
{
	n=read();
	for(int i=1;i<=n;i++) s[i]=read();
	int f=minget();
	for(int i=f;i<=n;i++) printf("%d ",s[i]);
	for(int i=1;i<=f-1;i++) printf("%d ",s[i]);
	return 0;
}
2021/10/5 21:20
加载中...