笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 CF1305E 【Kuroni and the Score Distribution】

posted on 2020-03-06 08:09:17 | under 题解 |

比较自然的想法是从头开始填 $1,2,3\cdots$,因为这样容易填且满足条件。同时可以发现,这种构造方式是使得每个位置作为 $k$ 时,贡献三元组最多的方式:由于序列满足单调性,所以一定不存在前面的 $i,j$ 彼此有交。那么对于一个 $a_k=k$ 他可以贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案。

考虑如果超出 $m$ 如何处理。假设当前答案超出了 $x$ 。对于一个 $k$ ,按照上述方式能够贡献 $\lfloor \frac{k-1}{2}\rfloor$ 的答案,那么如果想要只贡献 $\lfloor \frac{k-1}{2}\rfloor-x$ 的答案,就需要让其中的 $x$ 对 $(i,j)$ 无效。具体的,考虑令当前的 $k$ 变为 $k+2x$ ,那么考虑前 $k-1$ 个数里面最大的是 $k-1$ ,只能去匹配 $2x+1$,这样就会少掉 $2x$ 个可以用的数,答案变成了 $\lfloor\frac{k-1-2x}{2}\rfloor=\lfloor \frac{k-1}{2}\rfloor-x$ 。

那么补齐 $n$ 个数也很简单。只需要考虑如果当前填了的最大的数是 $j$ ,从 $10^9$ 向下按照 $2\cdot j$ 的步长递减即可。不难证明这样做是对的。

int main(){
    std :: cin >> n >> m ;
    for (int i = 1 ; i <= n ; ++ i){
        ans[i] = i ; cnt += (i - 1) / 2 ;
        if (cnt >= m){
            int s = 1000000000 ;
            ans[i] += 2 * (cnt - m) ;
            for (int j = n ; j > i ; -- j)
                ans[j] = (s -= (ans[i] + 1)) ;
            gf = 1 ; break ;
        }
    }
    if (gf)
        for (int i = 1 ; i <= n ; ++ i)
            printf("%d ", ans[i]) ;
    else return puts("-1"), 0 ;
}