Codeforces Round #783 (Div. 1)

发表于 2022-04-20 分类于 CF

A. Make it Increasing

暴力枚举 $0$ 所在位置，然后贪心。时间复杂度 $O(n^2)$。

设 $f_i$ 表示前 $i$ 个的最大值。则有 $f_i=\min{f_j+g(j,i)}$，其中 $g(j,i)$ 为区间 $[j,i]$ 的价值。

分三种情况，大力线段树即可。时间复杂度 $O(n\log n)$。

~~永远几乎不会构造题。~~

首先对于一个 $k\times k$ 的矩阵，可以用一条斜线去构造它。如图所示：

之后剩下的没被覆盖的点，再用一条斜线即可覆盖。如图：

于是大概需要 $\frac{2n+1}{3}$ 个就可以了。

树形DP，设 $f_u$ 表示节点 $u$ 与其父亲的边，需要在父亲节点的度数模 $2$ 的结果为 $f_u$ 时才可以消去。

那么一个节点的所有儿子的 $f_v$ 值的 $0,1$ 个数不能超过一个很小的数。

那么就有对于所有的叶子 $v$，$f_v=1$ （需要父亲的度数为奇数，这样这条边相邻的边就是父亲度数减一了。

根节点特殊，讨论一下即可。其他的点，根据度数奇偶性以及 $f_v$ 的 $0,1$ 个数共四种情况讨论，其他情况则无解。

判断完无解后，构造方案就很容易了，相当于 $0,1,0,1\cdots$ 或 $1,0,1,0\cdots$ 依次弄。

时间复杂度 $O(n)$。