4827: [Hnoi2017]禮物

Time Limit: 20 Sec??Memory Limit: 512 MB
Submit: 1091??Solved: 748
[Submit][Status][Discuss]

Description

我的室友最近喜歡上了一個可愛的小女生。馬上就要到她的生日了，他決定買一對情侶手 環，一個留給自己，一 個送給她。每個手環上各有 n 個裝飾物，并且每個裝飾物都有一定的亮度。但是在她生日的前一天，我的室友突 然發現他好像拿錯了一個手環，而且已經沒時間去更換它了！他只能使用一種特殊的方法，將其中一個手環中所有 裝飾物的亮度增加一個相同的自然數 c（即非負整數）。并且由于這個手環是一個圓，可以以任意的角度旋轉它， 但是由于上面 裝飾物的方向是固定的，所以手環不能翻轉。需要在經過亮度改造和旋轉之后，使得兩個手環的差 異值最小。在將兩個手環旋轉且裝飾物對齊了之后，從對齊的某個位置開始逆時針方向對裝飾物編號 1,2,…,n， 其中 n 為每個手環的裝飾物個數，第 1 個手環的 i 號位置裝飾物亮度為 xi，第 2 個手 環的 i 號位置裝飾物 亮度為 yi，兩個手環之間的差異值為(參見輸入輸出樣例和樣例解釋)： \sum_{i=1}^{n}(x_i-y_i)^2麻煩你幫他 計算一下，進行調整（亮度改造和旋轉），使得兩個手環之間的差異值最小， 這個最小值是多少呢？

Input

輸入數據的第一行有兩個數n, m，代表每條手環的裝飾物的數量為n，每個裝飾物的初始 亮度小于等于m。 接下來兩行，每行各有n個數，分別代表第一條手環和第二條手環上從某個位置開始逆時 針方向上各裝飾物的亮度。 1≤n≤50000, 1≤m≤100, 1≤ai≤m

Output

輸出一個數，表示兩個手環能產生的最小差異值。 注意在將手環改造之后，裝飾物的亮度 可以大于 m。

Sample Input

5 6
1 2 3 4 5
6 3 3 4 5

Sample Output

1
【樣例解釋】
需要將第一個手環的亮度增加1，第一個手環的亮度變為： 2 3 4 5 6 旋轉一下第二個手環。對于該樣例，是將第
二個手環的亮度6 3 3 4 5向左循環移動 2017-04-15 第 6 頁，共 6 頁 一個位置，使得第二手環的最終的亮度為
：3 3 4 5 6。 此時兩個手環的亮度差異值為1。

題解

環上的東西我們按照套路倍長解決.

然后我們來看那個表達式: $\sum\limits_{i=1}^n(x_i-y_i)^2$...

好像在哪見過? 是哪呢?

卷積與字符串

沒錯就是你! 字符串匹配!

那么好了我們翻轉其中一個串然后拆拆式子看看能得到什么:

$$
\begin{aligned}
c_k&=\sum_{i=0}^k(a_i-b_{k-i})^2 \\
&=\sum_{i=0}^ka_i^2-2a_ib_{k-i}+b_{k-i}^2 \\
&=\sum_{i=0}^ka_i^2+\sum_{i=0}^kb_{k-i}^2-2\sum_{i=0}^ka_ib_{k-i}\\
&=\sum_{i=0}^ka_i^2+\sum_{i=0}^kb_i^2-2\sum_{i=0}^ka_ib_{k-i}
\end{aligned}
$$

而$\sum\limits_{i=0}^ka_ib_{k-i}$ 顯然是個卷積, 剩下兩個和式是前綴和可以預處理.

那么我們只要有了 $a$ 和 $b$ , 我們就可以在 $O(n\log n)$ 時間內算出所有位置的差異值了...嗎?

然而并不是這樣的.

我們在字符串匹配問題中, 高位補 $0$ 相當于補的是通配符, 不會對答案作出貢獻. 但這次 $0$ 可就是字符了, 如果按照上面的式子算的話會把前 $k$ 個字符全都對位計算貢獻. ($(a-0)^2$可是有貢獻的).

我們設倍長并翻轉的串是 $a$, 另一個串是 $b$, 那么實際上的式子應該是:

