题意：
给出两种操作：
1.添加一个数字x到数组。
2.给出s，x，k，从数组中找出一个数v满足gcd(x,k) % v == 0 && x + v <= s && (x xor v 最大)，如果没有，输出-1.
思路：
有两种做法。
第一种，首先用若干个set存因子中有k的数字。
然后每次在set[k]中二分找到大于s-x的第一个数，然后从大到小开始找，假设sum为当前x xor v的最大值，那么当当前的*it +x < sum，那么就直接break，原理是因为a ^ b <= a + b。
这个没有优化之前是会tle，但是加了优化之后比字典树跑得快了许多。。。
第二种，对于每一个数，都把它添加到它的因子的01字典树当中去，然后根据x xor v最大这个经典问题，找 xor 最大，字典树是个好东西。
代码1；
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <set> 5 #include <math.h> 6 using namespace std; 7 const int N = 1e5 + 11; 8 set<int> mmp[N]; 9 int main() 10 { 11 int n; 12 scanf("%d",&n); 13 while (n--) 14 { 15 int t; 16 scanf("%d",&t); 17 if (t == 1) 18 { 19 int u; 20 scanf("%d",&u); 21 int m = sqrt(1.0 * u); 22 for (int i = 1;i <= m;i++) 23 { 24 if (u % i == 0) 25 { 26 mmp[i].insert(u); 27 mmp[u/i].insert(u); 28 } 29 } 30 } 31 else 32 { 33 int x,k,s; 34 scanf("%d%d%d",&x,&k,&s); 35 int sum = -1; 36 int ans = -1; 37 if (x % k) 38 { 39 printf("%dn",ans); 40 continue; 41 } 42 auto it = mmp[k].upper_bound(s-x); 43 if (mmp[k].empty() || it == mmp[k].begin()) 44 { 45 printf("%dn",ans); 46 continue; 47 } 48 --it; 49 for (;it != mmp[k].begin();--it) 50 { 51 if (sum > x + *it) break; 52 if (sum < (x ^ *it)) 53 { 54 ans = *it; 55 sum = x ^ *it; 56 } 57 } 58 if (sum < (x ^ *it)) 59 { 60 ans = *it; 61 sum = x ^ *it; 62 } 63 printf("%dn",ans); 64 } 65 } 66 return 0; 67 }
代码2：
1 #include <stdio.h> 2 #include <string.h> 3 #include <algorithm> 4 #include <stdlib.h> 5 #include <set> 6 using namespace std; 7 const int N = 1e5 + 10; 8 set<int> g[N]; 9 struct node 10 { 11 int mi; 12 struct node* bit[2]; 13 node() 14 { 15 mi = N; 16 bit[0] = bit[1] = nullptr; 17 } 18 }; 19 node *a[N]; 20 void update(int x,int u) 21 { 22 node* cu = a[x]; 23 cu -> mi = min(cu -> mi,u); 24 for (int i = 18;i >= 0;i--) 25 { 26 int b = u >> i & 1; 27 if (cu -> bit[b] != nullptr) 28 { 29 cu = cu -> bit[b]; 30 cu -> mi = min(cu -> mi,u); 31 } 32 else 33 { 34 cu -> bit[b] = new node(); 35 cu = cu -> bit[b]; 36 cu -> mi = min(cu -> mi,u); 37 } 38 } 39 } 40 int que(int x,int k,int s) 41 { 42 node *cu = a[k]; 43 if (x % k || cu -> mi > s - x) return -1; 44 int ret = cu -> mi; 45 for (int i = 18;i >= 0;i--) 46 { 47 int b = x >> i & 1; 48 if (cu -> bit[b^1] != nullptr && cu -> bit[b^1] -> mi + x <= s) 49 { 50 cu = cu -> bit[b^1]; 51 ret = cu -> mi; 52 } 53 else 54 { 55 cu = cu -> bit[b]; 56 ret = cu -> mi; 57 } 58 } 59 return ret; 60 } 61 int main() 62 { 63 int q; 64 for (int i = 1;i < N;i++) 65 { 66 for (int j = i;j < N;j += i) 67 { 68 g[j].insert(i); 69 } 70 } 71 for (int i = 1;i < N;i++) a[i] = new node(); 72 scanf("%d",&q); 73 while (q--) 74 { 75 int t; 76 scanf("%d",&t); 77 if (t==1) 78 { 79 int u; 80 scanf("%d",&u); 81 for (auto x : g[u]) 82 { 83 update(x,u); 84 } 85 } 86 else 87 { 88 int x,s,k; 89 scanf("%d%d%d",&x,&k,&s); 90 int ans = que(x,k,s); 91 printf("%dn",ans); 92 } 93 } 94 return 0; 95 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
