HBCPC2024 VP记

· · 个人记录

第一次VP ACM比赛，还是机房四个人一块打的，感觉非常有意思，以后可能会常打，写个游记。

起因非常突然，前几天某学长建议打 ACM ，ReTF 就突然建议晚上7点到10点VP一场，于是就和 zzzyyyyhhhhh,xtzqhy,ReTF 一起VP了HBCPC。

第一次打没什么经验，四个人同时使用一台机子，也没有什么策略。考前讨论了半天开题顺序，最后还是先开了A题……

A

先开 A 题。全英文题面，但不得不说 ReTF 是英语高手，我还没读完题他就已经切穿了。所幸A是签到，遂被 ReTF 两分钟切掉了,少输出一个数吃了一发罚时。

洛谷评价为橙题。

开完 A 后先看了 B，被 ReTF 评价为计算几何，于是去看别的题了。

E

发现 zzzyyyyhhhhh 好像见过 E ，于是让他写。他说是题解通道没关导致交了几千篇题解的抽象题，他也交过一篇题解。于是 6min 切掉了E

无罚时，洛谷评价为红题。

然后发现考前的策略全都没用，只要看榜上哪个题被过掉了即可……

B

接着想 B ，发现是海伦公式直接做，于是 xtzqhy 开始写写写。

16min写完，然后WA on Test 2……

于是他们三个开始调题，此时发现有人过了J，于是我开始想J了。

发现没判三点共线！草了，改完之后仍然WA on test 2。

J

就在调不出来 B 的时候，我大胆猜想，小心不求证，感觉结论就是平均值。于是我要求观察样例，但是样例是分数取模后的，连jb都看不出来。

此时 ReTF 感觉我猜的结论是对的，于是开写，发现真对了，在22min一遍过掉！

L

此时发现有人过了 L 并且我们调不出 B ，于是开 L 题。又一次， ReTF 在我没读完题时会了，真是强大。于是 ReTF 又开写了。

草！又是 WA on test2！难绷了……

ReTF 写的是分讨，但是一开始好像漏掉了亿点情况。这时候古希腊掌管 hack 的神 zzzyyyyhhhhh 发力了，接连 hack 掉 ReTF 好几次，但仍然 WA on test2。

ReTF: 这可能从 A 走到它的最小质因数，也可能走到 B 的最小质因数，也可能走到 2 ，也可能直接走到 B……。

我：不如对于这五个点的完全图跑最短路吧。

说完我们都绷不住了，感觉非常唐氏，遂拒绝了这个做法并接着调分讨。

于是经过5发罚时之后， ReTF 接近破防了。

他真开始写最短路了，并轻松过掉了……

绷不住了。

56min时拿下了，8发罚时，洛谷评价为黄题。

B

接着调 B 。

发现是精度问题，改为 long double 并改了 eps 之后直接过了……

64min时切掉，三发罚时，洛谷不予评价。

发现 G H 是 Genshin Impact 题目，并且都有人过掉，于是开 G H。

G

模拟围棋吃子，ReTF 表示不想写，感觉是大模拟，先放了。

H

ReTF 读完题后直接开始爆搜，此时我发现 D 是决策单调性，但是不会算贡献，于是三个人开始讨论。

91min，ReTF 两发罚时后与 zzzyyyyhhhhh xtzqhy 讨论，再次切掉，不得不拜谢了。

洛谷评价为绿题。

D

ReTF 想了想 D 之后，有了类似莫队的双指针的做法，一个小时这个大工程感觉调不出来，于是口胡了之后弃掉。

洛谷评价为紫题

G

ReTF 最终还是开始写大模拟了。

遂在 2h 1min 1发罚时过掉。

洛谷评价为绿题。

此时我们的排名早已来到了前 50！但是似乎做了错误的决策，没有先开简单的 I 题，而是一部分人想 F ，一部分人想 K 。

如果能再次拿下一个题，那么感觉 Au 就稳了。冲！

K

他们想 F ，我想 K 题。

发现关键的是系数。

有了一个 dp ，形如：

f_{i,j}=\frac{i-\frac{1}{2}}{i+j}\times f_{i-1,j}+\frac{j-\frac{1}{2}}{i+j}\times f_{i,j-1}

完全不会维护，于是去询问大家，未果。

但是！此时古希腊掌管斜率优化的神 xtzqhy 指出，不妨将 i+j 挪到左边，就有点像斜率优化的式子了。

挪过去了之后仍然不会，于是开始手算系数。

于是开始瞪眼观察。

花了10min 手推了系数三角，感觉是个类似杨辉三角的东西，但完全找不到规律，或者说规律太多了，五行根本推不出来。

想啊想，让 ReTF 尝试用程序打表，我继续观察。

几分钟之后， ReTF 打出了表，我还是没有结果。一看，啊？和我手算的不一样？完啦！

但是当时我还是坚信我算的是对的，于是又想了一会，此时只剩下 20min 了。

急急急急急！

再次回去审视 dp 式子。

挪过去 (i+j) 没用，那么挪过去 (i+j)! 呢？

卧槽，好像非常有用！

因为 f 数组的下标和与阶乘的下标和是一样的！

原式子变成了这样：

(i+j)!f_{i,j}=(i-\frac{1}{2})(i+j-1)!f_{i-1,j}+(j-\frac{1}{2})(i+j-1)!f_{i,j-1}

设 F_{i,j}=(i+j)!f_{i,j} ，原式为：

F_{i,j}=(i-\frac{1}{2})F_{i-1,j}+(j-\frac{1}{2})F_{i,j-1}

边界情况为 F_{0,0}=1。

那么从头开始转移，相当于一个网格图上从 (0,0) 走到 (i,j) 的位置，向上走权值 \times (i-\frac{1}{2}) ，向左走权值 \times (j-\frac{1}{2}) ,初始权值为 1 ，求走到终点的所有路径权值和。

那么推一推式子，最后长这样：

F_{i,j}=\prod_{k=1}^{i}(k-\frac{1}{2})\prod_{k=1}^{j}(k-\frac{1}{2})C_{i+j}^{i}

那么每一项的系数就容易求的，答案也容易求了。

把这个东西抛给 ReTF 之后，只剩下 10min 了。

ReTF：你确定这是对的吗？

说实话，当时我不敢确定，但是最终大家还是相信了我。我把思路讲给 ReTF 之后，在 2h49min的时候切掉了。（因为各种原因，比赛是7点20开始，我们十点下课）。

极限！

最后大家又胡了几个题之后走了。

走的时候是 rk22，最后五个小时比赛结束时是 rk53。

总结

打爽了。

被 ReTF 带飞了。

感觉到了团队协作的力量，大家都发挥了各种作用，如果自己打显然是坚持不下来的。