本文主要是介绍codeforces582C. Superior Periodic Subarrays，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
传送门：http://codeforces.com/problemset/problem/582/C
思路：首先观察题目条件，对于一个数a[i]能出现在“Superior Periodic Subarrays”
首先它要满足对于任意k属于N，a[i]>=a[i+k*n]
并且对于任意k属于N，a[i]>=a[i+k*s]
那么就是任意k属于N，a[i]>=a[i+k*d](d=gcd(s,n))
也就是a[i]是这些数中的最大值
于是我们枚举d=gcd(s,n)
显然d整除n
再求出f[i]表示以i结尾的最长“Superior Periodic Subarrays”长度
再记 cnt[i]表示1-i中有多少个j满足gcd(j,n)==d(可以改为gcd(j/d,n/d)==1)
那么这次对答案的贡献就是cnt[f[i]]
累加起来即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int maxn=400010;
typedef long long ll;
using namespace std;
int n,f[maxn],a[maxn],g[maxn],cnt[maxn];ll ans;bool bo[maxn];int gcd(int a,int b){return !b?a:gcd(b,a%b);}int main(){scanf("%d",&n);for (int i=0;i<n;i++) scanf("%d",&a[i]),a[i+n]=a[i];for (int d=1;d<n;d++){//枚举GCD(n,s)if (n%d==0){memset(bo,0,sizeof(bo));for (int k=0;k<d;k++){//枚举起点g[k]=0;for (int i=k;i<(n<<1);i+=d) g[k]=max(g[k],a[i]);//找出这些相隔为d的数之间最大的数for (int i=k;i<(n<<1);i+=d) if (a[i]==g[k]) bo[i]=1;//如果一个数是这些数中最大的才可能在子数列中 }f[0]=bo[0];//以i结尾的"卓越子序列"最长可能长度 for (int i=1;i<(n<<1);i++){if (bo[i]) f[i]=f[i-1]+1;else f[i]=0;f[i]=min(f[i],n-1);}cnt[0]=0;//1-i中有多少个数与n的gcd为枚举的d for (int i=1;i<(n/d);i++) cnt[i]=cnt[i-1]+(gcd(i,n/d)==1);//要把Gcd(s,n)==d化简成gcd(s/d,n/d)==1，不然会被卡 for (int i=n;i<(n<<1);i++) ans+=cnt[f[i]/d];/*for (int i=1;i<n;i++) cnt[i]=cnt[i-1]+(gcd(i,n)==d);for (int i=n;i<(n<<1);i++) ans+=cnt[f[i]];*/}}printf("%I64d\n",ans);return 0;
}
/*
180
7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 1 2 7 3 5 8 1 10 7 6 5 10 3 2 7 3 1 8 8 10 7 6 5 10 3 1 7 3 1 8 8 10 7 6 5 10 3 2 7 1 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 1 1 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 7 6 5 10 3 2 7 3 5 8 8 10 1 6 5 10 3 2 7 3 5 8 1 10 7 6 5 10 3 2 7 3 5 8 8 10255
*/
这篇关于codeforces582C. Superior Periodic Subarrays的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
