#P12290. [蓝桥杯 2024 国 Java A] 基因组合

[蓝桥杯 2024 国 Java A] 基因组合

题目描述

在医学领域,两位杰出的医生,小蓝和小乔,正在研究一种新型的基因治疗方案。他们需要从 nn 个候选基因中分别选择一个,并通过某种特定的运算将它们组合起来,以评估治疗方案的有效性。

已知这 nn 个候选基因可以用一个数组 {a1,a2,,an}\{a_1, a_2, \cdots, a_n\} 来表示,其中 aia_i 代表第 ii 个基因的特性数值。而将两个基因组合起来的方式,则是将它们的特性数值进行异或运算(用符号 \oplus 表示)。

小蓝倾向于激进的治疗方案,他总是希望所选基因组合的异或值尽可能大,以获得显著的治疗效果。小乔则更注重治疗的稳定性,他总是希望所选基因组合的异或值尽可能小,以降低治疗风险。

现在,两位医生需要决定先后选择的顺序。

假设双方都足够聪明,且都会使用最佳策略来最大化或最小化基因组合的异或值。请问,如果小蓝先选择基因,小乔后选择,那么他们能够得到的基因组合的最大异或值会是多少?反之,如果小乔先选择基因,小蓝后选择,那么他们能够得到的基因组合的最小异或值又会是多少?

输入格式

输入的第一行包含一个整数 nn,表示候选基因的数量。

第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \cdots, a_n,相邻整数之间使用一个空格分隔,依次表示每个基因的特性数值。

输出格式

输出一行,包含两个整数。第一个整数表示小蓝先选择基因时能够得到的基因组合的最大异或值;第二个整数表示小乔先选择基因时能够得到的基因组合的最小异或值。

4
2 3 5 6
3 5

提示

样例说明

在给定样例中,候选基因的数量为 44,特性数值分别为 22335566

当小蓝先选择基因时,小蓝可以选择特性值为 66 的基因,使基因组合的异或值尽可能大,小乔则会选择特性值为 55 的基因,使基因组合的异或值尽可能小:65=36 \oplus 5 = 3

当小乔先选择基因时,小乔可以选择特性值为 66 的基因,使基因组合的异或值尽可能小,小蓝则会选择特性值为 33 的基因,使基因组合的异或值尽可能大:63=56 \oplus 3 = 5

评测用例规模与约定

  • 对于 30%30\% 的评测用例,2n1032 \leq n \leq 10^31ai1051 \leq a_i \leq 10^5
  • 对于所有评测用例,2n1052 \leq n \leq 10^51ai1091 \leq a_i \leq 10^9