CF1625D.Binary Spiders(CF1625D. Binary Spiders)

\(\text{Problem}\)

大概就是给出 \(n\) 个数和 \(m\),要从中选最多的数使得两两异或值大于等于 \(m\)
输出方案

\(\text{Solution}\)

一开始的想法很复杂、、、
其实用到一个结论就做好了
对于一个升序数列,它们两两间的异或最小值就是相邻数的异或最小值
于是可以先排序,再 \(DP\)
设 \(f_i\) 表示到第 \(i\) 位强制选 \(i\) 能选出最多的数的数量
那么 \(f_i = f_{j} + 1(1\le j < i,a_j \oplus a_i \ge m)\)
于是优化这个 \(O(n^2)\) 的 \(DP\) 即可
这就是个很简单的事
考虑 \(j\) 的选取
若 \(a_i \oplus a_j > m\),那么异或值从高位到低位一部分等于 \(m\),然后在某一位大于 \(m\)
那么我们从高到低枚举位数,考虑在这一位之前等于 \(m\),统计这一位大于 \(m\) 的贡献
讨论 \(m\) 和 \(a_i\) 这一位的 \(0/1\) 值,发现可行数值区间是连续的,权值线段树即可
最后再处理 \(a_i \oplus a_j = m\) 的贡献

\(\text{Code}\)

#include <cstdio> 
#include <iostream>
#include <algorithm>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;

const int N = 3e5 + 5;
int n, m, f[N], g[N], Len, size, rt;
struct node{int v, id;}a[N];
IN bool cmp(node a, node b){return a.v < b.v;}

int seg[N * 31], ls[N * 31], rs[N * 31];
void Modify(int &p, int l, int r, int x, int v)
{
	if (!p) p = ++size;
	if (l == r) return seg[p] = v, void();
	int mid = l + r >> 1;
	if (x <= mid) Modify(ls[p], l, mid, x, v);
	else Modify(rs[p], mid + 1, r, x, v);
	if (f[seg[ls[p]]] > f[seg[rs[p]]]) seg[p] = seg[ls[p]];
	else seg[p] = seg[rs[p]];
}
int Query(int p, int l, int r, int x, int y)
{
	if (x > r || y < l) return 0;
	if (x <= l && r <= y) return seg[p];
	int mid = l + r >> 1, L = 0, R = 0;
	if (ls[p] && x <= mid) L = Query(ls[p], l, mid, x, y);
	if (rs[p] && y > mid)
	{
		R = Query(rs[p], mid + 1, r, x, y);
		if (!L) L = R;
		else{
			if (f[L] > f[R]) return L;
			return R;
		}
	}
	return L;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
	sort(a + 1, a + n + 1, cmp), Len = a[n].v;
	int ans = 1, pos = 0, pre, cur;
	for(RE int i = 1; i <= n; i++)
	{
		f[i] = 1, pre = 0;
		for(RE int j = 30; j >= 0; j--)
		{
			if ((m >> j) & 1){if (!((a[i].v >> j) & 1)) pre |= (1 << j);}
			else{
				if ((a[i].v >> j) & 1)
				{
					cur = Query(rt, 0, Len, pre, pre + (1 << j) - 1), pre |= (1 << j);
					if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
				}
				else{
					cur = Query(rt, 0, Len, pre + (1 << j), (LL)pre + (1LL << j + 1) - 1);
					if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
				}
			}
			if (!j)
			{
				cur = Query(rt, 0, Len, pre, pre);
				if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
			}
		}
		if (ans < f[i]) ans = f[i], pos = i;
		if (i < n) Modify(rt, 0, Len, a[i].v, i);
	}
	printf("%d\n", (ans == 1) ? -1 : ans);
	if (ans > 1) while (pos) printf("%d ", a[pos].id), pos = g[pos];
}
————————

\(\text{Problem}\)

Give the number of \ (n \) and \ (m \), and select the maximum number so that the pairwise XOR value is greater than or equal to \ (m \)
Output scheme

