\(\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];
}