Atcoder abc249
https://atcoder.jp/contests/abc249/tasks
G - Xor Cards
n个卡, 每张有正面ai,背面bi
求让正面的 xor 和 <= K时, 背面 xor和 最大
求最大值
范围
n 1000
k (1<<30)
ai,bi [0,1<<30)
我的思路
对于xor和不等式没啥想法
一个是 对结果从高位到低位去贪心
比如 第i位 结果xor为1
那么 假设当前集合中, 对应b的i位为1的选奇数个, i位为0的选偶数个
但如何控制与Ai 的关系
第二个方向就是 xor 是不是有线性基, 但是如何把线性基的 结果大小 和 对应的xor和 尽量大
第三个就是N只有1000, 有啥n^2 的方法
dp[i][j]
, 前i的j个, 感觉”个数” 和目标之间没啥关系