做题笔记 2023.10
October 12, 2023 •
Comment
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$
Solution. CF802N&O April Fools' Problem
November 25, 2022 •
Comment
Description
两个长度为 $n$ 的序列 $a_{1\dots n}$ 和 $b_{1\dots n}$，选择 $i_{1\dots k}$ 和 $j_{1\dots k}$，使得 $i_p\le j_p$，最小化 $\sum (a_{i_p}+b_{j_p})$。
Medium $1\le k\le n\le 2200$ 4s
Hard $1\le k\le n\le 500000$ 10s
做题笔记 since 2022.4.4
April 14, 2022 •
Comment