AT_abc249_g.[ABC249G] Xor Cards

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有 $N$ 张卡片，编号为 $1,\dots,N$ 。第 $i$ 张卡片的正面写有整数 $A_i$ ，背面写有整数 $B_i$ 。

你可以选择任意数量（至少一张）的卡片，使得所选卡片正面上的整数的异或和不超过 $K$ 。请你求出在满足条件的情况下，所选卡片背面上的整数的异或和的最大可能值。

异或和的定义如下：对于整数 $a,b$ ，它们的异或和 $a \oplus b$ 定义为：将 $a,b$ 用二进制表示后，每一位上只有一方为 $1$ 时该位为 $1$ ，否则为 $0$ 。

例如， $3 \oplus 5 = 6$ （二进制为 $011 \oplus 101 = 110$ ）。
一般地， $k$ 个整数 $p_1,\dots,p_k$ 的异或和定义为 $((\cdots((p_1 \oplus p_2) \oplus p_3)\oplus\cdots)\oplus p_k)$ ，并且可以证明其结果与顺序无关。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
$A_1$ $B_1$
$\vdots$
$A_N$ $B_N$

输出格式

请输出满足条件的卡片选择方案中，所选卡片背面上的整数的异或和的最大值。如果无法满足条件，则输出 $-1$ 。

输入输出样例

输入#1
```
4 2
1 1
3 2
2 2
0 1
```
输出#1
```
3
```
输入#2
```
1 2
3 4
```
输出#2
```
-1
```

输入#3

10 326872757
487274679 568989827
267359104 968688210
669234369 189421955
1044049637 253386228
202278801 233212012
436646715 769734012
478066962 376960084
491389944 1033137442
214977048 1051768288
803550682 1053605300

输出#3

1064164329

说明/提示

限制条件

$1 \leq N \leq 1000$
$0 \leq K < 2^{30}$
$0 \leq A_i, B_i < 2^{30}\ (1 \leq i \leq N)$
输入均为整数

样例解释 1

选择卡片 $1,2$ ，正面整数的异或和为 $2$ ，背面整数的异或和为 $3$ ，这是最大值。

样例解释 2

无法选择满足条件的卡片。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页