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，就好了。