「CTS 2019」氪金手游【容斥原理 + 树形 DP】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

小刘同学最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知:

  • 卡池里总共有 nn 种卡,第 ii 种卡有一个权值 WiW_i。小刘同学不知道 WiW_i 具体的值是什么,但是 WiW_i 服从一个分布。
  • 具体地,对每个 ii 有三个参数 pi,1,pi,2,pi,3p_{i, 1}, p_{i, 2}, p_{i, 3}WiW_i 将会以 pi,jp_{i, j} 的概率取值为 jj,保证和为 11

小刘每次会氪一元钱来抽一张卡,其中抽到卡 ii 的概率为:

WijWj\frac{W_i}{\sum_j W_j}

小刘会不停地抽卡,直到他手里集齐了全部 nn 种卡。抽卡结束后,记录下来了第一次得到每张卡的时间 {Ti}\{ T_i \}。有 n1n - 1 个二元组 (ui,vi)(u_i, v_i),对于任意的 ii 都必须满足 Tui<TviT_{u_i} < T_{v_i}

查看更多

「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 (("

查看更多