The XOR Largest Pair
题目描述
给你n个数，保证数据都在 int 范围内并且 n 小于等于 1e5，询问挑出两个数异或之后答案最大。
Solution
解决方案：01trie，字典树。
新学的算法，字典树之前只在博客多多少少了解一些，通过跳点避免重复的文段匹配。
但是当字典树的分支变成两个之后，分别赋值 0 1 ，就可以用来求一堆数中最大异或值 or 最小异或值。
很显然，我们可以写出每个数的二进制表示，在题目保证的 int 范围中每个数从最高位开始造 01 字典树
按照上面方法造好这颗字典树之后，就可以考虑如何跳点了，因为题目需要求的是异或最大，我们枚举每一个数，在当前字典树中寻找，这一位和它不一样的，看看是否存在，如果存在说明这一位是存在贡献的，累计答案上去，但是如果这一位不存在与之对应的不同数，那只有不算这一位的贡献了。但是跳点是不能停下来的。
接着就是枚举 n 个数，看看找到最大的那一对数是哪个？
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int trie[N * 32][2], sz, a[N];
void update(int x) {
int u = 0;
for (int i = 31; ~i; --i) {
int v = (x >> i) & 1;
if (!trie[u][v]) trie[u][v] = ++sz; // 建点
u = trie[u][v];
}
}
int query(int x) {
int res = 0, u = 0;
for (int i = 31; ~i; --i) {
int v = (x >> i) & 1;
if (trie[u][v ^ 1]) {
res |= (1 << i);
u = trie[u][v ^ 1];
}
else u = trie[u][v];
}
return res;
}
void solve() {
int n = read();
for (int i = 1; i <= n; ++i) {
a[i] = read();
update(a[i]);
}
int ans = 0;
for (int i = 1; i <= n; ++i)
ans = max(ans, query(a[i]));
print(ans);
}
int main() {
int T = 1;
//T = read();
while (T--) {
solve();
}
return 0;
}
奶牛异或
题目描述
给出 n 个数，n 小于等于 1e5，叫你判断选取一段连续的区间异或之后的值最大是多少？并且给出这个区间的起点和终点。
Solution
这个题目需要一个比较基础的前导知识，看到区间异或，应该需要了解异或前缀和的概念。如何快速求道这个区间中全部数的异或值。
知道异或前缀和之后，这个题目就变成了随机选取两个端点，叫你判断如何选取端点保证区间的异或值最大。
这个样子就变成了上一题一模一样的算法了，只需要加个记录之前点的下标是什么就行了。
我的写法需要特判只有 1 个数的情况，不然就会死。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 7;
int trie[N * 32][2], sz, a[N], num[N * 32];
void update(int x, int pos) {
int u = 0;
for (int i = 31; ~i; --i) {
int v = (x >> i) & 1;
if (!trie[u][v]) trie[u][v] = ++sz;
u = trie[u][v];
}
num[u] = pos;
}
pai query(int x) {
int res = 0, u = 0;
for (int i = 31; ~i; --i) {
int v = (x >> i) & 1;
if (trie[u][v ^ 1]) {
res |= (1 << i);
u = trie[u][v ^ 1];
}
else u = trie[u][v];
}
return { res,num[u] };
}
void solve() {
int n = read();
for (int i = 1; i <= n; ++i) {
int x = read();
a[i] = x ^ a[i - 1];
}
update(a[1], 1);
int ans = a[1], l = 1, r = 1;
for (int i = 2; i <= n; ++i) {
update(a[i], i);
pai tmp = query(a[i]);
if (tmp.first > ans)
ans = tmp.first, l = tmp.second + 1, r = i;
}
printf("%d %d %d\n", ans, l, r);
}
int main() {
int T = 1;
//T = read();
while (T--) {
solve();
}
return 0;
} Vitya and Strange Lesson
题目描述
给你长度是 n 的一个序列，首先给你一个 mex 运算函数，即找到这个序列中最小的未出现非负数。
但是后面有 m 次异或操作，每次异或会对序列中全部的数进行异或处理，并且这些数会覆盖掉之前的数。即更新会被保留。
现在需要你给出每次异或操作 当前 mex 当前序列的值是什么？
Solution
异或找最小，思路往 01trie 靠，首先我们知道异或是可以添加括号的，也就是
所以可以看出虽然题目说变化会保留，但是我们可以通过异或查询去保证不动原序列的前提下得到答案。
那么问题就来到了如何求解这个 mex 的地方了。
总而言之就是，在当前的数构成的 01trie 中异或 x ，需要找到一个数，不在当前 01trie 中，并且这个数还要尽可能小。
而且我们还需要知道的就是，出现过的 序列a 中全部的数异或 x 得到一个集合 A，没出现过的数 异或 x 得到一个集合 B ， A和B一定是不存在交集的。因为不存在哪两个不同的数异或同一个数之后是相同的值。
那么这个问题就容易解决了，把全部没有出现过的数放入 01trie 中，每次查询数中最小的哪个异或数即可，这个沿用上方第一题的板子即可，注意空间开大点。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 6e5 + 7;
int trie[N * 32][2], sz, a[N];
int vis[N];
void update(int x) {
int u = 0;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (!trie[u][v]) trie[u][v] = ++sz; // 建点
u = trie[u][v];
}
}
int query(int x) {
int res = 0, u = 0;
for (int i = 30; ~i; --i) {
int v = (x >> i) & 1;
if (!trie[u][v]) {
res |= (1 << i);
u = trie[u][v ^ 1];
}
else u = trie[u][v];
}
return res;
}
void solve() {
int n = read(), m = read(), maxi = -1;
for (int i = 1; i <= n; ++i) {
int x = read();
maxi = max(maxi, x);
vis[x] = 1;
}
for (int i = 0; i < N; ++i)
if (!vis[i])
update(i);
int pre = 0;
while (m--) {
int x = read();
pre ^= x;
print(query(pre));
}
}
int main() {
int T = 1;
//T = read();
while (T--) {
solve();
}
return 0;
}
Perfect Security
题目描述
给你长度为 n 的两个序列 a,b ，b可以交换顺序,需要你求到 最小字典序的 C。
最大长度 3e5
Solution
题目要求输出最小字典序的序列，那肯定是把异或之后最小的放在最前面。依次处理。
所以我们根据 trie 的异或性质，把 b 数组插入到 trie 树中，并且需要统计每个节点出现的数量，每次取数把数量减一，当数量不存在的时候就不能再取这一个数了。
其余的就是 01trie 的板子了，与第一题大同小异。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e7 + 7;
const int M = 3e5 + 7;
int trie[N][2], cnt[N], sz;
int a[M];
void update(int x) {
int u = 0;
for (int i = 30; ~i; --i) {
int j = x >> i & 1;
if (!trie[u][j]) trie[u][j] = ++sz;
u = trie[u][j];
++cnt[u];
}
}
int query(int x) {
int u = 0, res = 0;
for (int i = 30; ~i; --i) {
int j = x >> i & 1;
if (trie[u][j] and cnt[trie[u][j]] >= 1)
u = trie[u][j];
else
u = trie[u][j ^ 1], res |= (1 << i);
--cnt[u];
}
return res;
}
void solve() {
int n = read();
for (int i = 1; i <= n; ++i) a[i] = read();
for (int i = 1; i <= n; ++i)
update(read());
for (int i = 1; i <= n; ++i)
printf("%d ", query(a[i]));
}
int main() {
int T = 1;
//T = read();
while (T--) {
solve();
}
return 0;
}
Xor-MST
题目意思
给你n个点，并且给出这n个点的点权值，边权值是由点权值异或而来。需要你找到这n个点构成的图中最小生成树权值和是？
数据范围
Solution
异或？ 01trie树，最小生成树？ Kruskal，但是很显然我们这个数据范围中不能找出全部的边权值在进行Kruskal求解。那么怎么办呢？
居然我们Kruskal先走不通，那么画个 01 trie树看一下图片来自周道_Althen
看到上方两个图片的区别了吗，在5个两两不同的点构成的01trie树中找到了4个lca相同的父节点。这样多写几组样例之后，你就会发现这个 n - 1个 lca的点并不是偶然。
居然我们要构成最小生成树说明 n - 1条边是少不了的，那么这样每两个叶子节点就应该需要有一条通路连接。只要连接就会找到一个他们的 lca 节点上去。
所以就可以开始暴力往下DFS了。
首先先把全部的点插入到 01trie树中间去，如果一个节点是存在左右两个儿子的，说明这个点的深度构成的1在异或是一定存在贡献的。它的子树会出现的贡献需要额外寻找了。
如果一个节点有左孩子也有右孩子那么两颗子树都要递归处理，同理那颗子树为空时就不对这颗子树进行递归处理。
好的那么问题来到了，如何处理同时存在左右孩子的父节点（下方 find 函数）。上面我们说了，他是一定存在 的贡献的，因为这高位的深度是一定异或等于0了，那么后面新的我们只要尽量让左右子树走向尽可能相同的位置就行了，也就是同0或者同1，如果实在没办法了也只能加上新的不同位置深度了。
那么答案也就处理完了。
想想，想想，我们上面是不是自己规定了一个前提！在5个两两不同的点构成的01trie树中找到了4个lca相同的父节点，但是题目并没有说输入的n个数据全部不相同哦。我们需要处理这种情况吗？并不需要。如果插入两个相同的树去 01trie中，显然第二次插入会被pass，也就是啥也不干。这样在进行我们上方的 DFS 处理中相当于忽略了这个数，那么我们需不需要处理相同的数呢？也不需要，想想异或之后等于0的点，就是我们需要最优先选择的连接点，这个和我们Kruskal的思想很类似，并且相同位置下并不会存在对另外位置的选数存在影响。所以直接pass对我们答案没有任何的影响。
#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define all(__vv__) (__vv__).begin(), (__vv__).end()
#define endl "\n"
#define pai pair<int, int>
#define ms(__x__,__val__) memset(__x__, __val__, sizeof(__x__))
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(ll x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1; while (b) { if (b & 1) ans *= a; b >>= 1; a *= a; } return ans; } ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }
const int dir[][2] = { {0,1},{1,0},{0,-1},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1} };
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 2e7 + 7;
int trie[N][2], sz;
void update(int x) {
int u = 0;
for (int i = 30; ~i; --i) {
int j = x >> i & 1;
if (!trie[u][j]) trie[u][j] = ++sz;
u = trie[u][j];
}
}
ll ans;
int find(int r1, int r2, int b) {
if (b < 0) return 0;
int a1 = -1, a2 = -1;
if (trie[r1][0] and trie[r2][0]) a1 = find(trie[r1][0], trie[r2][0], b - 1);
if (trie[r1][1] and trie[r2][1]) a2 = find(trie[r1][1], trie[r2][1], b - 1);
if (~a1 and ~a2) return min(a1, a2);
if (~a1) return a1;
if (~a2) return a2;
if (trie[r1][0] and trie[r2][1]) a1 = find(trie[r1][0], trie[r2][1], b - 1) + (1 << b);
if (trie[r1][1] and trie[r2][0]) a2 = find(trie[r1][1], trie[r2][0], b - 1) + (1 << b);
if (~a1 and ~a2) return min(a1, a2);
if (~a1) return a1;
if (~a2) return a2;
}
void dfs(int a, int b) {
if (b < 0) return;
if (trie[a][0] and trie[a][1]) ans += find(trie[a][0], trie[a][1], b - 1) + (1 << b);
if (trie[a][0]) dfs(trie[a][0], b - 1);
if (trie[a][1]) dfs(trie[a][1], b - 1);
}
void solve() {
int n = read();
for (int i = 1; i <= n; ++i)
update(read());
dfs(0, 30);
print(ans);
}
int main() {
int T = 1;
//T = read();
while (T--) {
solve();
}
return 0;
} 
京公网安备 11010502036488号