HNCPC2024 简要游记

搬运自 我的知乎回答。

队伍：长沙市一中4队。本来应该叫“你说的都队”的，队友是 Godzilla 和 includer。

省流：打得唐完了，最后总共⑧题。

首先我看到 H 题，胡了一个 f(i,j) 表示到了第 i 个字符匹配状态为 j 的方案数，没有考虑到重叠的情况，过不了第三个样例，想了想可以利用 kmp 自动机，改一改最后一个点的转移函数就好了，比较 trival。

然后 Godzilla 以迅雷不及掩耳之势看出来 I,E,C,J 四道题。我表示我还没有看到题目四道题怎么就 AC 了。Godzilla 太强了。

includer 吐槽说怎么自己分到 A,B,C,D 题目，我从题面堆中抽出了 K 题，一眼就看出来是简单最短路建模，写完之后发现又过不了样例（太菜了导致的），includer 再读题面发现可以免费走一条边，我直接上了一个分层图就好了。无伤可还行。讲个笑话：一开始 dijkstra 的时候把点编号当 dis 传到了堆里去。

includer 和 Godilla 对我的评价：xzy 写份代码这么多 bug 你是怎么在 oi 圈生存下来的。

然后 includer 表示自己会 A 了，把电脑让出来交给 includer 去写去，然后我和 Godzilla 想 D。

D 一看就是莫反题，不过是对给出的序列而不是 1\sim n 去做，结合以前的简单 trick，我们转成值域去考虑，然后发现推导非常的顺，最后会剩下来一个类似这样的东西：

根据莫比乌斯函数经典结论，就是 C(i,j) 的和，直接拆贡献，可以做 O(n\log n) 。

发现又过不了第二个样例，暴力推式子也过不了，发现少写了一个 d^2 。

枚举 T 单独将形如 iT 的 b 拎出来去做，发现 TLE 了，吃一发罚时。把 vector 换成数组就过了。

includer 继续上写 A，还没有调出来，大雾。

终于过样例了，吃了 5 发罚时。看得我心态都崩了。

帮着 includer 把判断是否在半平面内改成了向量积，然后用了几个点到直线距离公式，把所有 double 都换成了 long long，就过了。

看 F，一眼代码在求圆方树，可是后面没想出来。Godzilla 给了一个挺对的 dp 做法，但是要跑 10^8 次计算，比较不牛。所以最后就摆烂了。

考后发现 G 也是简单题，大雾。

总之感谢 Godzilla 带我（不过简单题我也会做就是了）。