杭电多校 2022

ShaoJia的游记

其实没有游，都在ez机房。

人生第二次打 ACM（第一次算是 THUPC 吧）。

Day1

中午去面馆吃面，会到二中已经 11:55 ，跑去机房就开始了。

一下就开了 1011 签到题，结果误以为红色是 WA，想了好久那里挂了，结果 10 分钟后有人告诉我我过了。/qd

全场就做了 1011 和 1012 两道题，成为全队最卷选手。总之把 Shaojia 和 Cxny 带飞了。

中途帮 Shaojia 调了 1007，最后竟然是因为没加 inline 而爆栈了。/qd

最后在死磕 1001，一道 KMP 毒瘤题，WA 了两发无果。

Solved 6 problems，Rank 79。

Day2

吸取 Day1 的教训，早点出去吃饭，顺便换了一家快餐店。

到场离开始还有几分钟，和 Shaojia 打了一场 Generals 2V2，成功偷家，ShaoJia 太逊了。

继续倒序开题，1012 签到题，但 INF 没开够挂了一发。

然后看 1007，题目看了半个多小时，最后 5min 写完代码切掉了。

1011 线段树，但第一次写假了，还写得很繁。最后只能再写一次，过的时候已经 14:22 了。

1005 又是线段树，死磕 Dp 式最后和 Shaojia 研究出来了，但发现前面处理区间写挂了。

最后改了半小时还是 WA。贡献 3 题结束。最后半小时 Shaojia 和 Cxny 开始 Generals，本巨佬还在调题（驱蚊器）。

Solved 8 problems，Rank 56。

Day3

Shaojia 没来，没法吊打他了。

开场傻乎乎一题都不会，Cxny 把 2 道签到题给切了。我过了好久才把 1012 这道爪巴 Dp 给过了。

然后看 1011，第一反应曼哈顿距离转切比雪夫距离，然后分四个方向讨论，前后缀 $x$ 与 $w$ 最小最大值即可。

于是开始写，但发现很难写，才写四分之一 Daniel 就过了，问了以下发现自己是傻逼，并不用转切比雪夫距离，去掉冗余状态直接二分即可，于是过了。

1002 也是萌萌题，理解题意理解错了好多次，最后才知道每个技能只能用一次，直接 二分 + 状压 Dp 即可，很快就写完了。

1001 Daniel 柿子推错了，正解好像是 cdq 分治 + 多项式（FFT）优化 Dp，不在自己能力范围之内（虽然算法都会），没切正常。

1008 三维计算几何，一开始把 plane(平面) 理解成了飞机，笑了好久。当然计算几何还是算了（尽管过了一车人）。

今天一共就过了 5 道签到题，自己做了 3 道（当然感谢 Cxny 的翻译与罚时），没有 Shaojia 的日子真舒服，abandon 后打了好久的 Generals。

Solved 5 problems，Rank 143。

Day4

Shaojia 仍然没来，不过今天在家里打，不用担心吃饭的问题。

一开始选了几道题都没咋仔细看题面，然后看 1004 一车人过了，于是去看题，手玩几组发现这不就全是 NO 吗，然后又看时限给了 8000ms，不敢交。

过了好久才去试了试，然后过了，出题人你母亲时限干啥的。

然后 1006，非常的简单，比 1004 还简单，但没判一下就上 $200$ 的情况，吃了一发罚时。

随后去看 1007，发现又是非常萌萌的题，虽然但是，还是吃了一发罚时。

随后 Cxny 把 1001 切了，是一道记忆化搜索跑区间 Dp 的题，与 CSP-S2021 的 t2 有些类似。

然后发现 1011 过的人也挺多。虽然不会证，但奶了一口直接线性基，然后过了 /qd。

1002 则是罚时聚集地，我和 Cxny 一起写，一遍最短路再一遍最长路。然后我 WA 了，Cxny TLE 了，看了看写法，我的最长路是 topo 序 Dp 的，Cxny 直接 dij 了。于是我明白了会有 $0$ 环，然后加了个 tarjan 缩点就过了。

1005 过的人很多，但我看了一眼不会，然后去看 1003。一眼就看出对前缀和差分约束。然后写挂了。查了半天发现差分约束返回无解时队列里会有东西，下一次开始又没清空 /qd。改了下过了。

然后颓了一会儿。再看 1005 发现两层合并就是矩阵乘法，而点数又很少，一口奶定是用矩阵做的。然后是个双指针类似，但矩阵除法需要求逆，步数又会很大，又不能取模，于是寄了。

然后就开始写线段树，每次线段树查询区间乘积。正确的，但是多了一只 $\log$ 被卡了。

最后才想到能在用一个指针记录一下现在处理到的位置，然后对这个 $l$ 求基于这个位置的后缀积，复杂度与双指针相同（妙啊），于是最后半小时冲过了。

