CF1075-div2 / Contest 2189

Problem A

签到题

Problem B

签到题

Problem C1

简单构造

Problem C2

正解是建立在 $C1$ 的基础上的。易知 $n=2^x+r$，其中 $r$ 为偶数且 $r<2^x$。

考虑在原本构造的基础上交换 $p_1$ 与 $p_r$，则 $p_1=r+1<n$，指向 $p_{r+1}$

而 $p_r=2^x+r$，同样指向 $p_{r+1}$

---

虽然我没有往正解的方向想，但我利用正解大部分位置都指向 $n$ 的特性反向爆搜过了

Problem D1

不含 $?$ 的版本，即原序列固定。

考虑从小到大向序列中插入数字，即可发现 $w$ 对应的贡献的规律。

Problem D2

承接上文考虑策略，不难发现选择 $w_i=1$ 比 $w_i=0$ 带来的代价更小

从而要考虑 $c$ 的因子及其 $2$ 的因子数。

这样大体思路就差不多了……

---

E，F 咕咕咕