「联合省选 2024」魔法手杖_信奥算法NOI/NOI+/CTSC

题目描述

提示： 我们在题目描述的最后提供了一份简要的、形式化描述的题面。

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$ ，分别表示每个魔法水晶定向加强需要的体力值。

输出格式

对于每组测试数据输出一行一个整数表示小 $\omega$ 能获得魔法手杖魔力值的最大值。

输入输出样例

输入#1

输出#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$ 位有符号整数类型 __int128，它可以存储范围在 $[-2^{127},2^{127}-1]$ 内的整数，使用方法与其他整型类型基本一致。

需要注意，此类型无法使用诸如 cin/cout 或 scanf/printf 等常规输入输出方式进行输入输出。我们在选手目录下提供了一份 __int128 的输入输出函数实现供选手选择使用。

#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

A101466.「联合省选 2024」魔法手杖