MENU

Category: 题解

2023 笔记

Catalan 数

Catalan 数表示为 $C_n$,有通项 $C_n=\dfrac{\binom{2n}{n}}{n+1}$ 和递推式 $C_n=\sum_{i=1}^nC_{i-1}C_{n-i}$,定义应该使用的是递推式。

Read More

Solution. 取石子游戏

Description

$n$ 堆石子,第 $i$ 堆有 $a_i$ 个石子,颜色为 $c_i$。A 和 B 轮流行动,A 先手,每人有两种操作:

  • 选择一堆石子并从中取出任意个石子。
  • 选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。

不能不取。不能操作的人失败。

Read More

Solution. CF1025G Company Acquisitions

Description

有 $n$ 个结点,每个结点有两种状态:active 和 acquired。

一个 active 结点后面跟着若干 acquired 结点。

对于两个 active 结点 $A,B$,如果 $A$ 收购 $B$,那么所有跟着 $B$ 的结点变为 active,$B$ 变为 acquired 并跟在 $A$ 后面。

每次随机选择两个 active 结点,随机让其中一个收购另一个。

求只剩一个 active 结点的期望步数。

$n\le 500$

Read More

Solution. LG6054 开门大吉 / 切糕模型

Description

$n$ 位选手参加比赛,共有 $m$ 套题,每套题包含 $p$ 个题目,第 $i$ 位选手答对第 $j$ 套题中第 $k$ 道的概率为 $f_{i,j,k}$。

每位选手选择一套题按顺序依次作答。若一位选手答对第 $i$ 题,会额外得到 $c_i$ 元奖励,注意每位选手只有答对了上一道题才会继续作答。

有 $y$ 条形如「第 $i$ 位选手的套题编号必须至少比第 $j$ 位的大 $k$」的限制。

给每一位选手分配一套题(不同选手可以相同),使所有人的期望奖励和最小,你需要求出这个最小值。

$1\le n,m,p\le 80,0\le y\le 10^3$

Read More

Solution. CF1768F Wonderful Jump

Description

给定序列 $a_1,a_2,\dots,a_n$。

每次操作可以从 $i$ 跳到 $j$,费用为 $\min\{a_i,a_{i+1},\dots,a_j\}\times (j-i)^2$。

对于每个 $k,1\le k\le n$,求出从 $1$ 到达 $k$ 的最小费用。

Read More

Solution. Good Bye 2022

这一场题目难度应该还是挺高的,而且细节很多,一共交了五发 unsuccessful submission,尤其是在 C 上浪费了很多时间,感觉这场 C 应该放在 D 后面比较合理,当然 C 如果思路正确做起来也很快,思维难度很难衡量。

Read More