$$
\begin{aligned}
c_k&=\sum_{i=0}^{n-1}(a_{k-i}-b_i)^2 \\
&=\sum_{i=0}^{n-1}a_{k-i}^2-2a_{k-i}b_i+b_i^2 \\
&=\sum_{i=0}^{n-1}a_{k-i}^2+\sum_{i=0}^{n-1}b_i^2-2\sum_{i=0}^{n-1}a_{k-i}b_i
\end{aligned}
$$

前面兩個式子依然是前綴和即可處理, 后面的卷積式就可以通過高位補 $0$ 來避免多余計算了.

可是這 $a$ 和 $b$ 可能會變...這就比較蠢...直接 $O(mn\log n)$ 跑鐵定是過不去的...

我們再來拆式子.

那么我們首先來考慮給 $a$ 上加東西的情況. 設我們給 $a$ 整體加一個 $d$ , 則:

$$
\begin{aligned}
c_k&=\sum_{i=0}^{n-1}((a_{k-i}+d)-b_i)^2 \\
&=\sum_{i=0}^{n-1}(a_{k-i}+d)^2-2a_{k-i}b_i+b_i^2 \\
&=\sum_{i=0}^{n-1}(a_{k-i}+d)^2+\sum_{i=0}^{n-1}b_i^2-2\sum_{i=0}^{n-1}(a_{k-i}+d)b_i\\
&=\sum_{i=0}^{n-1}(a_{k-i}+d)^2+\sum_{i=0}^{n-1}b_i^2-2\sum_{i=0}^{n-1}a_{k-i}b_i+\sum_{i=0}^{n-1}db_i \\
&=\sum_{i=0}^{n-1}(a_{k-i}+d)^2+\sum_{i=0}^{n-1}b_i^2-2\sum_{i=0}^{n-1}a_{k-i}b_i+d\sum_{i=0}^{n-1}b_i
\end{aligned}
$$

于是原來的卷積式還在, 剩下三個前綴和式都可以 $O(n)$ 隨便重新算, 直接枚舉 $d$ 然后暴力就可以了

給 $b$ 上加東西的情況比較辣手, 因為直接給所有 $b$ 都加值是假的...這樣會把防止產生貢獻的系數 $0$ 變成非 $0$ 值, 然后就會爆炸...

所以我們再搞一搞式子

\begin{aligned}
c_k&=\sum_{i=0}^{n-1}(a_{k-i}-(b_i+d))^2 \\
&=\sum_{i=0}^{n-1}a_{k-i}^2-2a_{k-i}(b_i+d)+(b_i+d)^2 \\
&=\sum_{i=0}^{n-1}a_{k-i}^2+\sum_{i=0}^{n-1}(b_i+d)^2-2\sum_{i=0}^{n-1}a_{k-i}(b_i+d)\\
&=\sum_{i=0}^{n-1}a_{k-i}^2+\sum_{i=0}^{n-1}(b_i+d)^2-2\sum_{i=0}^{n-1}a_{k-i}b_i+da_{k-i}\\
&=\sum_{i=0}^{n-1}a_{k-i}^2+\sum_{i=0}^{n-1}(b_i+d)^2-2\sum_{i=0}^{n-1}a_{k-i}b_i+d\sum_{i=0}^{n-1}a_{k-i}\\
\end{aligned}

好了, 又是三個前綴和一個和 $d$ 無關的卷積.

FFT/NTT直接跑就行了

參考代碼