今天这场写了 7 题，手感还是不错的 doge。

Solved 8 problems，Rank 65。

Day5

Shaojia 回归，但是今天的剧情加了这个傻逼怎么会这样的呢？

开场 Shaojia 切了 1002，我看了 1012。1012 手写一个堆即可，但我蜜汁写挂了。

然后愣了半天发现节点更新写错了，改了就过了。

然后我和 Cxny 看 1010。又是一道博弈论，英文太差，完全看不懂题。在 Cxny 的技术支持下，我发现答案全是 Win!，即先手询问最大的正确信息，后手必输。

但是 WA 了。愣了半天发现 $x\ge 1$。改了就过了，空吃 3 发罚时。

1007 的柿子我和 Shaojia 推了半天无果，OEIS 还是无果，Cxny OEIS 了一下就出来了。然后他把柿子给我，我写了一个 NTT 加速转移就过了。很激动，第一次做多项式题就过了。

于是去看 1002，证了一下发现这是个积性函数，可以直接 Min_25 筛。但是以前没写过，怎么办呢？贺板子。

先贺了 OI-wiki 的板子，调了半天结果 TLE 了，十分愤怒，直接弃题。

然后去看 1006，想了好久发现是一个 dp，写了一下 WA 了，看了一下发现数组清空写错了，改了下就过了。

然后又是 1002，去 loj 上找跑地最快的板子，改到结束还是 TLE，十分愤怒。

Shaojia 状态不佳啊，是不是没睡够呢，还是本来就这么菜。

Solved 5 problems，Rank 92。

Day6

我发现我每次开场总不能先蒙到水题（盲狙一直很不准

赛前吸收了肯爷爷的祝福，神清气爽。

开场 Shaojia 直接爆切 1006 和 1009，排名直接 rank 8。我被震撼到了，膜膜膜。

我看 1012，看着一个一个队过了，自己一片混乱，感觉要寄。

然后 Shaojia 让我看 1008。手玩了一会儿发现根据二进制可以推出神秘的规律（不知道叫啥，且称周期性吧）。

然后和 Shaojia 讨论了一下，打了个暴力发现是正确的，于是两人开始一起码。

码完发现样例都过不了，非常疑惑。Shaojia 一下就看出了问题，改了 1min 就过了，不愧是 Shaojia。

然后 1010 平面图转对偶图，对偶图上的最小生成树等于原图上最大生成树中没有被选的边，并查集即可，很水，1A（终于 A 题了）。

Cxny 很快就把 1012 给过了，代码很短，我们都说 Cxny 在演。

接下来 Shaojia 把 1007 自己的见解告诉我，我想了想，Shaojia 开搞。

大概是一道同余原根的题目，Shaojia 想想想推推推发现有 BSGS + exgcd 的算法，虽然能够，但是时间有点卡。

Shaojia 说他人傻常数大，太逊了,但我还是怂恿他开写。

~~随后我作弊看了 cxy 他们的代码，发现直接逆元 + unordered_map 过，时间复杂度飞快，~~Shaojia 非常尴尬，我们都嘲笑他 OvO。

随后 Shaojia 就过了 1007。

我开始和 Cxny 讨论 1011，Shaojia 切完后也参与套路。我 oeis，被 wxw 看见了，他说“他们在 O 一道题”，非常尴尬。

最后绷不住，直接看 wxw 队的代码，Shaojia 直接怂恿我抄，过不了 TLE。

回头检查一下发现他们算次是 $10^9$ 级别的，本因过不了，但是他们就蜜汁过了。

wsyear 改了一下，从枚举因数到倍数 $O(n\sqrt n\log n)\rightarrow O(n\log^2 n)$，过了。

此后又把 1002 经过几次罚时调参调过了，之前就听到 xay 说他在调参。

最后 15min 集体颓废，FFA 了 3 把，第二把碰到了 Daniel777。

Cxny 抱怨说为啥你俩讨论不带我。

最后，Shaojia：4 题，我：3 题，cxny：1 题。Cxny 太演了。

Solved 8 problems，Rank 29。

总榜排名 Rank 50，非常爽。

Day7

zhy 来了，于是我们把 zhy 一起请了过来。

开场我准备倒开，发现一道不会。过了一会儿有队过了 1008，于是前去观赏，一道很不 naive 的博弈论，过了一会儿写完提交，发现 zhy 已经 A 了，非常尴尬。

为了防止再出现多名队员重复看题的情况，我建了个 QQ 群。

随后 Shaojia 写完了 1004，但是没有过，WA 了 2 发。他让我调，我也没看出来，后来还是他自己调过了，实在太强。

然后我开始停滞，一题不会，Shaojia 写 1003 树形 dp。写完之后没有过，TLE。让我一起调。

