luogu P6187 [NOI Online 提高组]最小环（民间数据）

题目传送门

//为啥题目名称叫最小环但题目要求最大环啊!!

作为一个在考场上差一点切掉这道题的蒟蒻，我还是来发个题解说一下

这道题考的东西还是蛮多的，有思维，前缀和，数论，找规律

暴力很好打，有\(20\)分，爆搜即可

然后思考正解，对于一个\(k\)，我们讲每个\(a_{i}\)与\(a_{(i-k+n)\%n}\)建边，那么肯定会得到一些环，我们以k为距离来跳跃边，则当跳跃\(s\)次且\(ks\)被\(n\)整除时就形成了一个环。那么我们就要求\(s\)

因为\(ks\)一定是\(n\)的倍数且\(s\)最小，那么\(ks\)就是\(\operatorname{lcm}(k,n)=\frac{nk}{\gcd(n,k)}\),那么\(s=\frac{n}{\gcd(n,k)}\)

那么环上点的个数确定了，接下来要决定使环上点权值最大的方案了。

定理1:当\(a+b=2n\)时，\(ab\)的最大值为\(n^2\)，且此时\(a=b=n\)。

证明:若\(a\)不为\(n\)，设\(a=n-x,b=n+x\)，那么ab=\((n-x)(n+x)=n^2-x^2\)，又因为\(n^2\)与\(x^2\)均非负，且\(x\neq n\)，小于原式。证毕。

有了这个定理，那么每个数肯定要和最近的数去配对，那么应该是每一段中的数都是在排好序\(a\)的中是连续的。设一个降序的排好序的环上的权值数列为\(f\)，\(f_n\)肯定要和\(f_{n-1}\)与\(f_{n-2}\)配对，以此类推，那么问题又来了，\(f_x,f_{x+1}\)要怎么和\(f_{x+2},f_{x+3}\)配对呢?

无非两种配法，最后证明出来是\(f_x,f_{x+2}\)为一对，其余为一对，具体证明过程留给读者自行思考

那么这道题不就好做了吗?\(O(n)\)枚举\(k\)，\(O(n)\)枚举统计答案，询问时直接输出答案。

那么恭喜你获得了\(80\)分的好成绩，我考试时也是栽在这里。看来我对前缀和还不太熟。

代码实现:

#include
#include
using namespace std;
long long n,m,a[200039],f[200039],s[200039],fs[200039],k,x,y,tot,pus,ans;
int main() {
//	freopen("ring.in","r",stdin);
	//freopen("ring.out","w",stdout);
	register int i,j,h;
	scanf("%lld%lld",&n,&m);
	for(i=1; i<=n; i++)scanf("%lld",&a[i]),ans+=a[i]*a[i];
	sort(a+1,a+n+1);
	f[0]=ans;
	for(i=1; i<=m; i++) {
		ans=0;
		scanf("%lld",&k);
		if(f[k]){printf("%lld\n",f[k]);continue;}
		tot=1;
		pus=1;
		do {
			pus=(pus+k-1)%n+1;
			tot++;
		} while(pus!=1);
		tot--;
		//printf("%lld\n",tot);
		for(j=1; j<=n/tot; j++) {
			ans+=a[(j-1)*tot+1]*a[(j-1)*tot+2]+a[j*tot]*a[j*tot-1];
			for(h=(j-1)*tot+3; h<=j*tot; h++)ans+=a[h]*a[h-2];
		}
		f[k]=ans;
		printf("%lld\n",ans);
	}
}

我们注意到，循环中有这样一行代码:

for(h=(j-1)*tot+3; h<=j*tot; h++)ans+=a[h]*a[h-2];

这明显是可以前缀和优化的，可以优化成\(O(ng(n))\)，\(g\)为欧拉函数，\(g(x)\)表示\(x\)的约数个数。那么我们得到代码:

#include
#include
using namespace std;
long long n,m,a[200039],f[200039],s[200039],fs[200039],k,x,y,tot,pus,ans,q[200039];
int main() {
	//freopen("ring.in","r",stdin);
	//freopen("ring.out","w",stdout);
	register int i,j,h;
	scanf("%lld%lld",&n,&m);
	for(i=1; i<=n; i++)scanf("%lld",&a[i]),ans+=a[i]*a[i];
	sort(a+1,a+n+1);
	f[0]=ans;
	for(i=3;i<=n;i++) q[i]=q[i-1]+a[i]*a[i-2];
	for(i=1; i<=m; i++) {
		ans=0;
		scanf("%lld",&k);
		if(f[k]){printf("%lld\n",f[k]);continue;}
		tot=__gcd(n,k);
		pus=n/tot;
		//printf("%lld\n",tot);
		for(j=1; j<=tot; j++) {
			ans+=a[(j-1)*pus+1]*a[(j-1)*pus+2]+a[j*pus]*a[j*pus-1]+q[j*pus]-q[(j-1)*pus+2];
		}
		f[k]=ans;
		printf("%lld\n",ans);
	}
}

这道\(TG\)的\(T3\)就被我们很容易地切掉了