A7154 | 「联合省选 2024」魔法手杖
来源省选 / 2024
时间限制1500ms
内存限制1024MB
通过 / 提交0/0
题目描述
**提示：** 我们在题目描述的最后提供了一份简要的、形式化描述的题面。
C 城是一座魔力之都，以最高的魔法师水平闻名。对于一名魔法师而言，最重要的固然是魔法手杖和镶嵌在手杖上的魔法水晶。
每个魔法手杖和魔法水晶都可以用**魔力值**来衡量其能力大小，一个魔法手杖的魔力值是镶嵌在其上的所有魔法水晶中魔力值的最小值。
小 $\omega$ 是 C 城的一名见习魔法师，他想加强他的魔法手杖。在加强之前，小 $\omega$ 的魔法手杖镶嵌着 $n$ 颗魔法水晶，它们的魔力值分别为 $a_1,a_2,\dots,a_n$。
小 $\omega$ 准备使用一次强力的秘术来加强他的手杖。这一次秘术中，他可以任意选择 $x$，然后将所有魔法水晶的魔力值由 $a_i$ 变为 $(a_i \oplus x)$，其中 $\oplus$ 表示按位异或。由于小 $\omega$ 能力有限，$a_1,a_2,\dots,a_n$ 和 $x$ 都是 $[0,2^k-1]$ 中的整数。
小 $\omega$ 还发现这个秘术可以定向加强。具体地，他可以花费 $b_i$ 的体力值对第 $i$ 个魔法水晶进行定向加强，将原本应变为 $(a_i \oplus x)$ 的魔力值变为 $(a_i+x)$。小 $\omega$ 能力有限，因此他定向加强所花费的体力值总和不能超过 $m$，且每个水晶只能被定向加强至多一次。
小 $\omega$ 想知道他在加强魔法手杖后，魔法手杖的魔力值最大能为多少，但他并不会算，所以请你来帮他计算。
**形式化的：** 给定 $a_1,a_2,\dots,a_n$ 以及 $b_1,b_2,\dots,b_n$，满足 $a_i \in [0,2^k-1]$ 以及 $b_i\geq 0$，你需要给出 $S \subseteq \{1,2,\dots,n\}$ 以及 $x \in [0,2^k-1]$ 满足以下条件：
- $\sum \limits_{i\in S} b_i\leq m$；
- 满足以上条件的前提下，最大化 $val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))$ 的值。
你只需要给出最大的 $val(S,x)$ 的值即可。
C 城是一座魔力之都，以最高的魔法师水平闻名。对于一名魔法师而言，最重要的固然是魔法手杖和镶嵌在手杖上的魔法水晶。
每个魔法手杖和魔法水晶都可以用**魔力值**来衡量其能力大小，一个魔法手杖的魔力值是镶嵌在其上的所有魔法水晶中魔力值的最小值。
小 $\omega$ 是 C 城的一名见习魔法师，他想加强他的魔法手杖。在加强之前，小 $\omega$ 的魔法手杖镶嵌着 $n$ 颗魔法水晶，它们的魔力值分别为 $a_1,a_2,\dots,a_n$。
小 $\omega$ 准备使用一次强力的秘术来加强他的手杖。这一次秘术中，他可以任意选择 $x$，然后将所有魔法水晶的魔力值由 $a_i$ 变为 $(a_i \oplus x)$，其中 $\oplus$ 表示按位异或。由于小 $\omega$ 能力有限，$a_1,a_2,\dots,a_n$ 和 $x$ 都是 $[0,2^k-1]$ 中的整数。
小 $\omega$ 还发现这个秘术可以定向加强。具体地，他可以花费 $b_i$ 的体力值对第 $i$ 个魔法水晶进行定向加强，将原本应变为 $(a_i \oplus x)$ 的魔力值变为 $(a_i+x)$。小 $\omega$ 能力有限，因此他定向加强所花费的体力值总和不能超过 $m$，且每个水晶只能被定向加强至多一次。
小 $\omega$ 想知道他在加强魔法手杖后，魔法手杖的魔力值最大能为多少，但他并不会算，所以请你来帮他计算。
**形式化的：** 给定 $a_1,a_2,\dots,a_n$ 以及 $b_1,b_2,\dots,b_n$，满足 $a_i \in [0,2^k-1]$ 以及 $b_i\geq 0$，你需要给出 $S \subseteq \{1,2,\dots,n\}$ 以及 $x \in [0,2^k-1]$ 满足以下条件：
- $\sum \limits_{i\in S} b_i\leq m$；
- 满足以上条件的前提下，最大化 $val(S,x)=\min(\min \limits_{i \in S}(a_i+x),\min \limits_{i \in U \backslash S}(a_i \oplus x))$ 的值。
你只需要给出最大的 $val(S,x)$ 的值即可。
输入格式
**本题有多组测试数据。** 输入的第一行包含两个整数 $c,T$，表示测试点编号与测试数据组数。样例中的 $c$ 表示该样例的数据范围与第 $c$ 个测试点的数据范围相同。
接下来依次给出每组输入数据，对于每组数据：
- 第一行三个整数 $n,m,k$；
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，分别表示每个魔法水晶的初始魔力值；
- 第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$，分别表示每个魔法水晶定向加强需要的体力值。
接下来依次给出每组输入数据，对于每组数据：
- 第一行三个整数 $n,m,k$；
- 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，分别表示每个魔法水晶的初始魔力值；
- 第三行 $n$ 个整数 $b_1,b_2,\dots,b_n$，分别表示每个魔法水晶定向加强需要的体力值。
输出格式
对于每组测试数据输出一行一个整数表示小 $\omega$ 能获得魔法手杖魔力值的最大值。
输入输出样例
输入 #1
1 2 5 2 3 1 1 2 3 7 1 1 0 3 2 1 1 1 1 0
输出 #1
5 2
### 样例解释
**【样例 1 解释】**
- 对于第一组数据，一种可行的方案为：定向强化魔法水晶 $5$（即 $S=\{5\}$）并取 $x=4$，最后得到的魔法水晶魔力值分别为 $5,5,6,7,11$，故魔法手杖的魔力值为 $5$。可以证明不存在更优方案。
- 对于第二组数据，一种可行的方案为：定向强化魔法水晶 $1$（即 $S=\{1\}$）并取 $x=1$。
### 数据范围
设 $\sum n$ 表示单组测试点各组数据 $n$ 的和。对于所有测试数据，
- $T \geq 1$；
- $1 \leq n \leq 10^5$，$1 \leq \sum n \leq 5\times 10^5$；
- $0 \leq m \leq 10^9$；
- $0 \leq k \leq 120$；
- $\forall 1 \leq i \leq n, 0 \leq a_i<2^k$；
- $\forall 1 \leq i \leq n, 0 \leq b_i \leq 10^9$。
### 复杂度限制
时间限制：$1.50s$
内存限制：$1024.00MB$
### 提示
本题输入文件较大，请使用较为快速的输入方式。
在评测环境中，你可以使用 $128$ 位有符号整数类型
需要注意，此类型无法使用诸如
```cpp
#include<bits/stdc++.h>
using namespace std;
void read(__int128 &x){
// read a __int128 variable
char c; bool f = 0;
while(((c = getchar()) < '0' || c > '9') && c != '-');
if(c == '-'){f = 1; c = getchar();}
x = c - '0';
while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';
if(f) x = -x;
}
void write(__int128 x){
// print a __int128 variable
if(x < 0){putchar('-'); x = -x;}
if(x > 9)write(x / 10);
putchar(x % 10 + '0');
}
int main(){
__int128 a, b;
read(a);
read(b);
write(a+b);
return 0;
}
```
### 附件下载
[xor.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/jlx2n2mj)
**【样例 1 解释】**
- 对于第一组数据，一种可行的方案为：定向强化魔法水晶 $5$（即 $S=\{5\}$）并取 $x=4$，最后得到的魔法水晶魔力值分别为 $5,5,6,7,11$，故魔法手杖的魔力值为 $5$。可以证明不存在更优方案。
- 对于第二组数据，一种可行的方案为：定向强化魔法水晶 $1$（即 $S=\{1\}$）并取 $x=1$。
### 数据范围
设 $\sum n$ 表示单组测试点各组数据 $n$ 的和。对于所有测试数据，
- $T \geq 1$；
- $1 \leq n \leq 10^5$，$1 \leq \sum n \leq 5\times 10^5$；
- $0 \leq m \leq 10^9$；
- $0 \leq k \leq 120$；
- $\forall 1 \leq i \leq n, 0 \leq a_i<2^k$；
- $\forall 1 \leq i \leq n, 0 \leq b_i \leq 10^9$。
### 复杂度限制
时间限制：$1.50s$
内存限制：$1024.00MB$
### 提示
本题输入文件较大，请使用较为快速的输入方式。
在评测环境中，你可以使用 $128$ 位有符号整数类型
__int128，它可以存储范围在 $[-2^{127},2^{127}-1]$ 内的整数，使用方法与其他整型类型基本一致。需要注意，此类型无法使用诸如
cin/cout 或 scanf/printf 等常规输入输出方式进行输入输出。我们在选手目录下提供了一份 __int128 的输入输出函数实现供选手选择使用。```cpp
#include<bits/stdc++.h>
using namespace std;
void read(__int128 &x){
// read a __int128 variable
char c; bool f = 0;
while(((c = getchar()) < '0' || c > '9') && c != '-');
if(c == '-'){f = 1; c = getchar();}
x = c - '0';
while((c = getchar()) >= '0' && c <= '9')x = x * 10 + c - '0';
if(f) x = -x;
}
void write(__int128 x){
// print a __int128 variable
if(x < 0){putchar('-'); x = -x;}
if(x > 9)write(x / 10);
putchar(x % 10 + '0');
}
int main(){
__int128 a, b;
read(a);
read(b);
write(a+b);
return 0;
}
```
### 附件下载
[xor.zip](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/jlx2n2mj)
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？