CWOI-N RER 1 ＞ 2 Solution
CWOI-N RER 1 > 2 Solution
声明：头图为断章取义。
这场比赛得 200 200 200 分是保底，得 300 300 300 分是基操，得 350 350 350 分以上才是实力（但不多）。
A - 机读卡
No solutions yet.
这题数据倒还不能无脑造。
B - 数学题
打表题，稍微打一下就可以找到规律。
对于部分分：暴力得 50 50 50 分。（普通暴力 20 20 20 分加值域暴力 30 30 30 分。）
如果要证明，暴算即可。
也可以建立情景，更好理解一些。（比如说在 n n n 个球中抽取若干个不相邻的球的方案数。）
C - 膨胀加法 1
原创结论题，属于好猜好写但严格证明的计算量比较大的那一类。
对于部分分：送 30 30 30 分。另外的 50 50 50 分，是给乱搞做法的。由于常数较大，所以 n n n 没有搞特别大。接下来介绍正解与严格证明步骤。
有一个很明显的结论：在一次运算中，较小的那个数一定是本来存在的数，而不是运算得到的数。这里不证明。
我们再猜一个结论：将 a a a 排序后，对于 a i , a j , a k a_i, a_j, a_k ai,aj,ak 满足 i < j < k i \lt j \lt k i<j<k，有 a k ⊕ a i ⊕ a j ≥ a k ⊕ a j ⊕ a i a_k \oplus a_i \oplus a_j \ge a_k \oplus a_j \oplus a_i ak⊕ai⊕aj≥ak⊕aj⊕ai。记这个结论为结论一。
得到这个结论后，很容易证明，答案为 a n ⊕ a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n − 1 a_n \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n - 1} an⊕a1⊕a2⊕⋯⊕an−1。记这个结论为结论二。
结论一
主打一个暴算。这里给几点提示，不详细证明。
-
按运算的定义展开
-
交叉相乘、消元
-
两数作差与零比较
最终可证明结论。
结论二
在得到结论一之后，钦定第一个数是 a p a_p ap，那么答案为 a p ⊕ a 1 ⊕ a 2 ⊕ ⋯ ⊕ a p − 1 ⊕ a p + 1 ⊕ a p + 2 ⊕ ⋯ ⊕ a n a_p \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{p - 1} \oplus a_{p + 1} \oplus a_{p + 2} \oplus \dots \oplus a_n ap⊕a1⊕a2⊕⋯⊕ap−1⊕ap+1⊕ap+2⊕⋯⊕an。显而易见，上式有最大值为 a n ⊕ a 1 ⊕ a 2 ⊕ ⋯ ⊕ a n − 1 a_n \oplus a_1 \oplus a_2 \oplus \dots \oplus a_{n - 1} an⊕a1⊕a2⊕⋯⊕an−1。
故将原数组排序并按上述方式计算即可。
D - 弱化题
原题：P6808。
这题数据真不好造，随机出来的数据的答案基本都是最小值。所以加了原题的数据，开了捆绑。
这是我写的题解，也可以参考一下其它题解。
对于 S u b t a s k 1 Subtask\ 1 Subtask 1，暴力。
对于 S u b t a s k 2 Subtask\ 2 Subtask 2，采用题解中的任何一种做法均可。
对于 S u b t a s k 3 Subtask\ 3 Subtask 3，需采用第四种解法。