日记

今天是考试 day。

我们初三 OIer 的日历已经没有周一还是周二的概念了，只有考试 day 和不考试 day。

T1 # Link to T1

没改。

细节：祝老的板书上都只写了 改第 2,3,4 题。

T2 # Link to T2

昨天，我们的祝老说：明天考概期 dp，好好复习。然后，他又说：没事，简单题。

但是一个人都没切。今天考试难度完全是反的，T4 该放 T1，T3 该放 T2…

于是我信了这道概期是简单题。于是兴致勃勃的推了 2h 的式子。不出意外的 WA 了。我刚开始还怀疑是我式子推错了，没想到我竟然难以置信的推对了。这样就只能是 dp 方程写错了。于是我的心态直接原地爆炸。

T3 # Link to T3

爆炸完了就去看 T3。也是想得到。写了一个 $O(n^2 \log n)$ 的做法。期望得分 $30 \sim 40$。实际得分 $20$。

正解实际上是和哈希。

T4 # Link to T4

真正的签到题

如果这套题按照难度排序的话，我说不定能拿一个 $130$。但是信了“没事，简单题。”这样的鬼话，导致策略出现大问题。

竞赛是自己的事情。不论是平时的练习，还是考试的策略，都得靠自己。不能信别人的“简单题”。不要在意别人的三言两语。

竞赛是自己的事情。

今天的 $3$ 到可做题都是理解起来很简单的。其中 T3，T4 也是想起来很简单的。半个下午就改完了。今天最主要的问题是策略问题。如果策略没有问题，那么期望得分应该是在 $130 \sim 150$ 之间。如果脑袋灵光，甚至可以打出 T3 正解。

竞赛是自己的事情

这篇日记在这里以上都是带点应付性质的。从这里开始就是为我自己写的了。想看我也不拦着。

[HNOI2015] 亚瑟王# Link to

这道题也是让我见识到了概期 dp 的多样性，于是我从今天晚上开始着手写我的概期 dp 学习笔记了。

考虑到每张牌对于答案的贡献是独立的，我们可以把答案拆成 $\sum_{i = 1}^{n}ans_i \times d_i$。其中 $ans_i$ 表示第 $i$ 张牌总的放出来的概率。于是这道题就转成了概率 dp 了。

我也是想得到。不过竞赛也要靠经验嘛。这次见过了下次就想得到咯。

对于第 $1$ 张牌，显然有发动概率有 $1 - (1 - p_1)^r$。对于第 $2$ 张牌，有两种：

• 当第 $1$ 张没放出来，那么发动概率就为 $1 - (1 - p_2)^r$。
• 当第 $1$ 张放出来了，那么第 $2$ 张在第 $1$ 张发动的那一轮显然发动不出来。那么发动概率就为 $1 - (1 - p_2)^{r - 1}$。

我们发现，对于一个牌发动的概率，和它排第几位有关，也和前面发动了几张牌有关。我们又发现数据范围不咋大。想到把这俩玩意放到状态里。

设 $dp_{i,j}$ 表示这是第 $i$ 张牌，在这 $r$ 轮里，排在 $i$ 前面的牌放了几张。于是我们有转移方程：

让我解释以下这个方程：

• 第一项表示第 $i$ 张发动的概率。因为如果第 $i$ 个能发动，前面有 $j - 1$ 张牌发动，那它就只有 $r - (j - 1)$ 轮能发动了。
• 第二项表示第 $i$ 张不发动的概率。和上面的一样。

我们就成功的做出了这道题。

总结：题做得不够多，没有见识过。

音乐真是治愈心神的良药啊。