Solution. LG10218 [省选联考 2024] 魔法手杖
Description
给你 $n$ 个 $[0,2^k)$ 中的整数 $a_1,a_2,\dots,a_n$，第 $i$ 个数对应代价 $b_i$。
你需要选取一个 $U=\{1,2,\dots,n\}$ 的子集 $S$，满足 $\sum_{i\in S} b_i\le m$，以及一个 $[0,2^k)$ 中的整数 $x$，最大化 $\min\{\min_{i\in S}\{a_i+x\},\min_{i\in U\setminus S}\{a_i\oplus x\}\}$。
共 $T$ 组数据。
$1\le n\le 10^5,1\le \sum n\le 5\times 10 ^5,0\le k\le 120,0\le m\le 10^9,0\le b_i\le 10^9$
Soluton
省选考场上已经无限接近这个题的正解，可以由于有一些细节没考虑清楚，少写了一些情况，最后挂到了 36pts，喜提暴力同分。
题目让我们将数分为加法和异或两部分，由于对一堆数进行异或的贡献很难计算，我们尝试着将这个问题放到 01-trie 上考虑。
特判掉将所有数都分入加法部分的情况。
我们希望从高往低逐位确定 $x$ 以及最终的答案。
不妨设我们当前走到了 trie 上的某个结点 $u$，已经确定的答案为 $ans$（$ans$ 只有高位有值），$ans$ 应当恰好是从根走到 $u$ 的路径异或上 $x$ 对应的二进制数。
我们首先需要判断 $ans$ 的当前位是否能够为 $1$，如果可以则必然要令这一位为 $1$。我们在这里只讨论 $u$ 有两个儿子的情形，一个儿子是类似的。若希望 $ans$ 的当前位为 $1$，我们必须将 $u$ 一个儿子子树内的所有数都划分进加法部分（这个操作在后文被称作删除）。同时，我们还需要加法部分对答案的贡献也 $\ge ans\mid 2^d$，其中 $2^d$ 即为当前位的权值。
具体来说，我们可以枚举要删除哪个儿子并判断是否可行，首先我们需要儿子子树内所有数对应的 $b_i$ 之和不超过剩余可用的代价，其次加法部分的数的最小值 $mn$ 需要满足 $mn+(x\mid(2^d-1))\ge ans\mid 2^d$，这里是在考虑加法部分在最优情形下对答案的贡献，在无需关心异或部分取值时，$x$ 的值可以任取，所以我们将还未确定的低位全部置为了 $1$。如果发现删除某一个儿子可以使得答案的当前位为 $1$，就对应的更新 $ans$ 与 $x$，朝另一个儿子递归即可。
若我们确定了 $ans$ 的当前位不可能为 $1$，首先我们仍考虑是否要删除一棵子树并令异或部分的当前位为 $1$，此时异或部分必然不会对最终的答案产生限制，只需要考虑加法部分，很显然，最优解即是将剩下的低位全部置为 $1$，所以我们直接用算出的数更新全局答案即可。现在只剩下不删除子树的情况，我们枚举 $x$ 的取值，此时当前位异或为 $1$ 的子树不会对答案产生限制，朝异或为 $0$ 的子树递归即可。
在任何情况下，我们都只会朝 $u$ 的每个儿子递归不超过一次，trie 上的每个结点至多被访问一次，所以总复杂度为 $O(nk)$。
Code
此为考场代码加上少量修改，仅供参考，变量命名与含义和题解中不完全一致。
namespace Main{
const int N = 100005;
const int S = 12000005;
const __int128_t inf = __int128_t(1) << 120;
int c, t, n, m, k, b[N], ch[S][2], tot;
__int128_t a[N], mn[S], g_ans;
ll sum[S];
void insert(__int128_t x, int cost){
int p = 0;
for(int i = k - 1; i >= 0; i--){
if(!ch[p][x >> i & 1]){
ch[p][x >> i & 1] = ++tot;
mn[tot] = inf;
sum[tot] = 0;
}
p = ch[p][x >> i & 1];
mn[p] = min(mn[p], x);
sum[p] += cost;
}
}
void solve(int p, int d, __int128_t mn_val, ll cost, __int128_t x, __int128_t ans){
if(d == 0){
g_ans = max(g_ans, min(mn_val + x, ans));
return;
}
__int128_t one = 1; one <<= d - 1;
if(!ch[p][0] || !ch[p][1]){
if(ch[p][0]){
solve(ch[p][0], d - 1, mn_val, cost, x | one, ans | one);
}
if(ch[p][1]){
if(x + mn_val > ans) solve(ch[p][1], d - 1, mn_val, cost, x, ans | one);
else{
g_ans = max(g_ans, x + mn_val + one - 1);
solve(ch[p][1], d - 1, mn_val, cost, x | one, ans);
}
}
return;
}
bool del = false;
if(cost + sum[ch[p][0]] <= m){
if(min(mn_val, mn[ch[p][0]]) + x > ans){
solve(ch[p][1], d - 1, min(mn_val, mn[ch[p][0]]), cost + sum[ch[p][0]], x, ans | one);
del = true;
}
else{
g_ans = max(g_ans, min(mn_val, mn[ch[p][0]]) + x + one - 1);
}
}
if(cost + sum[ch[p][1]] <= m){
if(min(mn_val, mn[ch[p][1]]) + x + one > ans){
solve(ch[p][0], d - 1, min(mn_val, mn[ch[p][1]]), cost + sum[ch[p][1]], x | one, ans | one);
del = true;
}
else{
g_ans = max(g_ans, min(mn_val, mn[ch[p][1]]) + x + one + one - 1);
}
}
if(!del){
solve(ch[p][0], d - 1, mn_val, cost, x, ans);
solve(ch[p][1], d - 1, mn_val, cost, x | one, ans);
}
}
void Main(){
input(c, t);
while(t--){
for(int i = 0; i <= tot; i++) ch[i][0] = ch[i][1] = 0;
g_ans = 0, tot = 0;
input(n, m, k);
__int128_t mn_a = inf; ll sum_b = 0;
for(int i = 1; i <= n; i++) input(a[i]), mn_a = min(mn_a, a[i]);
for(int i = 1; i <= n; i++) input(b[i]), sum_b += b[i];
if(sum_b <= m) g_ans = mn_a + (__int128_t(1) << k) - 1;
for(int i = 1; i <= n; i++) insert(a[i], b[i]);
solve(0, k, inf, 0, 0, 0);
write(g_ans);
puts("");
}
return;
}
} // namespace Main本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。
@(哈哈)