[HNOI2017]礼物

C++14(g++5.4) 解法, 执行用时: 471ms, 内存消耗: 109536K, 提交时间: 2020-03-20 18:42:13

#include<bits/stdc++.h>
typedef long long ll;
typedef double db;
using namespace std;
const ll N=2e6+1e5;
const ll MAXN=N;
const db pi=acos(-1.0);//π
ll n,m;
struct cp{//复数，x是实部，y是虚部 
    db x,y;
    cp(){x=y=0;}
    cp(db xx,db yy){x=xx,y=yy;}
}f[N],g[N],ans[N];
//复数运算 
cp operator + (cp a,cp b){
    return cp(a.x+b.x,a.y+b.y); 
}cp operator - (cp a,cp b){
    return cp(a.x-b.x,a.y-b.y);
}cp operator * (cp a,cp b){
    return cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}void FFT(ll n,cp *a,ll t){//t：1表示系数转点值，-1则相反 
    if(n<=1)return;//递归边界 
    ll mid=n>>1;
    cp a1[mid],a2[mid];
    //按系数奇偶性分出 a1, a2
    for (ll i=0;i<=mid-1;i++){
        a1[i]=a[i<<1];
        a2[i]=a[i<<1|1];
    }//递归 
    FFT(mid,a1,t);
    FFT(mid,a2,t);
    cp w1(cos(pi/mid),t*sin(pi/mid)),w(1,0),wt;
    //w1：就是 wn，t的运用使IFFT时能乘上共轭复数 
    //w是第一个单位根，就是实数 1 
    for (ll i=0;i<=mid-1;i++){
        wt=w*a2[i];
        //代入公式 
        a[i]=a1[i]+wt;//注意 a1[i] 表示是 n/2 次单位根 
        a[i+mid]=a1[i]-wt;
        w=w*w1;//下一个单位根 
    }
}
ll A[MAXN],B[MAXN],ANS[MAXN];
ll mult(ll n,ll m){
	for (ll i=0;i<=n;i++)
		f[i].x=A[i];
	for (ll i=0;i<=m;i++)
		g[i].x=B[i];
	ll k=1;
    while(k<=n+m)k<<=1;//记得吗？我们能处理的必须是2的整数次幂 
    FFT(k,f,1);
    FFT(k,g,1);
    for (ll i=0;i<=k;i++)
        ans[i]=f[i]*g[i];
    FFT(k,ans,-1);
    for (ll i=0;i<=n+m;i++){
		ANS[i]=(ll)(ans[i].x/k+0.5);
		//cout<<ans[i].x<<endl;
	}
}	
ll suma=0,sumb=0;
int main(){
    cin>>n>>m;
    for (int i=0;i<n;i++)
    {
    	cin>>A[i];
    	suma+=A[i];
    }
    for (ll i=0;i<n;i++){
    	cin>>B[n-1-i];
    	sumb+=B[n-1-i];
    	B[2*n-i-1]=B[n-i-1];
    }
    mult(n-1,2*n-1);
    ll mc=0;
    for (ll i=n;i<=2*n-1;i++)//cout<<ANS[i]<<' ';
		mc=max(mc,ANS[i]);
	//cout<<mc<<endl;
	ll z=0;
	for (ll i=0;i<n;i++)
		z+=A[i]*A[i]+B[i]*B[i];
	//cout<<z<<endl;
	z-=2*mc;
	//cout<<z<<endl;
	ll r=abs(suma-sumb)/n;
	ll rr=r+1;
	//cout<<r<<endl;
	z+=min(2*-abs(suma-sumb)*r+n*r*r,2*-abs(suma-sumb)*rr+n*rr*rr);
	cout<<z<<endl;
    return 0;
}

C++ 解法, 执行用时: 82ms, 内存消耗: 17144K, 提交时间: 2022-04-26 09:17:26

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const double pi=acos(-1.0);

struct node{
	double x,y;
	node(double a=0,double b=0):x(a),y(b){}
	node operator + (const node &b) const{return node(x+b.x,y+b.y);}
    node operator - (const node &b) const{return node(x-b.x,y-b.y);}
    node operator * (const node &b) const{return node(x*b.x-y*b.y,x*b.y+y*b.x);}
}a[500010],b[500010];
int rev[500010],ans[500010];

void fft(node F[],int len,int kk=1){
	for(int i=0;i<len;i++)
	    if(i<rev[i]) swap(F[i],F[rev[i]]);
	
	for(int i=1;i<len;i<<=1){
		node unit=node(cos(pi/i),sin(kk*pi/i));
		for(int j=0;j<len;j+=(i<<1)){
			node w(1,0);
			for(int k=0;k<i;k++,w=w*unit){
				node x=F[j+k],y=w*F[j+k+i];
				F[j+k]=x+y; F[i+j+k]=x-y;
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int n,m;
	ll A=0,B=0,C=0;
	cin>>n>>m;
	A=n;
	for(int i=0;i<n;i++){
		cin>>a[i].x; a[i+n].x=a[i].x;
	}
	for(int i=0;i<n;i++) cin>>b[n-1-i].x;
	for(int i=0;i<n;i++){
		int aa=a[i].x,bb=b[n-1-i].x;
		B+=aa-bb;
		C+=aa*aa+bb*bb;
	}
	B*=2;
	int len=1,bit=0;
	while(len<=3*n){
		len<<=1;
		bit++;
	}
	
	for(int i=0;i<len;i++) 
	    rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));
	    
	fft(a,len);
	fft(b,len);
	for(int i=0;i<len;i++) a[i]=a[i]*b[i];
	fft(a,len,-1);
	
	ll tmp=-0x3f3f3f3f3f3f3f3f;
	for(int i=n-1;i<=2*n-1;i++) tmp=max(tmp,(ll)(a[i].x/len+0.5));
	C-=2*tmp;
	int l=(-1.0*B/(2*A)),r=ceil(-1.0*B/(2*A));
	cout<<max(0ll,min(1ll*A*l*l+B*l+C,1ll*A*r*r+B*r+C))<<"\n";
	return 0;
}

详情