CF1747 Sol

· · 个人记录

至今见过的最简单的 Div.2，1h 不到就下班了。

A

正负数分到两个集合。

B

交换第一个 B 和倒数第一个 N，第二个 B 和倒数第二个 N，以此类推，需要交换 \lceil \frac{n}{2} \rceil 次。

C

显然最优会把 a_{2 \sim n} 中最小的值丢进来，并且这个动作是重复的。Alice 肯定换进来外面的最小值，Bob 会换外面的次小值或者是 a_1-1，下面的东西都是重复的，做个比较就好。

2022.11.5 7:51 补：其实不用看次小值，只需要比较外面的最小值就好了。也就是说如果 a_1 是全局非严格最小值 Bob 赢。

D

首先一次操作异或和根本不会变，所以合法的充分（并非充要）条件是区间异或和为 0。

接下来如果区间内和为 0 那么答案就是 0。否则如果区间长度是奇数答案就是 1。排除这三种情况后继续讨论。

如果是偶数，那么有解当且仅当能分成两个奇数段满足两个段异或和均为 0。要判断有没有这个分界 p，因为分界一定满足 pre_p = pre_{l-1} 并且 p 的奇偶性和 l 相等，可以维护 2n 个 set 解决，可以用来判断有无解。

答案一定是 2 吗？当然出了点小问题，如果 a_l=0 或者 a_r=0 的话这里的答案是 1 不是 2。

E

将问题抽象成从网格图，每次向右或向上，从 (0,0) \to (n,m) 的路径上选出一些点构成点集，问所有本质不同的点集大小和。

假设我们枚举了点集，但是可以形成这个点集的路径太多，我们得通过一种方法让它在所有的路径中只有一种合法供我们计算。在这里我们强制两个点间采用先向上再向右的方式，这样两个点间的方案唯一，进而一个点集只对应一条路径。

那么会形成很多个拐点，我们枚举先右后上的拐点个数（拐点可以是先上后右，也可以是先右后上，这个不重要），记其为 i。那么拐点个数为 i 的方案数为 \dbinom{n}{i}\dbinom{m}{i}。

注意到我们忽视了路径上的除了拐点和起点终点的所有点，这些点加入仍然对应同一条路径，因此我们需要计算。那么现在有 s=n+m-i-1 个点可以任取，总方案为 \displaystyle \sum_{i=0}^s \dbinom{s}{i} = 2^s 个，拐点上的贡献为 \displaystyle \sum_{i=0}^s \dbinom{s}{i}i。这个贡献的处理方式是，你发现 \displaystyle \sum_{i=0}^s \dbinom{s}{i}i = \displaystyle \sum_{i=0}^s \dbinom{s}{s-i}i，两者相加就是 \displaystyle s\sum_{i=0}^s \dbinom{s}{i} = s2^s，那么答案就是 s2^{s-1}。

注意终点和起点以及枚举的拐点个数（即 i+2）需要被计算 2^s 次。