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

题目链接：点击查看

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

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

1 x：向集合中插入x

2 x k s：我们需要在集合中找到一个v，使其满足下面的条件：

gcd(x,v)%k==0

x+v<=s

x^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; }

 

总结

以上是生活随笔为你收集整理的CodeForces - 979D Kuro and GCD and XOR and SUM(字典树+暴力+模拟)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。