CodeForces - 979D Kuro and GCD and XOR and SUM(字典树+暴力+模拟)

题目链接：点击查看

题目大意：说实话看到这么复杂而且还是英文的题面我是拒绝的，但题还是得补啊，就去百度找的题解看题意，题意大概是这样的：

给出n个操作，每个操作分为两种类型：

1 x：向集合中插入x2 x k s：我们需要在集合中找到一个v，使其满足下面的条件： gcd(x,v)%k==0x+v<=sx^v最大

模拟每一次操作

题目分析：看完题意之后，肯定不能直接上手就模拟啊，就比如题目让求gcd，还能真的就是去求gcd嘛，我们需要尽可能的简化题意，首先，gcd(x,v)%k==0，也就是说x%k==0&&v%k==0，然后x^v最大看似是经典的字典树求异或问题，但还是需要分类讨论一下的，若k等于1的时候，我们就可以对于经典的01字典树改动一下即可，因为经典的01字典数的查找函数最后输出的是异或之后的结果，而本题要求输出的却是哪个值，所以我们需要映射一下，这个一会再说，那么关于x+v<=s这个情况，我们可以移项，从而转换为v<=s-x，也就是给v规定了一个取值范围而已，并不是什么麻烦的事情，现在处理完了k等于1的情况，那么k不等于1该怎么办呢？一开始我实在想不到好的办法，若是枚举的话我感觉会爆。。因为假如1e5个操作的s都给的是1e5，而k给的都是2，那时间复杂度都到了1e10了，但显然题目没有这么狠，所以网上的正解都是直接暴力即可 ，我也纳闷，题目是不是故意卡k==1的数据了，然后其他的都没怎么卡，因为不加字典树优化的话会T，加了字典树优化的话几十毫秒就过了，我人都呆住了？？

上代码吧，没什么好说的了，反正我是想不到可以暴力：

#include<iostream>#include<cstdlib>#include<string>#include<cstring>#include<cstdio>#include<algorithm>#include<climits>#include<cmath>#include<cctype>#include<stack>#include<queue>#include<list>#include<vector>#include<set>#include<map>#include<sstream>using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int trie[N*20][2];int mmin[N*20];//储存经过每个节点的最小值bool vis[N];int cnt=0;void insert(int x){int pos=0;mmin[pos]=min(mmin[pos],x);for(int i=19;i>=0;i--){int to=(x>>i)&1;if(!trie[pos][to])trie[pos][to]=++cnt;pos=trie[pos][to];mmin[pos]=min(mmin[pos],x);}} int search(int x,int limit){int pos=0;if(mmin[pos]>limit)return -1;for(int i=19;i>=0;i--){int to=(x>>i)&1;if(trie[pos][!to]&&mmin[trie[pos][!to]]<=limit)//判断条件改一下pos=trie[pos][!to];elsepos=trie[pos][to];}return mmin[pos];//注意这里，返回的应该是哪个值，而不是异或后的结果}int main(){// freopen("input.txt","r",stdin);//ios::sync_with_stdio(false);int n;memset(mmin,inf,sizeof(mmin));scanf("%d",&n);while(n--){int op;scanf("%d",&op);if(op==1){int x;scanf("%d",&x);insert(x);vis[x]=true;}else{int x,k,s;scanf("%d%d%d",&x,&k,&s);if(x%k){printf("-1\n");continue;}if(k==1)printf("%d\n",search(x,s-x));else{int ans=-1,mmax=-1;for(int i=k;i<=s-x;i+=k){if(!vis[i])continue;if((i^x)>mmax)//注意这里，位运算的优先级比比较运算符要低，所以要加括号{mmax=i^x;ans=i;}}printf("%d\n",ans);}}}return 0;}