日记

昨天晚上去打了 div.3，然后今天看到排名：$5$ 题能排到 $1000$ 名以内。我记得上一次 VP 的 div.3 $5$ 题都排到 $3000$ 多名去了。上 clist.by 瞅了一眼 T5 的难度：1700，而且做法基本上一眼。我真厉害

祝老的练习真是卓有成效。

Empty Triangle# Link to

这就是昨天晚上的 T5。

赛时是这么想的：我先问随便问一个 1 2 3 吧。然后假设它返回的是 $i$，我们就再问一个 1 2 i。但是我们的出题人造数据肯定会想到有人会这么写于是就想把它卡掉。要不我 rand() 决定替换哪一个吧。好，开干！

然后就过了。。。

主打一个我估摸能过它就能过。但是题解用了神秘小方法证明出来这么询问在 $75$ 次以内问不出来的概率是 $1.2 \times 10^{-18}$ 以下。比买彩票还低。

[YNOI2019] 游戏# Link to

第一眼还以为是 Ynoi。。。

读完题先看一眼数据范围：$n \le 10$。应该要用高斯消元。然后苦思冥想 1h+。居然连状态怎么设都不知道。我好菜。于是去看题解。看到了状态的设法，于是就去推转移。也是成功的推出来了一半。于是又去看题解。于是便懂了。开始写代码。

该说不说这个系数的初始化是真的又臭又长。然后高斯消元还挂了，复制的之前的高斯消元代码。

[USACO24JAN] Merging Cells P# Link to

其实老早以前就瞟过一眼题解，知道怎么设状态和转移。但是不知道怎么优化。于是又去看题解。

疑似有点题解过度依赖。

并非疑似。

于是去找了几道简单（吗？）的题练手。

Aeroplane chess# Link to

简单是简单，但是我没读题。。。导致题意理解有误…

Maze# Link to

并非简单题。

首先我们就设出来 $dp_u$ 表示当前在 $u$ 还要走几步才能出去。设 $t_i = 1 - k_i - e_i$，显然有 $dp_u = k_i \times dp_1 + t_i \times (dp_{fa} + 1 + \sum\limits_{v \in son_u}(dp_v + 1)$。但是这玩意有后效性。显然不能直接 dp。我们直接想到高斯消元。

消不了一点。$O(n^3)$ 的复杂度直接让你飞起来。显然我们需要人工消元。于是题解直接把 dp 式子里的 $dp_u$ 之类的全部消完了？？！疑似有点消的太猛了。

然后我们的私人 HDU 评测机性能时好时坏。