%你赛二三事 - 洛谷保存站

## 模拟赛

### 赛时

看到 $\text{T3}$ 是概率 $\text{dp}$ 就先做了 $\text{T3}$. 写了 $\text{30min}$，弄了个 $n \times n \times 2n\ (n = 200)$ 的三维 $\text{dp}$ 数组，甚至觉得没啥问题，随便拍了拍把精度问题解决后就去看 $\text{T1}$ 了.

$\text{T1}$ 还挺好写的，玩了一下样例，发现若新加的边 $e = (u, v)$ 中的 $u$ 与 $v$ 连通，则可以令答案的指数自增一，记其为 $k$，则答案为 $2^k - 1$. 但正确性实在证不了，不过这个性质看着就很对，拿并查集记了一下连通情况，后来对拍结果出来了感觉相当对，于是自信爆棚去了第一趟厕所.

回来之后又拍了拍 $\text{T1}$，感觉挺无懈可击的就打算开 $\text{T2}$ 了，但是比赛页面崩了，就口胡了一下正确性的证明，后来 $\text{one}$ 给我们又给我们搞了个网址.（不过原网址能用之后还是回原网址了）

不知道啥时候突然想到 $\text{T3}$ 没开快读，后来去开了一下，其实没啥用.
 
$\text{T2}$ 就很令人难绷了. 一道很基础的树形 $\text{dp}$ 写了我 $\text{1h}$. 但其实这里面应该有 $\text{10min}$ 是在卫生间里待的...

本来懒得写对拍了，结果突然看到有个地方计算过程中没取模，当场就怕了. 改完写了一下对拍发现好像就错了这一处. 不过也是安心搞 $\text{T4}$ 了.

$\text{T4}$ 在比赛刚开始的时候就感觉没怎么读懂题，不过部分分给的很慷慨，貌似能骗到 $\text{80pts}$. 把 $n = 1$ 和 $k = 1$ 的拿到手后给 $n \leq 50$ 的打了个暴力，但是貌似时间不太够（$\text{11:58}$ 才交）也没查，最后拿了 $\text{60pts}$ 滚粗.

总分是 $100 + 100 + 90 + 60 = 350$.

---

### 一些难绷的事

xiao_beng 说他要爆零了，然后赛后站了一个 $\text{rk2}$ 拿了 $\text{300pts}$.

niu_zh 大爷说他要听天由命了，于是拿到了 $\text{T4}$ 的惟一 $AC$.

Potata 在写 $\text{T2}$ 的时候试图用 $\text{int}$ 存概率 $p$，在样例输出 $0$ 后恍然大悟（？

> $\text{NineOne outputed 100 examples of problems}$
> 
> 译：91 输出了 100 道题的样例

---

### 赛后

niu_zh 彻底怒了，他的 $\text{T1}$ 被卡了输入，$\text{T3}$ 因为用了 $\text{long double}$ 出现了大量不知名错误.

貌似很多人都被 $\text{T1}$ 卡了输入.

Potata 的 $\text{T3}$ 因为没开滚动数组把内存炸了，拿到了 $\text{133168KB > 131072KB}$ 的好成绩，你也快来试试吧.

貌似切掉 $\text{T3}$ 的两人都没滚动且规模与 Potata 一样为 $n^3$.

zzx99 把模数 $10^9 + 9$ 当 $10^9 + 7$ 写，导致在 $\text{T1}$ 挂了 $\text{70pts}$.

---

### 讲题

$\text{T1}$ 的证明请机房数学神犇讲了一下，感觉听不太懂.

niu_zh 大爷给了一个十分权威的证明：`这不是显然的吗？`

$\text{T2}$ 有一个带逆元的做法，机房数学神犇再次上台，讲了一下关于费马小定理的证明，不过讲了半个小时感觉在讲滚木（niu_zh 言），有人发表暴论：

> 原本会的不听；原本不会的听不懂；原本会的听完感觉云里雾里；原本不会的仍听不懂.

后来怂恿 xiao_beng 上台讲了不需要逆元的做法，感觉比带逆元的更显然...

$\text{T3}$ 因为挂了 $\text{10pts}$ 所以大概讲了下开头（把动规的状态、初值还有答案讲了），后来 zhou 回来了就把转移丢给他讲了，然后 lzy 竟然来了，给回答了俩问题. 我上去把转移的顺序结了一下就去撤硕了.

niu_zh 大爷讲的 $\text{T4}$，他做了一个 $\text{hack}$ 好像把题解区大部分代码（包括他自己的）都 $\text{hack}$ 掉了，那题是 $80\%$ 的水数据 $+$ $20\%$ 的均匀（随机生成）数据，所以大部分乱搞做法都能水过.

最后 lzy 讲了一下正解，确实有难度.

---

### 总结

$\text{T2}$ 梦游太久了，不然应该能把 $\text{T4}$ 搞出来.

$\text{T3}$ 太难绷了，一个 $200^3 \times 2$ 的 $\text{double}$ 还不滚动，活该 $\text{MLE}$，能拿 $\text{90pts}$ 也是猎奇.

$\text{T1}$ 说明数学这边还要练练，其实是可以证的，但是赛时只会口胡了.

$\text{T4}$ 也搞的挺烂，应该能拿下 $\text{80pts}$，但是暴力部分挂了，痛失 $\text{20pts}$

---

### 闲话

比赛的时候诗兴大发去了三趟厕所，第二次还看到 $\text{teacherone}$ 了。。。

正在渲染内容...