礼物 bzoj-4827 Hnoi-2017

题目大意：给定两个长度为$n$的手环，第一个手环上的$n$个权值为$x_i$，第二个为$y_i$。现在我可以同时将所有的$x_i$同时加上自然数$c$。我也可以将第一个手环任意旋转。旋转后每一个$x$对应一个$y$，那么代价为$\sum\limits_{i=0}^{n-1} (x_i-y_i)^2$。求最小代价。

注释：$1\le n\le 10^5$，$0\le maxval \le 100$。

---

想法：

水题啊.....

推推式子，我们假设就加了$c$，那么总代价为$\sum\limits_{i=0}^{n-1} (x_i-y_i+c)^2$

$\Leftrightarrow \sum\limits_{i=0}^{n-1} ((x_i+c)^2-2y_i\cdot (x_i+c)+y_i^2)$

$\Leftrightarrow \sum\limits_{i=0}^{n-1} (x_i^2+y_i^2)+nc^2+2c\cdot \sum\limits_{i=0}^{n-1}(x_i-y_i)-2\sum\limits_{i=0}^{n-1} x_i\cdot y_i$

我们发现，上述式子分成了三部分：

显然第一部分是定值。

第二部分的话我们设$sum_x=\sum\limits_{i=0}^{n-1} x_i$，$sum_y=\sum\limits_{i=0}^{n-1} y_i$，那么如果$sum_x>sum_y$，显然$c$为0的时候取得最小值，反之用二次函数的对称轴来判断最小值即可。

剩下了第三部分：

我们要求对应位相乘的最大值

还没有旋转的时候我们发现就是对应位相乘的和。

如果进行了一次旋转，那么就相当于$x_1$和$y_{n-1}$配对，剩下的依次对应。

故此我们发现，x序列的开始一段对应乘上$y$的后面一段，$x$剩下的部分对应上$y$开头剩下的那部分。

我们将$y$翻转，发现其实每个答案就是两个卷积的和。

用$FFT$优化然后$O(n)$更新答案即可。

Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N 50010 using namespace std; typedef double db;const db pi=acos(-1);inline void Max(int &x,int y) {x=max(x,y);}inline char nc() {static char *p1,*p2,buf[100000]; return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}int rd() {int x=0; char c=nc(); while(!isdigit(c)) c=nc(); while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=nc(); return x;}struct cp{	db x,y;	cp() {x=y=0;}	cp(db x_,db y_) {x=x_,y=y_;}	cp operator + (const cp &a) const {return cp(x+a.x,y+a.y);}	cp operator - (const cp &a) const {return cp(x-a.x,y-a.y);}	cp operator * (const cp &a) const {return cp(x*a.x-y*a.y,x*a.y+y*a.x);}}a[N<<2],b[N<<2];void fft(cp *a,int len,int flg){	int i,j,k,t;	cp tmp,w,wn;	for(i=k=0;i
          
           k) swap(a[i],a[k]); for(j=len>>1;(k^=j)
           
            >=1); } for(k=2;k<=len;k<<=1) { wn=cp(cos(2*pi*flg/k),sin(2*pi*flg/k)); t=k>>1; for(i=0;i
            
             =sum2) printf("%d\n",all1+all2-2*ans); else { int ANS=all1+all2-2*ans; int dlt=(sum1-sum2)*2; int x=(-1*dlt)/(2*n); ANS+=min(n*sqr(x)+dlt*x,n*sqr(x+1)+dlt*(x+1)); cout << ANS << endl ; } return 0;}
            
           
          
         
        
       
      
     

小结：冷静下来还是非常水的。