#PQJ1542x8322. QOJ 1542_8322

    ID: 2632 传统题 1500ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:二十一省联合省选2024枚举

QOJ 1542_8322

NOI2024 联合省选 第一试魔法手杖(xor) 魔法手杖(xor) 【题目描述】 .提.示:我们在题目描述的最后提供了一份简要的、形式化描述的题面。 C 城是一座魔力之都,以最高的魔法师水平闻名。对于一名魔法师而言,最重要的 固然是魔法手杖和镶嵌在手杖上的魔法水晶。 每个魔法手杖和魔法水晶都可以用.魔.力.值来衡量其能力大小,一个魔法手杖的魔力 值是镶嵌在其上的所有魔法水晶中魔力值的最小值。 小ω 是C 城的一名见习魔法师,他想加强他的魔法手杖。在加强之前,小ω 的魔 法手杖镶嵌着n 颗魔法水晶,它们的魔力值分别为a1, a2, · · · , an。 小ω 准备使用一次强力的秘术来加强他的手杖。这一次秘术中,他可以任意选择 x,然后将所有魔法水晶的魔力值由ai 变为(ai ⊕x),其中⊕表示按位异或。由于小ω 能力有限,a1, a2, · · · , an 和x 都是[0, 2k −1] 中的整数。 小ω 还发现这个秘术可以定向加强。具体地,他可以花费bi 的体力值对第i 个魔 法水晶进行定向加强,将原本应变为(ai ⊕x) 的魔力值变为(ai + x)。小ω 能力有限,因 此他定向加强所花费的体力值总和不能超过m,且每个水晶只能被定向加强至多一次。 小ω 想知道他在加强魔法手杖后,魔法手杖的魔力值最大能为多少,但他并不会 算,所以请你来帮他计算。 .形.式.化.的:给定a1, a2, · · · , an 以及b1, b2, · · · , bn,满足ai ∈[0, 2k −1] 以及bi ≥0, 你需要给出S ⊆{1, 2, · · · , n} 以及x ∈[0, 2k −1] 满足以下条件: • ! i∈S bi ≤m; • 满足以上条件的前提下,最大化val(S, x) = min(min i∈S (ai + x), min i∈U\S(ai ⊕x)) 的值。 你只需要给出最大的val(S, x) 的值即可。 【输入格式】 从文件xor.in 中读入数据。 .本.题.有.多.组.测.试.数.据。输入的第一行包含两个整数c, T,表示测试点编号与测试数 据组数。样例中的c 表示该样例的数据范围与第c 个测试点的数据范围相同。 接下来依次给出每组输入数据,对于每组数据: • 第一行三个整数n, m, k; • 第二行n 个整数a1, a2, · · · , an,分别表示每个魔法水晶的初始魔力值; • 第三行n 个整数b1, b2, · · · , bn,分别表示每个魔法水晶定向加强需要的体力值。 【输出格式】 输出到文件xor.out 中。 对于每组测试数据输出一行一个整数表示小ω 能获得魔法手杖魔力值的最大值。 第5 页 共12 页

NOI2024 联合省选 第一试魔法手杖(xor) 【样例1 输入】 1 1 2 2 5 2 3 3 1 1 2 3 7 4 1 1 0 3 2 5 1 1 1 6 1 7 0 【样例1 输出】 1 5 2 2 【样例1 解释】 • 对于第一组数据,一种可行的方案为:定向强化魔法水晶5(即S = {5})并取 x = 4。最后得到的魔法水晶魔力值分别为5, 5, 6, 7, 11,故魔法手杖的魔力值为 5。可以证明不存在更优方案。 • 对于第二组数据,一种可行的方案为:定向强化魔法水晶1(即S = {1})并取 x = 1。 【样例2】 见选手目录下的xor/xor2.in 与xor/xor2.ans。 该组样例满足c = 4。 【样例3】 见选手目录下的xor/xor3.in 与xor/xor3.ans。 该组样例满足c = 7。 【样例4】 见选手目录下的xor/xor4.in 与xor/xor4.ans。 该组样例满足c = 9。 第6 页 共12 页

NOI2024 联合省选 第一试魔法手杖(xor) 【样例5】 见选手目录下的xor/xor5.in 与xor/xor5.ans。 该组样例满足c = 11。 【样例6】 见选手目录下的xor/xor6.in 与xor/xor6.ans。 该组样例满足c = 14。 【样例7】 见选手目录下的xor/xor7.in 与xor/xor7.ans。 该组样例满足c = 22。 【子任务】 设! n 表示单组测试点各组数据n 的和。对于所有测试数据, • T ≥1; • 1 ≤n ≤105,1 ≤! n ≤5 × 105; • 0 ≤m ≤109; • 0 ≤k ≤120; • ∀1 ≤i ≤n,0 ≤ai < 2k; • ∀1 ≤i ≤n,0 ≤bi ≤109。 测试点编号 ! n ≤ n ≤ m ≤ k ≤ 特殊性质 1 ∼3 10 10 109 10 / 4 ∼6 5 × 105 105 0 30 A 7, 8 2 109 B 9, 10 105 11 ∼13 C 14, 15 500 102 / 16 ∼18 5 × 104 104 60 19 ∼21 3 × 105 105 120 22 ∼25 5 × 105 特殊性质A:m = 0;∀1 ≤i ≤n,bi ≥1。 特殊性质B:m = 1;∀1 ≤i ≤n,bi ∈{1, 2},且至多只有1 个i 满足bi = 1。 特殊性质C:m = 1;∀1 ≤i ≤n,bi ∈{1, 2}。 第7 页 共12 页

NOI2024 联合省选 第一试魔法手杖(xor) 【提示】 本题输入文件较大,请使用较为快速的输入方式。 在评测环境中,你可以使用128 位有符号整型类型__int128,它可以存储范围在 [−2127, 2127 −1] 内的整数,使用方法与其他整型类型基本一致。 需要注意,该类型无法使用诸如cin/cout 或scanf/printf 等常规输入输出方式 进行输入输出。我们在选手目录下提供了一份__int128 的输入输出函数实现供选手选 择使用。 第8 页 共12 页