Solution. LG10218 [省选联考 2024] 魔法手杖
March 8, 2024 •
2 Comments
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$
