• 周六. 7月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

Codeforces Round #737 (Div. 2)

admin

11月 28, 2021

比赛链接 – Codeforces Round #737 (Div. 2)

A. Ezzat and Two Subsequences

(a_1, a_2, dots, a_{n-1})一组,(a_n)一组。

B. Moamen and k-subarrays

首先,原数组要能被分成(k)个非降子数组。

其次,每个子数组内元素的排名要连续。

遍历一下就完事了。

C. Moamen and XOR

难度突然上升,DP+组合数学。

回顾一下,与操作时全1为1,异或操作是奇数个1为1。

然后将每个数都当作(k)位二进制数,从高位开始DP,记(dp_{i, 0})表示考虑前(i)位时等式两边相等的方案数,(dp_{i, 1})表示考虑前(i)位时左式子大于右式的方案数。

两边相等

必定是前(i – 1)位相等,然后第(i)位相等。

(i)位相等共有两种情况:同为0和同为1。

同为0的话,相当于第(i)位需要有偶数个1;同为1需要第(i)位全为1且(n)为奇数。共(f = [ ext{n is odd}] + sum_{k} [ ext{k is even}]C_n^k)种方案。

然后就有(dp_{i, 0} = dp_{i – 1, 0} imes f)

左大于右

(i – 1)位相等且第(i)位左大与右或者前(i-1)位大且第(i)位随意。

(i)位左大于右当且仅当(n)为偶数且全为1。

然后就有(dp_{i, 1} = dp_{i – 1, 0} [ ext{n is even}] + dp_{i-1,1} imes 2^k)

最后

(ans = dp_{n, 0} + dp_{n, 1})

D. Ezzat and Grid

考虑动态规划+线段树。

首先,记(dp_{i, j})为考虑前(i)行,第(i)行通过第(j)列和之前的列保持满足条件,最多能保留几行。那么就有

[dp_{i, j} =
left{
egin{aligned}
& 1 + max_{a_{i-1, j} = 1}(dp_{i – 1, j}) & a_{i, j} = 1\
& dp_{i -1, j} & a_{i, j} = 0 \
end{aligned}
ight.
]

然后每次都只和上一行有关,所以可以滚动数组优化空间。

然后通过离散化可以把行数缩成(O(m))级别,然后一个线段树区间最大值就解决了。

由于要输出方案,所以可以加个区间置数或者以{value, index}作为线段树的元素,然后维护每一行的最优的前驱就行了。

AC代码

传送门

写在最后

补8.11 -8.13

发表评论

您的电子邮箱地址不会被公开。