【解题报告】Codeforces Global Round 19
赛时 $\tt{ABCDEF}$,$\text{rank 151}$。
改题 $\tt{GH}$。
G. Birthday
第一步个人感觉比较难以猜到(除非写爆搜),剩下的部分有一个地方想复杂了。
通过各种方式,可以证明最后的答案是 $2^{\lceil\log_2 n\rceil}$,证明如下:
考虑若最后的答案含有奇质因子 $p$,注意到一步操作 $(x,y)\to (x+y,|x-y|)$ 不可能将两个不同时为 $p$ 的倍数的数,都变成 $p$ 的倍数。
目标是 $x=2^{\lceil\log_2 n\rceil}$,我们首先希望把每个数字都变成 $2$ 的整次幂,然后如果有 $0$ 的话,就能 $(x,0)\to (x,x)\to (2x,0)$ 来 $\times 2$ 了。
考虑 $\dfrac{x}{2}$ 这个位置,左右可以拼起来组成若干个 $x$,产生的另外一个数字可以看作是一个子问题,每个元素都变成两倍。前面可能剩下一些,但那也是个子问题。
当 $n\le 2$ 的时候,本身就都是 $2$ 的整次幂了,可以直接返回。注意到这个序列中,元素个数有 $n$ 个,种类只有 $\mathcal{O}(\log n)$,因此肯定存在两个相等的数字($n=3$ 是最紧的,但是证明确实有),只需要 $(x,x)\to (2x,0)$,然后拿这个 $0$ 做上面的事情就行。
最后肯定还要一个 $(0,x)\to (x,x)$。
H. Minimize Inversions Number
感觉是只需要 $\text{Hint 1}$ 就能过了的题。
首先考虑将某一个单点 $i$ 换到最前面,对逆序对的贡献,应该形如:
$$ c_i=\sum_{j=1}^{i-1} [p_j<p_i] - \sum_{j=1}^{i-1}[p_j>p_i] $$
在有多个的时候呢?应该形如:
$$ \sum_{i\in S} c_i + f(S) - (\binom{|S|}{2} - f(S)) $$
其中 $f(S)$ 是 $S$ 的逆序对数。相当于把 $S$ 中原本就有的逆序对要加回来,但是在 $c$ 中我们认为 $S$ 里的顺序对会变成逆序对,也需要减去。如果设一开始的逆序对数为 $x$,那么某一组方案的答案就是:
$$ x+\binom{|S|}{2} + 2f(S) + \sum_{i\in S} c_i $$
前面的 $x+\binom{|S|}{2}$ 在 $|S|=k$ 固定时是定值,只要最小化后面的部分。尝试构造 $d_i$,满足后两项的值恰好是 $\sum_{i\in S} d_i$(就像把 $2f(S)$ 吃进去)。那么应该有:
$$ d_i=\sum_{j=1}^{i-1}[p_j<p_i]-[p_j>p_i]+2\sum_{j=i+1}^n [p_i>p_j\land j\in S] $$
考虑 $[p_i>p_j\land j\in S]$ 什么时候满足。一个关键性质是:
若 $i\in S$,$\forall j$ 满足 $j>i,p_j<p_i$,有 $j\in S$。
证明暂鸽。然后就可以改成:
$$ d_i=\sum_{j=1}^{i-1}[p_j<p_i]-[p_j>p_i]+2\sum_{j=i+1}^n [p_i>p_j] $$
时间复杂度 $\mathcal{O}(n\log n)$。