「Codeforces」Educational Round 46【题解】

简要题解

A. Codehorses T-shirts

贪心,对每种长度分别考虑。

B. Light It Up

插入的位置只可能是 ai±1a_i \pm 1 (i mod 2=1)(i \text{ mod } 2 = 1),枚举即可。

C. Covered Points Count

离散化,统计每一段被覆盖的次数,把长度加到答案里。

D. Yet Another Problem On a Subsequence

f(i)f(i) 表示以 ii 结尾的子序列的个数,枚举最后一个 good array\text{good array} 转移。

查看更多

「Codeforces」Round 556 (Div.2)【题解】

简要题解

A. Stock Arbitraging

贪心,用 max{b}\max \{ b \} 来换 min{s}\min \{ s \} 或者不换。

B. Tiling Challenge

贪心,从上到下枚举中心,能填就填。

C. Prefix Sum Primes

题目大意:给你一个长度为 nn 且只包含 1122 的序列,你需要重排这个序列,使得有尽可能多的前缀和是质数,输出方案。保证 n2×105n \leqslant 2 \times 10^5

贪心,从小到大枚举质数,能选就选,先放 22 后放 11

D. Three Religions

题目大意:给你一个长度为 nn 的母串,另外还有不断变化的三个字符串 s1,s2,s3s_1, s_2, s_3。判断 s1,s2,s3s_1, s_2, s_3 是否可以表示为母串的不相交子序列,可以参考下图。有 qq 个操作,每次会在 sis_i 的末尾加上字符 cc 或者删除 sis_i 的末尾状态 (i{1,2,3})(i \in \{ 1, 2, 3 \})。保证 n105,n \leqslant 10^5, q1000q \leqslant 1000,任意时刻 s1,s2,s3250\lvert s_1 \rvert, \lvert s_2 \rvert, \lvert s_3 \rvert \leqslant 250

示意图

查看更多

「Codeforces」Educational Round 45【题解】

简要题解

A. Commentary Boxes

模拟。

B. Micro-World

贪心。

C. Bracket Sequences Concatenation Problem

题目大意:给你 nn 个括号序列 sis_i,求有多少对 (i,j)(i, j) 使得 si+sjs_i + s_j 是合法的括号序列。保证 n,si3×105n, \sum \lvert s_i \rvert \leqslant 3 \times 10^5

任意的括号序列都可以化简为如下形式 ((否则可以继续化简))

))))"+ (((("``)) \cdots ))" +\ ``(( \cdots (("

查看更多