#P17750. 「RSOI-2C」异或 / xor
「RSOI-2C」异或 / xor
背景
题目来源:【HT-124-Div.3】核桃 CSP-J 组模拟赛
题目描述
小 R 觉得他的鹦鹉长得很漂亮,于是想带它去参加百鸟朝凤大会。
我们可以把小 R 生活的城市看作一张图,上面存在 个节点 ,其权值分别为 。
在这张图上存在若干条边,当两个节点 满足 且 时,则说明点 之间存在一条无向边。
小 R 突发奇想,想要通过改变节点权值的方法让这 个节点的鸟都能到达第 个节点参加百鸟朝凤大会(即让这 个节点相连通)。若要将一个节点 的权值修改为 (可以增加或减小, 为非负整数),则花费为 。
现在请你帮助小 R 计算出让这 个节点相连通的最小总花费。
其中, 表示按位异或运算,也就是 C++ 里的 ^ 运算符。
输入格式
输入共两行。
第一行,一个正整数 表示节点个数。
第二行, 个正整数 表示每个节点的初始权值。
输出格式
输出共一行,一个非负整数表示让 个节点相连通的最小花费。
4
37 38 39 40
6
1
7
0
提示
【样例解释 #1】
将节点 的权值修改为 ,花费 。可以证明此时图连通,且这是一种花费最少的方案。
【样例解释 #2】
无需进行任何操作,花费为 。
【数据范围】
对于所有测试数据,保证:,。
| 测试点编号 | 数据范围 | 特殊性质 |
|---|---|---|
| , | 无 | |
| 无特殊限制 | 保证存在至少一个 | |
| 保证 均为 的非负整数次幂 | ||
| 无 |