#P9081. 「HNOI2021 省集 Day3」合成小丹

    ID: 5165 传统题 文件IO:merge 1000ms 512MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2700省选/NOI-按位贪心位集求交位集求补Kraft 不等式与等式

「HNOI2021 省集 Day3」合成小丹

题目描述

丹最喜欢做的两件事情分别是踩人和位运算,所以现在他要用位运算来踩你。

丹给了你 nn 个范围在 [0,2w−1][0, 2^w − 1] 内的非负整数,你需要执行下面两种操作共 n−1n − 1 次:

  1. 选择两个非负整数 xx 和 yy,将两个非负整数合成成一个非负整数 zz,其中 z=⌊(x∣y)2⌋z=\lfloor \frac{(x|y)}{2}\rfloor。(这里的运算符 ∣| 表示的是按位或)
  2. 选择一个非负整数 xx 并将其删去。

不难发现每次操作后你拥有的整数数量都会减少恰好一个,所以在 n−1n − 1 次操作后你会拥有恰好一个非负整数,你需要最小化剩下来的这个整数的值。你只需要输出最后这个非负整数的值。

输入格式

从文件 merge.in 中读入数据。

本题包含多组数据,输入第一行一个整数 TT 表示数据组数,对于每组测试数据:

第一行两个正整数 n,wn, w,含义见题面。

第二行 nn 个非负整数 a1,a2,…,ana_1,a_2,\ldots,a_n,描述你一开始拥有哪些数。

输出格式

输出到文件 merge.out 中。

对于每组测试数据:

输出一行一个非负整数表示最后你剩下来的值最小是什么。

样例

样例 1

3
3 4
9 10 12
4 3
7 7 7 7
7 3
5 2 0 1 3 1 4
5
1
0

在第一组数据中一种最优的操作方案:

一开始你拥有的整数有 {9,10,12}\{9, 10, 12\};第一次操作选择删除整数 1212,你拥有的整数有 {9,10}\{9, 10\};第二次操作选择合并整数 99 和 1010,9∣10=11,⌊112⌋=59|10 = 11, \lfloor \frac{11}{2}\rfloor= 5,你拥有的整数有 {5}\{5\};最后你剩下的整数为 55,不难发现没有更优的做法了。

在第二组数据中一种最优的操作方案:

一开始你拥有的整数有 {7,7,7,7}\{7, 7, 7, 7\};第一次操作选择合并整数 77 和 77,7∣7=7,⌊72⌋=37|7 =7, \lfloor \frac{7}{2}\rfloor = 3,你拥有的整数有 {3,7,7}\{3, 7, 7\};第二次操作选择合并整数 77 和 77,你拥有的整数有 {3,3}\{3, 3\};第三次操作选择合并整数 33 和 33,3∣3=3,⌊32⌋=13|3 = 3, \lfloor \frac{3}{2}\rfloor = 1,你拥有的整数有 {1}\{1\};最后你剩下的整数为 11,不难发现没有更优的做法了。

在第三组数据中一种最优的操作方案:

删掉除了 00 以外的其他整数。

样例 2

见选手目录下的 merge/merge2.in 与 merge/merge2.ans。

该样例满足测试点 1∼21 \sim 2 的性质。

样例 3

见选手目录下的 merge/merge3.in 与 merge/merge3.ans。

该样例满足测试点 6∼86\sim 8 的性质。

数据范围

对于所有测试点,满足 1≤T≤101\le T\le 10,1≤n≤1051\le n\le 10^5,0≤w≤600\le w\le 60,ai∈[0,2w−1]a_i\in[0,2^w-1]。

每个测试点的具体限制见下表:

测试点编号 nn ww 特殊性质
1∼21\sim 2 ≤6\le 6 ≤60\le 60 无
3∼53\sim 5 ≤8\le 8
6∼86\sim 8 ≤300\le 300 ≤12\le 12
9∼129\sim 12 ≤5000\le 5000 ≤18\le 18
13∼1513\sim 15 ≤40\le 40
16∼1716\sim 17 ≤105\le 10^5 ≤60\le 60 A\text{A}
18∼2018\sim 20 无

特殊限制 A\text{A}:保证所有 aia_i 都可以表示成 22 的整数次幂。