WC2026 游记

前面忘了。hb 集训模拟赛打了 $200,300,0,100,115,100,226$。

试机写了 noip t4，写完 wa 了以为大家都走了，调了一会儿发现了 zyz，不调了润了。试机赛喜提 $10$ 分。

回来听说 cts 试机有交互，吓哭了。

第二天发现三个交互，吓哭了。

8:00：开始写 T1。初步思路是只能 *+ 和 *，为什么不是看一下 lcp。我草还可以 +++。

8:15：讨论几下过样例了。selfeval 怎么就 $25$ 次，写个暴力。

8:30：写完暴力测了一下 $512\times 512$，一测绷不住了，怎么是对的。交一发发现是 $84$。

8:37：猜了个结论改成了 $O(1)$，变成了 $96$。

等等，没过？？？？？

然后卡了好久常，玉玉正了。

然后看了 T2 的题意发现是连 $O(n^2)$ 条边求 $k$ 流量最小费用。发现这个沟槽的连边细节有点多，画满了一张草稿纸还没画明白。想了想发现好像任何暴力都很难写，不如直接写流子。稍微写了点代码，捏了个费用流出来，写了点暴力连边的代码，调了调把样例 $1$ 过了，然后样例 $2,3$ 完全过不去。这个时候 gzy 在后面走来走去，我也没交代码。

然后去画了一会儿 T3，想了一下一对铅笔橡皮发现不太会做。发现是不是可以做链 reverse，那也不会做啊。

然后发现两个题都不咋做得明白就去卡 T1 了。？把大小为 $2$ 的循环手动展开了，快了一点点。把两次函数调用展开了，交一发竟然过了。何意味。这时候是 10:35。想不到吧我这个时候 $96+0+0$ 还去变成 $100+0+0$ 了。

然后肯定是调 T2。画了画发现我的连边条件好像全错了。好像应该关心 $a_i\pm t_i$ 和 $b_i\pm (t_i+|a_i-b_i|)$ 的大小关系。写了写过了点我忘了多少样例，反正样例 $2$ 好像过了。11:16 交一发，$12$ 分，何意味。

发现过了若干个 $k=1$。这个时候肯定是去看流子哪里写错了，发现我写的是跑 $k$ 次 dfs(n-2,1e18)，好像应该是 dfs(n-2,1)。交上去多过了一个点，何意味。然后又瞪了一下网络流发现我好像反向边的流量也写的 -=，绷不住了。交一发，$28$ 分，还在 wa，何意味。但是三分钟改了两个错，何意味。

然后肉眼了十分钟没发现问题，玉玉正了，倒是发现样例 $6$ 能跑出来并且全 wa 了。

然后去蠕动一下 T3，目标是部分分。发现前两档竟然不需要 $k_{\min}$，原来可以用无穷对铅笔橡皮啊！想了想发现两对铅笔橡皮直接随便删边加边了，十分钟写完调了调交上去过了 $41$ 分，那就扔了。这时候是 11:45，$100+28+41=169$。现在想想已经金牌了。？

然后蠕动了一会儿，突然发现这个运算好像 $t_2=t+|a-b|$ 已经是 $2\cdot 10^9$ 了，然后他妈的又和 $b$ 做了加法，怎么你妈的爆 long long 了？？？把传参的数组改个名，重新开了 long long 的数组，在 12:09 获得了 $32$ 分？？？这个时候样例 $6$ 前两行过了，其它没过，何意味。

然后又看了十分钟发现我开了一个叫 $T$ 的 int 变量，大小是 $3\cdot 10^9$？？？改改过了样例 $6$，12:20 交一发 $56$ 分。我草，心安了。

然后想了想剩下的分有什么可做的。推了推发现这个 $a_i\le b_i$ 好像是二维偏序的形式，然后 $k=1$ 直接写了个 dp 过了。中途排序排反了（只有这一个错），还写了个拍子，花了十分钟。12:42 获得 $100+68+41=209$，心安理得上厕所去了。

回来推一下发现三个讨论全是二维偏序的形式，那我问你，是不是动态二维数点优化网络流？看一眼发现 6s，感觉差不多就这样，睡觉去了。

其实我想不到优化建图是因为 dmy 集训教会了我 bitset 优化 dfs，后面又有个卡空间题只能优化 dfs 不能优化建图，从此我忘了什么叫优化建图，脑子里只剩优化 dfs 了。哈哈哈。

出来一问感觉还行，虽然回宿舍路上问到一个比我高的。但是问到 0 个人 T1 通过，何意味。反正应该稳了。

查分，别人倒着挂，我没挂，是不是相当于我挂了一分。

我就不信没有金牌。

后来讨论了一下发现这个 t2 C 性质的思考有点误导了，还好我想的是 $k=1$，避免了误入歧途。

推荐一下思考方式：思考 $k=1$，把 Jerry 的策略变成删掉 $k-1$ 个线段然后满血通关。这样 Tom 就是要让最小割 $\ge k$ 了，那就是最大流 $\ge k$，就好了。