Codeforces 979 D. Kuro and GCD and XOR and SUM(异或和，01字典树）

[Codeforces 979 D. Kuro and GCD and XOR and SUM](http://codeforces.com/problemset/problem/979/D)
题目大意：有两种操作：①给一个数v，加入数组a中②给出三个数x,k,s；从当前数组a中找出一个数u满足 u与x的gcd可以被k整除，u不大于s-x，且与x的异或和最大。
思路：之前没有碰到过异或和最值的问题，所以是懵逼的。学习了01字典树后把这题补出来。
碰到操作①就上树，上树过程中注意不断维护每个节点往后路径中的最小值（具体见代码细节）；
碰到操作②，如果k==1，那么从树上找数的同时注意限制条件最小值不超过s-x；如果k>1,那么直接枚举找最值。
```C++
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=1e5+10;
bool a[maxn];
struct Trie_01
{
static const int N = 32*maxn , M = 2;
int node[N][M],value[N],rt,L;
void init()
{
fill_n(node[N-1],M,0);
fill_n(value,N,INT_MAX);
L = 0;
rt = newnode();
}
int newnode()
{
fill_n(node[L],M,0);
return L++;
}
void add(int x)
{
int p = rt;
value[p]=min(value[p],x);
for (int i=31;i>=0;--i)
{
int idx = (x>>i)&1;
if (!node[p][idx])
{
node[p][idx] = newnode();
}
p = node[p][idx];
value[p]=min(value[p],x);
}
}
int query(int x,int bound)
{
int p = rt;
if (value[p]>bound)
return -1;
for (int i=31;i>=0;--i)
{
int idx = (x>>i)&1;
if (node[p][idx^1]&&value[node[p][idx^1]]>n;
tree.init();
for (i=0;imx)
{
mx=j^x;
ans=j;
}
}
cout

巴特西

Codeforces 979 D. Kuro and GCD and XOR and SUM(异或和，01字典树）

最新文章

热门文章