#P5514. [MtOI2019] 永夜的报应

    ID: 4489 Type: RemoteJudge 1000ms 125MiB Tried: 0 Accepted: 0 Difficulty: 2 Uploaded By: Tags>数学贪心2019洛谷原创O2优化

[MtOI2019] 永夜的报应

题目背景

在这世上有一乡一林一竹亭,也有一主一仆一仇敌。

有人曾经想拍下他们的身影,却被可爱的兔子迷惑了心神。

那些迷途中的人啊,终究会消失在不灭的永夜中……

题目描述

蓬莱山 辉夜(Kaguya)手里有一堆数字。

辉夜手里有 nn 个非负整数 a1,a2ana_1,a_2\cdots a_n,由于辉夜去打 Gal Game 去了,她希望智慧的你来帮忙。

  • 你需要将这些数分成若干组,满足 nn 个数中的每一个数都恰好被分到了一个组中,且每一组至少包含一个数。

定义一组数的权值为该组内所有数的异或和。请求出一种分组方案,使得分出的所有组数的权值之和最小,输出权值之和的最小值。

输入格式

输入的第一行包含一个正整数 nn,表示给定的非负整数的数量。

接下来一行包含 nn 个非负整数 a1,a2ana_1,a_2\cdots a_n

输出格式

输出一行一个整数表示答案。

3
1 2 5
6
6
9 18 36 25 9 32

15

提示

样例 11 解释:

一种最优的分组方案如下:

  • 将第 11 个数和第 33 个数分为一组,该组的权值为 15=41\oplus 5 = 4
  • 将第 22 个数分为一组,该组的权值为 22

该分组方案的所有组的权值之和为 4+2=64 + 2 = 6,可以证明,不存在权值之和更小的分组方案。

样例 22 解释:

一种最优的分组方案如下:

  • 将第 11 个数和第 55 个数分为一组,该组的权值为 99=09\oplus 9 = 0
  • 将第 22 个数和第 44 个数分为一组,该组的权值为 1825=1118\oplus 25 = 11
  • 将第 33 个数和第 66 个数分为一组,该组的权值为 3632=436\oplus 32 = 4

该分组方案的所有组的权值之和为 0+11+4=150 + 11 + 4 = 15。可以证明,不存在权值之和更小的分组方案。

子任务

  • 对于 80%80\% 的数据,满足 n15n\leq 15
  • 对于 100%100\% 的数据,满足 n106,ai109n\leq 10^6,a_i \leq 10^9

题目来源

迷途之家2019联赛(MtOI2019) T1

出题人:disangan233