专栏文章

THUWC2025 游记

llsj2009Isj2OO9
生活·游记参与者 7已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@mijcnax0
此快照首次捕获于
2025/11/29 05:03
3 个月前
此快照最后确认于
2025/12/04 05:14
3 个月前
查看原文

Day 0

来的比较早，没有罚站，很快签完了到。
你说得对，但是为啥 rdfz 两顿午餐卖我 100 RMB 啊？？
第一次 ak 试机赛！
晚上挺早就睡了。

Day 1

去麦吃了早饭。
开 t1，想了一段时间二分图匹配/模拟费用流相关，想了一段时间决策单调性相关，最后发现我是啥比，1.5h 通过了。
开 t2，一眼想到了最大次大相关，想了一段时间去维护一个神秘数据结构（大概胡了一个高度为 33 的 33 叉树去解决这个东西），发现没啥道理；然后想能不能线段树分治之类的，感觉又没啥道理。
这时候大概想了这样子的一个东西：
对于一个前缀 [1,i][1,i]，我宣称一个 j≤ij\le i 是有用的，当且仅当存在三元组 (x′,y′,z′)(x',y',z') 使得其和所有 k≤ik\le i 且 wk>wjw_k>w_j 的 (x,y,z,w)k(x,y,z,w)_k 均冲突，且其和 (x,y,z,w)j(x,y,z,w)_j 不冲突。
并且很容易注意到，有用的 jj 不是很多，只有 O(1)\mathcal{O}(1) 个（应当是 ≤8\le 8 个？），下面记作 mm。
且若 jj 对于前缀 [1,i][1,i] 无用，则对于前缀 [1,k],k>i[1,k],k>i 也都无用（因为限制只会更严）。
那我就时刻维护所有有用的 jj 构成的集合，每次新加入一个 ii 暴力拍扁重构就好了，复杂度大概是 O(nm3)\mathcal{O}(nm^3) 或 O(nm4)\mathcal{O}(nm^4)，常数很小且跑不满。
乱写了一通，通过小样利一交就 800ms 通过了。
其实这个题过得还挺快的，但记不清具体时间了。
然后开 t3，发现我怎么只会第一个包啊？？冷静了一下，手摸了 k→k−1k\to k-1 的影响，发现 [ansk−1>ansk][ans_{k-1}>ans_k] 这个东西有单调性，好的我会 O(qnlog⁡n)\mathcal{O}(qn\log{n}) 了，先写了一下拿下 2424 分。
又去把 t4 2020 分写了，想用 long double 把 3030 冲过去，但好像并不可能。
继续回来分析 t3，想了一下发现我要是能求出 kk 后面算贡献乱分讨一下就做完了，但我求 kk 怎么只会单次 nlog⁡nn\log{n} 啊？？
想了一堆可能很有道理的东西，但写了一个我觉得没啥道理的 O(n)\mathcal{O}(n) 求 kk 的东西（伏笔），把 3636 分过了，继续尝试分析无果。
最终 100+100+36+20=256100+100+36+20=256，是不是这个分还可以来着。
出来问了几个人发现没有比我高的。
xhgua xuzishuai 和一堆人的 t2 8nlog⁡n8n\log{n} 做法全部被卡常了，what can i say。
下午 合照 & 嘉年华 都在罚站。
伏笔：在 Day 2 颁完奖后 xhgua 跟我说 kk 差不多是个最大子段和，冷静思考了一下：我那个 O(n)\mathcal{O}(n) 代码写的咋是 max⁡1≤i≤n(prei−min⁡j≥iprej)\max\limits_{1\le i\le n}(pre_i-\min\limits_{j\ge i} pre_j) 啊？？我咋没看出来这个是最大子段和啊？？
不过感觉当时看出来也没时间了，最后那个 3636 分代码差不多也是最后 1010 分钟交的了。

Day 2

又去麦吃了早饭。
开场发现工程题又是 AI 相关/tuu
不是哥们，怎么函数式交互并且还没有下发样例的，这是肉眼静态查错顶针大赛吗？？？
迅速通过了 t1，t2 二维矩阵转一维比较魔怔，挂了一发。
一开始没看懂 t3 在说啥，交了几分获得 00 分。
这时候去看 t4 然后把他过了，再回头看 t3 突然看懂了也过了。
然后做 t5，CE 了几发然后过了。
这时候可能 2h 不到一点。然后看 t6 没看懂在说啥，这时候记错时间以为只有 1h 了，不过后来监考人报时发现看记时间了/hsh
t6 仍然看得云里雾里，又过了 30min 终于捋顺了，写了 30min 写完了，CE 了若干发在大概还剩 40min 多一点时终于获得了非 CE 的成绩，获得了 8.?8.? 分。
然后随机调参，获得过 3.?,6.?,8.?,9.?,20.?,28.?3.?,6.?,8.?,9.?,20.?,28.?，最终没调出来，获得了 28.?28.?。
最终 100+100+100+100+100+28.?+0100+100+100+100+100+28.?+0。
两天总分是 256+528.?256+528.?。
出来遇到 xhgua ak 了，其余人都是 500+a(a<10)500+a(a<10)。
遇到教练，教练说现在改为一二等合并作金牌，三等作银牌。
然后就 Au 了，看起来报名字的时候是按成绩降序报的，我似乎是金牌第二组靠前的，加上卓越奖 2020 个应当 ≤40\le 40 名？
xhgua 似乎是 2929 名。
感觉最后那个 t6 调出来就有卓越了啊，有点可惜。
其余人都是 Ag 了。

评论

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

正在加载评论...