\(\text{Solution}\)

At first, the idea was very complicated
In fact, it’s good to use a conclusion
For an ascending sequence, the XOR minimum between them is the XOR minimum of adjacent numbers
So you can sort first and then \ (DP \)
Set \ (f_i \) to indicate the maximum number that can be selected by forcing \ (I \) to the \ (I \) bit
Then \ (f_i = f_ {J} + 1 (1 \ Le J & lt; I, a_j \ oplus a_i \ Ge m) \)
Therefore, the \ (DP \) of this \ (O (n ^ 2) \) can be optimized
This is a very simple thing
Consider the selection of \ (J \)
If \ (a_i \ oplus a_j & gt; m \), the XOR value is equal to \ (m \) from high to low, and then greater than \ (m \) in some bit
Then we enumerate the number of bits from high to low, consider that it is equal to \ (m \) before this bit, and count the contribution of this bit greater than \ (m \)
The \ (0 / 1 \) values of \ (m \) and \ (a_i \) are discussed. It is found that the feasible value interval is continuous, and the weight segment tree can be used
Finally, deal with the contribution of \ (a_i \ oplus a_j = m \)

\(\text{Code}\)

#include <cstdio> 
#include <iostream>
#include <algorithm>
#define RE register
#define IN inline
using namespace std;
typedef long long LL;

const int N = 3e5 + 5;
int n, m, f[N], g[N], Len, size, rt;
struct node{int v, id;}a[N];
IN bool cmp(node a, node b){return a.v < b.v;}

int seg[N * 31], ls[N * 31], rs[N * 31];
void Modify(int &p, int l, int r, int x, int v)
{
	if (!p) p = ++size;
	if (l == r) return seg[p] = v, void();
	int mid = l + r >> 1;
	if (x <= mid) Modify(ls[p], l, mid, x, v);
	else Modify(rs[p], mid + 1, r, x, v);
	if (f[seg[ls[p]]] > f[seg[rs[p]]]) seg[p] = seg[ls[p]];
	else seg[p] = seg[rs[p]];
}
int Query(int p, int l, int r, int x, int y)
{
	if (x > r || y < l) return 0;
	if (x <= l && r <= y) return seg[p];
	int mid = l + r >> 1, L = 0, R = 0;
	if (ls[p] && x <= mid) L = Query(ls[p], l, mid, x, y);
	if (rs[p] && y > mid)
	{
		R = Query(rs[p], mid + 1, r, x, y);
		if (!L) L = R;
		else{
			if (f[L] > f[R]) return L;
			return R;
		}
	}
	return L;
}

int main()
{
	scanf("%d%d", &n, &m);
	for(RE int i = 1; i <= n; i++) scanf("%d", &a[i].v), a[i].id = i;
	sort(a + 1, a + n + 1, cmp), Len = a[n].v;
	int ans = 1, pos = 0, pre, cur;
	for(RE int i = 1; i <= n; i++)
	{
		f[i] = 1, pre = 0;
		for(RE int j = 30; j >= 0; j--)
		{
			if ((m >> j) & 1){if (!((a[i].v >> j) & 1)) pre |= (1 << j);}
			else{
				if ((a[i].v >> j) & 1)
				{
					cur = Query(rt, 0, Len, pre, pre + (1 << j) - 1), pre |= (1 << j);
					if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
				}
				else{
					cur = Query(rt, 0, Len, pre + (1 << j), (LL)pre + (1LL << j + 1) - 1);
					if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
				}
			}
			if (!j)
			{
				cur = Query(rt, 0, Len, pre, pre);
				if (f[cur] + 1 > f[i]) f[i] = f[cur] + 1, g[i] = cur;
			}
		}
		if (ans < f[i]) ans = f[i], pos = i;
		if (i < n) Modify(rt, 0, Len, a[i].v, i);
	}
	printf("%d\n", (ans == 1) ? -1 : ans);
	if (ans > 1) while (pos) printf("%d ", a[pos].id), pos = g[pos];
}