[关闭]
@zzzc18 2017-12-27T14:47:08.000000Z 字数 3700 阅读 1103

BZOJ4827: [Hnoi2017]礼物

bzoj FFT


由于之前FFT学习笔记实在太长了,就不再往里面加了

Description

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手 环,一个留给自己,一个送给她。每个手环上各有 个装饰物,并且每个装饰物都有一定的亮度。但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的自然数 (即非负整数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,
但是由于上面 装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 ,其中 为每个手环的装饰物个数,第 个手环的 号位置装饰物亮度为 ,第 个手环的 号位置装饰物
亮度为 ,两个手环之间的差异值为(参见输入输出样例和样例解释): 麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小, 这个最小值是多少呢?

Input

输入数据的第一行有两个数 , ,代表每条手环的装饰物的数量为 ,每个装饰物的初始亮度小于等于
接下来两行,每行各有 个数,分别代表第一条手环和第二条手环上从某个位置开始逆时 针方向上各装饰物的亮度。

Output

输出一个数,表示两个手环能产生的最小差异值。
注意在将手环改造之后,装饰物的亮度 可以大于

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。

Solution:

我们根据题意,另第一个手环的增加量为 ,第二个手环旋转过 个位置,最终在 位置的差异值为函数

不难把题意写成一下式子:

然后进行一些化简

这时,我们可以发现,上式中的 是一个定值,而对于各个 可以进行计算,而考虑到 只有 ,可以枚举每一个 计算上式的值,并取最小值即为最终答案。

对于的计算,记

反转得到 ,则

那么 ,这是一个卷积的形式,可以使用FFT进行优化,具体操作的时候只要在 数组,后面复制一遍其本身,使长度达到 即可。

感觉m可以很大,不知道为什么只有100,可以直接暴力枚举

总时间复杂度为

  1. /**************************************************************
  2. Problem: 4827
  3. User: zzzc18
  4. Language: C++
  5. Result: Accepted
  6. Time:980 ms
  7. Memory:10980 kb
  8. ****************************************************************/
  9. #include<cmath>
  10. #include<cstdio>
  11. #include<cstring>
  12. #include<algorithm>
  13. using namespace std;
  14. typedef long long LL;
  15. const double PI = acos(-1.0);
  16. const int MAXN = 200000+9;
  17. int n,m;
  18. int loc[MAXN];
  19. int size,bit_length;
  20. struct C{
  21. double x,y;
  22. C(double _x=0,double _y=0):x(_x),y(_y){}
  23. };
  24. C operator + (const C &A,const C &B){
  25. return C(A.x+B.x,A.y+B.y);
  26. }
  27. C operator - (const C &A,const C &B){
  28. return C(A.x-B.x,A.y-B.y);
  29. }
  30. C operator * (const C &A,const C &B){
  31. return C(A.x*B.x-A.y*B.y,A.x*B.y+A.y*B.x);
  32. }
  33. C A1[MAXN],B1[MAXN];
  34. LL calc[MAXN];
  35. LL sumA,sumB;
  36. LL sumA2,sumB2;
  37. int a[MAXN],b[MAXN];
  38. void init(int len){
  39. for(size=1,bit_length=-1;size<len;size<<=1,bit_length++);
  40. int now=0;
  41. for(int i=0;i<size;i++){
  42. loc[i]=now;
  43. for(int j=1<<bit_length;(now^=j)<j;j>>=1);
  44. }
  45. }
  46. void DFT(int *A,C *re){
  47. for(int i=0;i<size;i++)
  48. re[i]=C(A[loc[i]],0);
  49. for(int k=2;k<=size;k<<=1){
  50. int len=k>>1;
  51. C Wn(cos(2.0*PI/k),sin(2.0*PI/k));
  52. for(int i=0;i<size;i+=k){
  53. C W(1,0);
  54. for(int j=0;j<len;j++){
  55. C u=re[i+j],v=re[i+j+len]*W;
  56. re[i+j]=u+v;
  57. re[i+j+len]=u-v;
  58. W=W*Wn;
  59. }
  60. }
  61. }
  62. }
  63. void IDFT(C *A,C *re){
  64. for(int i=0;i<size;i++)
  65. re[i]=A[loc[i]];
  66. for(int k=2;k<=size;k<<=1){
  67. int len=k>>1;
  68. C Wn(cos(2.0*PI/k),sin(-2.0*PI/k));
  69. for(int i=0;i<size;i+=k){
  70. C W(1,0);
  71. for(int j=0;j<len;j++){
  72. C u=re[i+j],v=re[i+j+len]*W;
  73. re[i+j]=u+v;
  74. re[i+j+len]=u-v;
  75. W=W*Wn;
  76. }
  77. }
  78. }
  79. for(int i=0;i<size;i++)
  80. re[i].x/=size;
  81. }
  82. void solve(){
  83. init(n<<1);
  84. DFT(a,A1);DFT(b,B1);
  85. for(int i=0;i<size;i++)
  86. A1[i]=A1[i]*B1[i];
  87. IDFT(A1,B1);
  88. for(int i=0;i<size;i++)
  89. calc[i]=-2LL*LL(B1[i].x+0.5);
  90. /*//DEBIG
  91. for(int i=0;i<size;i++)
  92. printf("%lld\n",calc[i]/(-2LL));*/
  93. LL ans=1000000000000000;
  94. for(int t=0;t<=n;t++){
  95. LL val=calc[n+t+1]+sumA2+sumB2;
  96. LL tmp=1000000000000000;
  97. for(int i=0;i<=m;i++)
  98. tmp=min(tmp,1LL*n*i*i+2LL*i*(sumA-sumB)+val);
  99. ans=min(ans,tmp);
  100. }
  101. printf("%lld\n",ans);
  102. }
  103. int main(){
  104. scanf("%d%d",&n,&m);
  105. for(int i=1;i<=n;i++){
  106. scanf("%d",&a[i]);
  107. sumA+=a[i];
  108. sumA2+=a[i]*a[i];
  109. }
  110. for(int i=1;i<=n;i++){
  111. scanf("%d",&i[b]);
  112. b[i+n]=b[i];
  113. sumB+=b[i];
  114. sumB2+=b[i]*b[i];
  115. }
  116. reverse(a+1,a+n+1);
  117. solve();
  118. return 0;
  119. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注