首页 > 代码库 > Gym100783C Golf Bot（FFT）
Gym100783C Golf Bot（FFT）
https://vjudge.net/problem/Gym-100783C
题意：
给出n个数，然后有m次查询，每次输入一个数x，问x能否由n个数中2个及2个以下的数相加组成。
思路：
题意很简单，但是如果直接去算要超时。
可以利用傅里叶，计算出两个卷积中的数相加的所有可能性。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<string> 6 #include<vector> 7 #include<queue> 8 #include<cmath> 9 using namespace std; 10 11 #define LL long long 12 const double PI = acos(-1.0); 13 14 // 复数结构体 15 struct Complex 16 { 17 double x, y; // 实部和虚部 x + yi 18 Complex(double _x = 0.0, double _y = 0.0) 19 { 20 x = _x; 21 y = _y; 22 } 23 Complex operator - (const Complex &b) const 24 { 25 return Complex(x - b.x, y - b.y); 26 } 27 Complex operator + (const Complex &b) const 28 { 29 return Complex(x + b.x, y + b.y); 30 } 31 Complex operator * (const Complex &b) const 32 { 33 return Complex(x * b.x - y * b.y, x * b.y + y * b.x); 34 } 35 }; 36 37 // 进行FFT和IFFT前的反转变换 38 // 位置i和（i二进制反转后的位置）互换 39 // len必须去2的幂 40 void change(Complex y[], int len) 41 { 42 int i, j, k; 43 for (i = 1, j = len / 2; i < len - 1; i++) 44 { 45 if (i < j) 46 { 47 swap(y[i], y[j]); 48 } 49 // 交换护卫小标反转的元素，i < j保证交换一次 50 // i做正常的+1，j左反转类型的+1，始终保持i和j是反转的 51 k = len / 2; 52 while (j >= k) 53 { 54 j -= k; 55 k /= 2; 56 } 57 if (j < k) 58 { 59 j += k; 60 } 61 } 62 return ; 63 } 64 65 // FFT 66 // len必须为2 ^ k形式 67 // on == 1时是DFT，on == -1时是IDFT 68 void fft(Complex y[], int len, int on) 69 { 70 change(y, len); 71 for (int h = 2; h <= len; h <<= 1) 72 { 73 Complex wn(cos(-on * 2 * PI / h), sin(-on * 2 * PI / h)); 74 for (int j = 0; j < len; j += h) 75 { 76 Complex w(1, 0); 77 for (int k = j; k < j + h / 2; k++) 78 { 79 Complex u = y[k]; 80 Complex t = w * y[k + h / 2]; 81 y[k] = u + t; 82 y[k + h / 2] = u - t; 83 w = w * wn; 84 } 85 } 86 } 87 if (on == -1) 88 { 89 for (int i = 0; i < len; i++) 90 { 91 y[i].x /= len; 92 } 93 } 94 } 95 96 const int maxn=200000+100; 97 98 Complex x1[5*maxn]; 99 int a[5*maxn];100 LL num[5*maxn];101 102 int main()103 {104 //freopen("D:\\input.txt","r",stdin);105 int n,m;106 while(~scanf("%d",&n))107 {108 memset(num,0,sizeof(num));109 for(int i=0;i<n;i++)110 {111 scanf("%d",&a[i]);112 num[a[i]]++;113 }114 a[n]=0; n++; num[0]++;115 sort(a,a+n);116 int len1=a[n-1]+1;117 int len=1;118 while(len<2*len1) len<<=1;119 for(int i=0;i<len1;i++)120 x1[i]=Complex(num[i],0);121 for(int i=len1;i<len;i++)122 x1[i]=Complex(0,0);123 fft(x1,len,1);124 for(int i=0;i<len;i++)125 x1[i]=x1[i]*x1[i];126 fft(x1,len,-1);127 for(int i=0;i<len;i++)128 num[i]=(long long)(x1[i].x+0.5);129 len=2*a[n-1];130 //for(int i=0;i<n;i++)//减去2次选的同一个数131 // num[a[i]+a[i]]--;132 //for(int i=1;i<=len;i++) num[i]/=2;//选1 2和选2 1是一样的所以除2133 134 //for(int i=0;i<=10;i++)135 //printf("%d: %d\n",i,num[i]);136 int ans=0;137 scanf("%d",&m);138 while(m--)139 {140 int xx;141 scanf("%d",&xx);142 if(num[xx]) ans++;143 }144 printf("%d\n",ans);145 }146 }
Gym100783C Golf Bot（FFT）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。