小Z在无意中发现了一个神奇的OJ，这个OJ有一个神奇的功能：每日签到，并且会通过某种玄学的算法计算出今日的运势。在多次试验之后，小Z发现自己的运势按照一定的周期循环，现在他找到了你，通过他的记录，请你帮忙找出他运势的循环节。
第一行一个整数n，表示小Z记录的天数 接下来n行，表示每天的运势，用一个正整数表示，相同的整数表示相同的运势，不同的整数表示不同的运势。
一行若干个整数表示所有可能的小于等于n的循环节。
6 1 2 1 1 2 1
3 5 6
对于100%的数据，n<=365，每天的运势不会爆int
本题是一道水题。题目的意思即为让我们求出字符串的所有小于等于长度的周期，这应该都能理解，然后我们直接套用KMP模板，求出字符串的所有的Border，也就求出了所有的周期。上述文字看不懂的同学们可以参考2017年WC 的金策的《字符串算法》，然而我并没有链接。。。
就是一个KMP
#include<cstdlib>#include<cstdio>#include<algorithm>#define maxn 370using namespace std;int len,f[maxn],s[maxn];void KMP(){ f[0]=f[1]=0; for(int i=2;i<=len;i++){ int op=f[i-1]; while(op!=0&&s[op]!=s[i-1])op=f[op]; f[i]=((s[op]==s[i-1])?op+1:0); } return;}int main(){ /*freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);*/ scanf("%d",&len); for(int i=0;i<len;i++) scanf("%d",&s[i]); KMP(); int ans[maxn],cnt=0; int k=len; while(f[k]!=0){ans[cnt++]=len-f[k];k=f[k];} ans[cnt++]=len; sort(ans,ans+cnt); for(int i=0;i<cnt;i++){ printf("%d ",ans[i]); } return 0;}新闻热点
疑难解答
