专栏文章

(THU+1)WC 游记

llichenghan
生活·游记参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mijcnr7r
此快照首次捕获于
2025/11/29 05:03
3 个月前
此快照最后确认于
2025/12/04 02:56
3 个月前
查看原文
寄了。寄了。寄了。

THU day -1

到达北京。
中午和教练、同学们聚餐，晚上在酒店睡觉。
买了一些生活用品，发现多买一点东西可以省运费，于是买了一些零食 XD。

THU day 0

教练上午貌似出去玩了。我在酒店睡觉。
下午 14:00 签到。
签到按姓名首字母分两队。但是这个 A-P 队怎么这么长？？？
排了不知道多久（>2h）的队，签到成功。紧急前往试机。
机器是 Windows 下的 NOI Linux 虚拟机？？
所幸电脑性能足够，卡顿比较小。
测了一下，本地暴力计算 (3×108)!(3\times 10^8)! 需要 1.6s1.6s，评测机算 (1×108)!(1\times 10^8)! 需要大约 1s1s。属于是经典土豆评测机了。
由于几乎一直宅在酒店，晚上根本不饿。楼下便利店买了两个饭团解决晚饭。

THU day 1

快进到开考。
看了下 T1。发现所有上升或下降的情况都是可构造的，然后变成了经典的线段树优化 DP。
迅速开写，但是突然急需上厕所。我并未在上厕所前阅读 T2，但是在厕所想到了 T1 更好写的构造。问题不大。
回来接着写，由于线段树没 build 调了约 10 分钟（
50min 签上到了。
开 T2。感觉这个题似曾相识？
  • 我会树套树套树！O(nlog⁡3n)O(n\log^3 n)，显然过不去。
  • 我会容斥！可以先二分答案，然后容斥，拿个 unordered_map 计数。O(nlog⁡w)O(n\log w)，带 88 倍常数，还要 unordered_map，感觉常数飞起来了。先放放。
  • 我会 CDQ 分治！将左侧按 ww 从大到小排序，然后逐个插入，判断每个点能否覆盖一些新的点，以维护一个“支配集”。判定我写的 O(∣S∣3)O(|S|^3)，∣S∣|S| 是支配集大小，复杂度 O(nlog⁡n∣S∣3)O(n\log n |S|^3)。感性上 ∣S∣=O(1)|S| = O(1)，而且 ∣S∣3|S|^3 感觉卡不满。可以接受。开写！
（1h later）被卡常了？？？
貌似 O(∣S∣3)O(|S|^3) 有点太极端了。随机情况下能卡到数百的样子。
  • 我会分块！把序列分成 BB 个块，整块内排序算出上面的支配集，零散块暴力查。时间复杂度是 O(n(log⁡n−log⁡B)+n2B−1+nB∣S∣+n∣S∣3)O(n(\log n-\log B) + n^2B^{-1} +nB|S| + n|S|^3)。BB 取 n∣S∣−1\sqrt {n|S|^{-1}} 时达到 O(nn∣S∣+n∣S∣3)O(n\sqrt {n|S|}+n|S|^3)。
（20min later）更慢了？？？
现在时间瓶颈到了 O(n2B−1+nB∣S∣)O(n^2B^{-1} +nB|S|) 这个部分。随机情况下 ∣S∣|S| 可以轻松卡到 55 左右。
考虑 分散层叠状物 在要检查的支配集总大小多于 CC 的时候 O(C(log⁡C+∣S∣3))O(C(\log C+|S|^3)) 重算支配集？
复杂度改成 O(n(log⁡n−log⁡B)+n2B−1+nC+n∣S∣3+C(log⁡C+∣S∣3)B∣S∣C−1)O(n(\log n-\log B) + n^2B^{-1}+{\color{red}nC}+n|S|^3 +C(\log C+|S|^3)B|S|C^{-1})。
等下？BB 好像不用根号平衡了？？B=n,C=∣S∣B=n,C=|S| 时复杂度为 O(n∣S∣4)O(n|S|^4)？？？
这个过去了，难绷。但是这个线性解在 n=5×105n=5\times 10^5 时跑了 440ms。
剩了大约 2.5h。紧急开始暴力。
T3 直接枚举 kk 模拟 55 分，T4 指数级暴力 1010 分。
T4 好像可以 O(n3)O(n^3) DP，常数还很小？预期 4545 分，开写！
高精度调不出来。浪费 30min。然后发现高精度运算常数过大，过不去 n=103n=10^3。3030 分遗憾离场。
看看 T3 吧。猜测答案关于 kk 是单峰的？
暴力拍了几组，感觉没问题。冲刺 m=1m=1！
写完了……诶？这个题我的总分怎么只有 1919？
每题得分取所有提交总分的最大值（而非子任务的最大值之和）
晕。紧急拼包。
本地测小样例错了。流汗。
12:58 提交终稿。13:02 完成评测。拿到 2424 分。
pretest 得分 100+100+24+30=254100+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×5)+8.64+0=508.64(100\times 5) + 8.64+0=508.64。
与同学交流，发现 sub6 直接返回全 00 的得分恰为 8.648.64。生气了。
不想排大长队，中饭再次前往便利店。
本来下午想在酒店睡觉的，但是家长说还是去一下颁奖比较好。
今年的一二等约合并为金牌，另颁发卓越奖 20 个。我获得金牌，没有卓越。
我出来之后遇到了 251Sec，与他进行了亲切的交流。他获得了卓越奖，但是 day1 的得分比我低。我们 day1 t2 貌似是一个做法。
晚上再次与教练和伙伴们聚餐，收拾行李。

中转日 1.16

上午前往绍兴，下午清空了脏衣服库，晚上参加了 zxx 家长群的聚餐。
由于教练买的机票不包含行李托运，我的 19.2kg19.2\text{kg} 的箱子收了 475475 元。愤怒。
几位上午去杭州玩的同学（Otomachi_Una_、Dairuichen007、Daniel_lele、Ray1）当日走了近 4×1044\times10^4 步。害怕。

报道日至疏散日 1.17 - 1.24

待更新。

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...