今天先写了01字典树，学习博客
这个01字典树还是很简单的，看看模板就会了
贴一下我的模板
const int maxn = 1e5 + 10; int n, m, tot; int trie[32 * maxn][2], num[maxn]; ll val[maxn * 32]; void init() { tot = 1; trie[0][0] = trie[0][1] = 0; } void insert(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if(trie[u][v]==0) { trie[tot][0] = trie[tot][1] = 0;//初始化 val[tot] = 0, num[tot] = 0; trie[u][v] = tot++; } u = trie[u][v]; num[u]++; } val[u] = x; } void update(ll x,int f) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; u = trie[u][v]; num[u] += f; } } ll query(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if (trie[u][v ^ 1] && num[trie[u][v ^ 1]]) u = trie[u][v ^ 1]; else u = trie[u][v]; } return val[u] ^ x; }
然后就是今天写的两个简单的裸题
G - Xor Sum
#include <cstring> #include <queue> #include <cstdlib> #include <cstdio> #include <iostream> #include <string> #include <bitset> #include <algorithm> #include <map> #include <vector> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e5 + 10; int n, m, tot; int trie[32 * maxn][2]; ll val[maxn * 32]; void init() { tot = 1; trie[0][0] = trie[0][1] = 0; } void insert(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if(trie[u][v]==0) { trie[tot][0] = trie[tot][1] = 0;//初始化 val[tot] = 0; trie[u][v] = tot++; } u = trie[u][v]; } val[u] = x; } ll query(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if (trie[u][v ^ 1]) u = trie[u][v ^ 1]; else u = trie[u][v]; } return val[u]; } int main() { int t; scanf("%d", &t); for(int cas=1;cas<=t;cas++) { int n, m; init(); scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) { ll x; scanf("%lld", &x); insert(x); } printf("Case #%d: ", cas); while(m--) { ll x; scanf("%lld", &x); printf("%lld ", query(x)); } } return 0; }
H - Chip Factory
这个有修改的操作，学习一下
有点卡时间，注意for的优化
#include <cstring> #include <queue> #include <cstdlib> #include <cstdio> #include <iostream> #include <string> #include <bitset> #include <algorithm> #include <map> #include <vector> #define inf 0x3f3f3f3f #define inf64 0x3f3f3f3f3f3f3f3f using namespace std; typedef long long ll; const int maxn = 1e5 + 10; int n, m, tot; int trie[32 * maxn][2], num[maxn]; ll val[maxn * 32]; void init() { tot = 1; trie[0][0] = trie[0][1] = 0; } void insert(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if(trie[u][v]==0) { trie[tot][0] = trie[tot][1] = 0;//初始化 val[tot] = 0, num[tot] = 0; trie[u][v] = tot++; } u = trie[u][v]; num[u]++; } val[u] = x; } void update(ll x,int f) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; u = trie[u][v]; num[u] += f; } } ll query(ll x) { int u = 0; for(int i=32;i>=0;i--) { int v = (x >> i) & 1; if (trie[u][v ^ 1] && num[trie[u][v ^ 1]]) u = trie[u][v ^ 1]; else u = trie[u][v]; } return val[u] ^ x; } ll a[maxn]; int main() { int t; scanf("%d", &t); while(t--) { int n; init(); scanf("%d", &n); for(int i=1;i<=n;i++) { scanf("%lld", &a[i]); insert(a[i]); } ll ans = 0; for (int i = 1; i <= n; i++) { for (int j = i + 1; j <= n; j++) { update(a[i], -1), update(a[j], -1); ans = max(ans, query(a[i] + a[j])); update(a[i], 1), update(a[j], 1); } } printf("%lld ", ans); } return 0; }