我们都认为是 IO 问题，我还减少了取模次数，用了 buff 的 Fast IO，还是蜜汁 TLE。

于是我开始写数据生成，本地跑了一下，发现真的特别慢。然后发现一个 $tot$ 写成了 $n$，于是过了。

zhy 说只要无视罚时他就能切 1001，我说罚时不重要，于是他开切。

Cxny 从半小时前说所有人都别看 1009，给他机会切题，到如今说他寄了，开始摆烂，真是太演了。

我和 Shaojia 开始想 1006，一道稍加（绍嘉）改变的数位 dp。很显然的统计每种数个数，柿子也不难推，于是我催促 Shaojia 开始写，他说他有 $16$ 的常数，我说没事。

过了好久写完，有过了好久过样例，中间还有 UB。交了还是 WA，我写了个对拍，大数据没有问题。

后来才发现 $k=0$ 的时候会错，改了一下终于过了，很开心的 2 发罚时。

Shaojia:

正当我刚刚说的排查掉头发时，cxny 开始和同桌的 zqs 打 florr，还时不时戳我让我看游戏局面，当时我非常恼火。

最后我看 1002，发现每个三角形需要恰好选一个，又没有环，做一遍 dp 即可，第一遍用了 map TLE，改成 unordered_map 就过了。

随后 zhy 把全场不到 20 人过的 1001 给切了，写个 8 个 binary_search，太强了。

（所以 Cxny 写了歌姬吧）

Solved 6 problems，Rank 86。

总排名还上升到了 Rank 49，非常吃鲸。

Day8

开场先写了 3 道签到题（1004 1001 1008），非常的爽，抢人头，一道树形 dp 第一遍还推假了，非常傻逼。

因此 Cxny 再次被迫成为演员。

Shaojia 同时把 1011 整除分块切了，非常强，但是赛后发现这题暴力就能过，$10^7$ 级别运算量。

然后 Cxny 非常厉害地想出了 1007 的 $O(n\sqrt n)$ 解法，但是没有卡过去，我花了好些时间帮 Cxny 卡常，还是 TLE。随后 Cxny 把值域阀调小了，终于过了，可惜吃了 8 发罚时。

此时 Shaojia 在写 1005，我在看 1002。中途 Shaojia 的 1005 WA 了，还问我她有没有想错，我觉得是对的。然后 Shaojia 对拍了好久，最后还是我交过的（事实上 Shaojia 拍着去上厕所了，让后我看没问题就拿她电脑交了。

然后我把 1002 过了，听 xsc 说他们也会了，但好像没调出来？

然后我们去上课，Shaojia 在楼上继续想题 1010，他说面积与 $t$ 成二次函数关系，然后就很简单了。于是我，Shaojia 和 zhy 一起写 1010，但是我贺得板子是错的，贺了两次都是错的，Shaojia 没开 __int128，最终 zhy 第一个过，并在 16:59 帮 Shaojia 调过了，实在是太强辣！

最终我无耻地抢到了 4 道题，Shaojia 2 道，Cxny 1 道，zhy 1 道。

Solved 8 problems，Rank 50。

总排名 Rank 45，Shaojia 和 zhy 非常强。

Day9

现在已经是几个月以后了，记不太清了，大致讲讲就好。

开场先速切两道签到题，然后开始坐牢，和 Shaojia 一起想 1008，想到了容斥套容斥。

结果 Shaojia 写完锅了，才发现外层容斥有问题。于是想直接内层容斥，我算了一下发现复杂度并不会爆。

于是改 1008，Shaojia 去写 1001，他所是二进制翻转 + 排序，非常强大。

Shaojia 又把 1006 贺过了，Cxny 又非常强大的把 1003 过了。

Solved 6 problems，Rank 51。

Day10

最后一场了，开场还是签到，我 1007，Cxny 1003。

让后 xsc 发现 1001 是原题，我写了一下，直接 dinic 速过。

然后我又去把 1009 过了，非常愉悦。

Shaojia 说这段时间他都在和 zhy 讨论 1004，发现难推，写了一个暴力，然后连猜两个结论，第一个结论证出来后他直接开写，过了。

1 hour 出头过 5 题，直接 rank11，非常震撼，甚至 ez rank1 了。

然后我们推 1002，Shaojia 推柿子，我写，是一个 容斥 + 矩阵快速幂优化 dp。但是交了几发都没过。

最后发现是 Shaojia 边界的容斥推错了，多了一个 $1$。随后便过了。

然后一起想 1008，有 LCT 启发式合并 树剖 倍增四种写法，然后我写了倍增过了。常数比 wdssean 的树剖大不少。

Solved 7 problems，Rank 41。

End

终于结束了，10 场连打真的很累，总分排名 Rank 46，还是比较满意的。