33OJ
登录 注册

#P17750. 「RSOI-2C」异或 / xor

「RSOI-2C」异或 / xor

背景

题目来源:【HT-124-Div.3】核桃 CSP-J 组模拟赛

题目描述

小 R 觉得他的鹦鹉长得很漂亮,于是想带它去参加百鸟朝凤大会。

我们可以把小 R 生活的城市看作一张图,上面存在 nn 个节点 1,2,3,⋯ ,n1,2,3,\cdots,n,其权值分别为 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。

在这张图上存在若干条边,当两个节点 u,vu,v 满足 au⊕av≥min⁡(au,av)a_u \oplus a_v \geq \min(a_u,a_v) 且 u≠vu \not= v 时,则说明点 u,vu,v 之间存在一条无向边。

小 R 突发奇想,想要通过改变节点权值的方法让这 nn 个节点的鸟都能到达第 nn 个节点参加百鸟朝凤大会(即让这 nn 个节点相连通)。若要将一个节点 ii 的权值修改为 ai′a_i'(可以增加或减小,ai′a_i' 为非负整数),则花费为 ∣ai−ai′∣|a_i-a_i'|。

现在请你帮助小 R 计算出让这 nn 个节点相连通的最小总花费。

其中,⊕\oplus 表示按位异或运算,也就是 C++ 里的 ^ 运算符。

输入格式

输入共两行。

第一行,一个正整数 nn 表示节点个数。

第二行,nn 个正整数 aia_i 表示每个节点的初始权值。

输出格式

输出共一行,一个非负整数表示让 nn 个节点相连通的最小花费。

4
37 38 39 40
6
1
7
0

提示

【样例解释 #1】

将节点 11 的权值修改为 3131,花费 66。可以证明此时图连通,且这是一种花费最少的方案。

【样例解释 #2】

无需进行任何操作,花费为 00。

【数据范围】

对于所有测试数据,保证:1≤n≤1051 \leq n \leq 10^5,0≤ai≤231−10 \leq a_i \leq 2^{31}-1。

测试点编号 数据范围 特殊性质
1∼21 \sim 2 n≤103n \leq 10^3,ai≤103a_i \leq 10^3 无
3∼53 \sim 5 n≤103n \leq 10^3
6∼106 \sim 10 n≤3n \leq 3
1111 无特殊限制 保证存在至少一个 ai=0a_i=0
12∼1312 \sim 13 保证 aia_i 均为 22 的非负整数次幂
14∼2014 \sim 20 无