Codeforces Round 836 (Div. 2) solution

· · 个人记录

A

正着来一遍，再倒着来一遍。

B

$n$ 是偶数：考虑最简单的 $n=2$ 的情况，此时答案是 $2,6$，然后，考虑偶数个数字异或和为 $0$，那么只需要前 $n-2$ 个填 $3$，最后两个填 $2,6$ 就可以。 ### C 坑点：直接匹配是错误的。 考虑从弱化版入手，不考虑 $a_1 = x$ 的限制。 那么对于 $i \in [2,n-1]$，$a_i = i$。 那么考虑现在的问题，对 $[2,n-1]$ 分配数字。 $[2,n-1]$ 可选的数字原来是 $2,3,\cdots,n-1$，加上 $a_1 = x$ 的限制后，可选数字失去了 $x$，加入了 $n$。 也就是说，如果其他位置保持不变，那么现在 $a_x = n$。 作一个猜测：有解当且仅当 $x | n$。 首先，$x$ 能整除 $n$ 时显然有解。 如果不能整除的话， $x$ 就需要其倍数去递补，但最后总有一个数不可递补。 如果有解，简单的设置 $a_x = n$ 可能不是最优的。 考虑 $x$ 与其最近的，能整除 $n$ 且是 $x$ 倍数的位置进行交换，反复进行，直到不存在可交换的小于 $n$ 的位置。 维护这个操作，只需要每次交换时计算 $\frac{n}{x}$，求这个东西的最小质因数 $y$，然后 $x$ 与 $xy$ 交换就可以。 每个数的最小质因数可以用筛素数同样原理的方法求出来。 ### D 如果数列最小值，最大值已经确定，那么设数列能得到的出来的最小总和为 $x$，最大总和为 $y$，那么这个序列能表示出 $[x,y]$ 之间的所有总和。 根据上述，如果固定了极差，那么可以二分求合法的数列最小值。 猜个结论，只要极差够大，一定能存在一组合法解。 这里取极差为 $5n$，实测可以通过。