题解 P6187 【[NOI Online 提高组]最小环(民间数据)】
xukuan
2020-03-09 22:18:51
这题是全场最好做的一题,构造方法很好想,是个人都猜的出,这里给出证明过程。
不妨设只有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;
}
```