做题笔记 2023.2 Part 2
March 3, 2023 •
Comment
Solution. 取石子游戏
February 9, 2023 •
Comment
Description
$n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子，颜色为 $c_i$。A 和 B 轮流行动，A 先手，每人有两种操作：
- 选择一堆石子并从中取出任意个石子。
- 选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。
不能不取。不能操作的人失败。
做题笔记 2023.2
February 2, 2023 •
Comment
CF808G Anthem of Berland
数据范围明示 dp。首先在模式串上跑 kmp，预处理失配指针，dp 时遇到问号就暴力枚举字符集中每个字母，复杂度为 $O(|\Sigma|\cdot|S|\cdot|T|)$，可以卡过。
Solution. CF1025G Company Acquisitions
January 31, 2023 •
Comment
Description
有 $n$ 个结点，每个结点有两种状态：active 和 acquired。
一个 active 结点后面跟着若干 acquired 结点。
对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。
每次随机选择两个 active 结点，随机让其中一个收购另一个。
求只剩一个 active 结点的期望步数。
$n\le 500$
Solution. LG6054 开门大吉 / 切糕模型
January 18, 2023 •
Comment
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$