1 #include <bits/stdc++.h> 2 3 const int G=3; 4 const int DFT=1; 5 const int IDFT=-1; 6 const int MAXN=270000; 7 const int MOD=998244353; 8 9 int n; 10 int m; 11 int bct; 12 int bln=1; 13 int a[MAXN]; 14 int b[MAXN]; 15 int c[MAXN]; 16 int na[MAXN]; 17 int nb[MAXN]; 18 int sa[MAXN]; 19 int sb[MAXN]; 20 int sa2[MAXN]; 21 int sb2[MAXN]; 22 int rev[MAXN]; 23 24 int Pow(int,int,int); 25 void NTT(int*,int,int); 26 27 int main(){ 28 scanf("%d%d",&n,&m); 29 for(int i=0;i<n;i++) 30 scanf("%d",a+i); 31 for(int i=n;i<2*n;i++) 32 a[i]=a[i-n]; 33 std::reverse(a,a+2*n); 34 for(int i=0;i<2*n;i++){ 35 na[i]=a[i]; 36 sa[i]=(i>0?sa[i-1]:0)+a[i]; 37 sa2[i]=(i>0?sa2[i-1]:0)+a[i]*a[i]; 38 } 39 for(int i=0;i<n;i++){ 40 scanf("%d",b+i); 41 nb[i]=b[i]; 42 sb[i]=(i>0?sb[i-1]:0)+b[i]; 43 sb2[i]=(i>0?sb2[i-1]:0)+b[i]*b[i]; 44 } 45 for(int i=n;i<2*n;i++){ 46 sb[i]=sb[i-1]; 47 sb2[i]=sb2[i-1]; 48 } 49 while(bln<3*n){ 50 bln<<=1; 51 ++bct; 52 } 53 //printf("bln=%d\n",bln); 54 for(int i=0;i<bln;i++) 55 rev[i]=(rev[i>>1]>>1)|((i&1)<<(bct-1)); 56 NTT(na,bln,DFT); 57 NTT(nb,bln,DFT); 58 for(int i=0;i<bln;i++) 59 c[i]=1ll*na[i]*nb[i]%MOD; 60 NTT(c,bln,IDFT); 61 int ans=INT_MAX;/* 62 for(int i=0;i<2*n;i++) 63 printf("c[%d]=%d\n",i,c[i]);*/ 64 for(int d=0;d<=m;d++){ // Change A 65 for(int i=0;i<2*n;i++){ 66 sa[i]=(i>0?sa[i-1]:0)+a[i]+d; 67 sa2[i]=(i>0?sa2[i-1]:0)+(a[i]+d)*(a[i]+d); 68 } 69 for(int i=n-1;i<2*n-1;i++){ 70 int sum=sa2[i]+sb2[i]; 71 sum-=2*(c[i]+d*sb[i]); 72 if(i>=n) 73 sum-=sa2[i-n]; 74 //printf("d=%d pos %d: sa2=%d sb2=%d c=%d sum=%d\n",d,i,sa2[i],sb2[i],c[i],sum); 75 ans=std::min(ans,sum); 76 } 77 } 78 //printf("%d\n",ans); 79 for(int i=0;i<2*n;i++){ 80 sa[i]=(i>0?sa[i-1]:0)+a[i]; 81 sa2[i]=(i>0?sa2[i-1]:0)+a[i]*a[i]; 82 } 83 for(int d=0;d<=m;d++){ // Change B 84 for(int i=0;i<n;i++){ 85 sb[i]=(i>0?sb[i-1]:0)+b[i]+d; 86 sb2[i]=(i>0?sb2[i-1]:0)+(b[i]+d)*(b[i]+d); 87 } 88 for(int i=n;i<2*n;i++){ 89 sb[i]=sb[i-1]; 90 sb2[i]=sb2[i-1]; 91 } 92 for(int i=n-1;i<2*n-1;i++){ 93 int sum=sa2[i]+sb2[i]; 94 sum-=2*(c[i]+d*(sa[i]-(i>=n?sa[i-n]:0))); 95 if(i>=n) 96 sum-=sa2[i-n]; 97 ans=std::min(ans,sum); 98 } 99 } 100 printf("%d\n",ans); 101 return 0; 102 } 103 104 void NTT(int* a,int len,int opt){ 105 for(int i=0;i<len;i++) 106 if(rev[i]>i) 107 std::swap(a[rev[i]],a[i]); 108 for(int i=1;i<len;i<<=1){ 109 int step=i<<1; 110 int wn=Pow(G,(MOD-1+opt*(MOD-1)/step)%(MOD-1),MOD); 111 for(int j=0;j<len;j+=step){ 112 int w=1; 113 for(int k=0;k<i;k++,w=1ll*w*wn%MOD){ 114 int x=a[j+k]; 115 int y=1ll*w*a[j+k+i]%MOD; 116 a[j+k]=(x+y)%MOD; 117 a[j+k+i]=(x-y+MOD)%MOD; 118 } 119 } 120 } 121 if(opt==IDFT){ 122 int inv=Pow(len,MOD-2,MOD); 123 for(int i=0;i<len;i++) 124 a[i]=1ll*a[i]*inv%MOD; 125 } 126 } 127 128 inline int Pow(int a,int n,int p){ 129 int ans=1; 130 while(n>0){ 131 if(n&1) 132 ans=1ll*a*ans%p; 133 a=1ll*a*a%p; 134 n>>=1; 135 } 136 return ans; 137 } BZOJ 4827

?

轉載于:https://www.cnblogs.com/rvalue/p/10220159.html

總結

以上是生活随笔為你收集整理的[BZOJ 4827][Hnoi2017]礼物的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。