题解 P6187 【[NOI Online 提高组]最小环(民间数据)】

xukuan

2020-03-09 22:18:51

Solution

这题是全场最好做的一题,构造方法很好想,是个人都猜的出,这里给出证明过程。 不妨设只有1个环 当同一组内的数字不超过4个的时候,直接大的配大的即可,这里看5个数字及以上的方法。 假设有$i,i+1,i+2,i+3,i+4$ 5个数字让你填。 显然大的要和大的在一起。 那么有两种填法: 1. $i+1,i+3,i+4,i+2,i$ 2. $i,i+3,i+4,i+2,i+1$ 不算i+4的贡献,那么第一种是$(i+1)(i+3)+(i+2)i$,第二种是$i(i+3)+(i+2)(i+1)$ 第一种大。 所以构造方法就是$1,3,5,7,...,n,...,8,6,4,2$ 那么环不止一个呢? 环的个数是$\frac{n}{gcd(n,k)}$,环的个数相同的解的个数相同。对于每一种我们暴力算,时间复杂度是$O(nd(n))$ 话说有没有和我一样的傻逼写记忆化的时候记了$k$。注意这里要记$gcd(n,k)$或者$\frac{n}{gcd(n,k)}$ 代码: ```cpp #include<bits/stdc++.h> #include<iostream> #include<cstdio> #define ll long long using namespace std; const ll N=200010; ll a[N],ans1,ans2,ans[N],n,m; inline ll read(){ ll x=0,tmp=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') tmp=-1; ch=getchar(); } while(isdigit(ch)){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return tmp*x; } inline void write(ll x){ if(x<0){ putchar('-'); x=-x; } ll y=10,len=1; while(y<=x){ y=(y<<3)+(y<<1); len++; } while(len--){ y/=10; putchar(x/y+48); x%=y; } } ll gcd(ll x,ll y){ return x%y==0?y:gcd(y,x%y); } int main(){ freopen("ring.in","r",stdin); freopen("ring.out","w",stdout); n=read(); m=read(); for(ll i=1; i<=n; i++) a[i]=read(); for(ll i=1; i<=n; i++) ans1+=a[i]*a[i]; sort(a+1,a+1+n); for(ll i=1; i<=n; i++) ans2+=a[i]*a[i+2]; ans2+=a[1]*a[2]+a[n-1]*a[n]; while(m--){ ll x=read(); if(x==0){ write(ans1); putchar('\n'); continue; } ll _Gcd=gcd(n,x); if(_Gcd==1){ write(ans2); putchar('\n'); continue; } ll k=n/_Gcd; if(ans[k]){ write(ans[k]); putchar('\n'); continue; } for(ll i=1; i<=n; i+=k){ for(ll j=i; j<=i+k-1; j++){ if(j+2<=i+k-1) ans[k]+=a[j]*a[j+2]; } ans[k]+=a[i]*a[i+1]+a[i+k-2]*a[i+k-1]; } write(ans[k]); putchar('\n'); } fclose(stdin); fclose(stdout); return 0; } ```