CWOI-N RER 1 ＞ 2 Solution

CWOI-N RER 1 > 2 Solution

声明：头图为断章取义。

这场比赛得 $200$ 分是保底，得 $300$ 分是基操，得 $350$ 分以上才是实力（但不多）。

A - 机读卡

No solutions yet.

这题数据倒还不能无脑造。

B - 数学题

打表题，稍微打一下就可以找到规律。

对于部分分：暴力得 $50$ 分。（普通暴力 $20$ 分加值域暴力 $30$ 分。）

如果要证明，暴算即可。

也可以建立情景，更好理解一些。（比如说在 $n$ 个球中抽取若干个不相邻的球的方案数。）

C - 膨胀加法 1

原创结论题，属于好猜好写但严格证明的计算量比较大的那一类。

对于部分分：送 $30$ 分。另外的 $50$ 分，是给乱搞做法的。由于常数较大，所以 $n$ 没有搞特别大。接下来介绍正解与严格证明步骤。

有一个很明显的结论：在一次运算中，较小的那个数一定是本来存在的数，而不是运算得到的数。这里不证明。

我们再猜一个结论：将 $a$ 排序后，对于 $a_i,a_j,a_k$ 满足 $i<j<k$，有 $a_k\oplus a_i\oplus a_j\ge a_k\oplus a_j\oplus a_i$。记这个结论为结论一。

得到这个结论后，很容易证明，答案为 $a_n\oplus a_1\oplus a_2\oplus \cdots \oplus a_{n-1}$。记这个结论为结论二。

结论一

主打一个暴算。这里给几点提示，不详细证明。

• 按运算的定义展开

• 交叉相乘、消元

• 两数作差与零比较

最终可证明结论。

结论二

在得到结论一之后，钦定第一个数是 $a_p$，那么答案为 $a_p\oplus a_1\oplus a_2\oplus \cdots \oplus a_{p-1}\oplus a_{p+1}\oplus a_{p+2}\oplus \cdots \oplus a_n$。显而易见，上式有最大值为 $a_n\oplus a_1\oplus a_2\oplus \cdots \oplus a_{n-1}$。

故将原数组排序并按上述方式计算即可。

D - 弱化题

原题：P6808。

这题数据真不好造，随机出来的数据的答案基本都是最小值。所以加了原题的数据，开了捆绑。

这是我写的题解，也可以参考一下其它题解。

对于 $Subtask1$，暴力。

对于 $Subtask2$，采用题解中的任何一种做法均可。

对于 $Subtask3$，需采用第四种解法。