(THU+1)WC 游记

lichenghan · 2025-01-31 07:17:04 · 生活·游记

寄了。寄了。寄了。

THU day -1

到达北京。

中午和教练、同学们聚餐，晚上在酒店睡觉。

买了一些生活用品，发现多买一点东西可以省运费，于是买了一些零食 XD。

THU day 0

教练上午貌似出去玩了。我在酒店睡觉。

下午 14:00 签到。

签到按姓名首字母分两队。但是这个 A-P 队怎么这么长？？？

排了不知道多久（>2h）的队，签到成功。紧急前往试机。

机器是 Windows 下的 NOI Linux 虚拟机？？

所幸电脑性能足够，卡顿比较小。

测了一下，本地暴力计算 (3\times 10^8)! 需要 1.6s，评测机算 (1\times 10^8)! 需要大约 1s。属于是经典土豆评测机了。

由于几乎一直宅在酒店，晚上根本不饿。楼下便利店买了两个饭团解决晚饭。

THU day 1

快进到开考。

看了下 T1。发现所有上升或下降的情况都是可构造的，然后变成了经典的线段树优化 DP。

迅速开写，但是突然急需上厕所。我并未在上厕所前阅读 T2，但是在厕所想到了 T1 更好写的构造。问题不大。

回来接着写，由于线段树没 build 调了约 10 分钟（

50min 签上到了。

开 T2。感觉这个题似曾相识？

• 我会树套树套树！O(n\log^3 n)，显然过不去。
• 我会容斥！可以先二分答案，然后容斥，拿个 unordered_map 计数。O(n\log w)，带 8 倍常数，还要 unordered_map，感觉常数飞起来了。先放放。
• 我会 CDQ 分治！将左侧按 w 从大到小排序，然后逐个插入，判断每个点能否覆盖一些新的点，以维护一个“支配集”。判定我写的 O(|S|^3)，|S| 是支配集大小，复杂度 O(n\log n |S|^3)。感性上 |S| = O(1)，而且 |S|^3 感觉卡不满。可以接受。开写！

（1h later）被卡常了？？？

貌似 O(|S|^3) 有点太极端了。随机情况下能卡到数百的样子。

• 我会分块！把序列分成 B 个块，整块内排序算出上面的支配集，零散块暴力查。时间复杂度是 O(n(\log n-\log B) + n^2B^{-1} +nB|S| + n|S|^3)。B 取 \sqrt {n|S|^{-1}} 时达到 O(n\sqrt {n|S|}+n|S|^3)。

（20min later）更慢了？？？

现在时间瓶颈到了 O(n^2B^{-1} +nB|S|) 这个部分。随机情况下 |S| 可以轻松卡到 5 左右。

考虑 分散层叠状物 在要检查的支配集总大小多于 C 的时候 O(C(\log C+|S|^3)) 重算支配集？

复杂度改成 O(n(\log n-\log B) + n^2B^{-1}+{\color{red}nC}+n|S|^3 +C(\log C+|S|^3)B|S|C^{-1})。

等下？B 好像不用根号平衡了？？B=n,C=|S| 时复杂度为 O(n|S|^4)？？？

这个过去了，难绷。但是这个线性解在 n=5\times 10^5 时跑了 440ms。

剩了大约 2.5h。紧急开始暴力。

T3 直接枚举 k 模拟 5 分，T4 指数级暴力 10 分。

T4 好像可以 O(n^3) DP，常数还很小？预期 45 分，开写！

高精度调不出来。浪费 30min。然后发现高精度运算常数过大，过不去 n=10^3。30 分遗憾离场。

看看 T3 吧。猜测答案关于 k 是单峰的？

暴力拍了几组，感觉没问题。冲刺 m=1！

写完了……诶？这个题我的总分怎么只有 19？

每题得分取所有提交总分的最大值（而非子任务的最大值之和）

晕。紧急拼包。

本地测小样例错了。流汗。

12:58 提交终稿。13:02 完成评测。拿到 24 分。

pretest 得分 100+100+24+30=254。

大合影。在风中站了 15min。好像会 T3 了。生气。

与同学交流，T2 那个容斥解也过不去。

rdfz 的饭堂好吃。但是队伍和签到一样长。

下午学科嘉年华没去，在酒店睡觉。

THU day 2

今年的工程题是手搓 AI，有 7 个 subtask。

sub 1-4 简单模拟签到。

sub 5 开始长篇论文阅读理解。晕。

由于认为 low_freq_wavelen < high_freq_wavelen 调了半天。还有若干小错。

进入 sub6。

写了大概一个小时，4kb 的代码。进入漫长的调试。

点名批评出题人，不给样例，不给本地交互库，所有调试只能通过提交进行。提交返回的结果只有与答案的误差。

大概瞄了一眼 sub7，是把前面的所有东西拼起来。还有一个 0 分的 sub8 教你如何在本地玩你写出来的东西。

在比赛结束前三分钟发现分组注意力部分理解错了。紧急更改，但在改完前打铃了。

最终得分 (100\times 5) + 8.64+0=508.64。

与同学交流，发现 sub6 直接返回全 0 的得分恰为 8.64。生气了。

不想排大长队，中饭再次前往便利店。

本来下午想在酒店睡觉的，但是家长说还是去一下颁奖比较好。

今年的一二等约合并为金牌，另颁发卓越奖 20 个。我获得金牌，没有卓越。

我出来之后遇到了 251Sec，与他进行了亲切的交流。他获得了卓越奖，但是 day1 的得分比我低。我们 day1 t2 貌似是一个做法。

晚上再次与教练和伙伴们聚餐，收拾行李。

中转日 1.16

上午前往绍兴，下午清空了脏衣服库，晚上参加了 zxx 家长群的聚餐。

由于教练买的机票不包含行李托运，我的 19.2\text{kg} 的箱子收了 475 元。愤怒。

几位上午去杭州玩的同学（OtomachiUna、Dairuichen007、Daniel_lele、Ray1）当日走了近 4\times10^4 步。害怕。

报道日至疏散日 1.17 - 1.24

待更新。