BZOJ4827 [Hnoi2017]礼物

Solution

如果一串数的增加，不就等于另一串数减吗？

那么我们可以把答案写成另一个形式：

\(ans=\sum_{i=1}^n(x_i-y_i+C)^2\)

\(y\)可以是重新排列

那么疯狂拆一下式子,化简之后就是:

\(ans=\sum_{i=1}^nx_i^2+\sum_{i=1}^ny_i^2+\sum_{i=1}^nC^2+2*C*\sum_{i=1}^n(x_i-y_i)-2*\sum_{i=1}^nx_i*y_i\)

如果我们枚举\(C\),那么现在的任务就是算出\(\sum_{i=1}^nx_i*y_i\)的最大值,这样才能让\(ans\)最小.

怎么做呢?

如果把\(y\)数列翻转一下,那么就是:

\(\sum_{i=1}^nx_i*y_i=\sum_{i=1}^nx_i*y_{n-i}\)

这个不就是卷积?

考虑可以逆时针旋转怎么做?断环成链就好了啊.

那么就是把\(y\)串翻转然后复制一遍,求一个卷积然后走人了.

是的结束了.

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int N=1000010,Inf=1e9+10;const double Pi=acos(-1.0);int x[N],y[N],r[N],limit,n,m,Ans[N];struct node{ double x,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};} node operator*(const node b)const{return (node){x*b.x-y*b.y,x*b.y+y*b.x};}}A[N],B[N];void FFT(node *A,int type){ for(int i=0;i
             
              >1]>>1)|((i&1)<<(l-1)); FFT(A,1);FFT(B,1); for(int i=0;i

转载于:https://www.cnblogs.com/mle-world/p/10333135.html

你可能感兴趣的文章