THUWC2025游记

· · 生活·游记

Day 0

上午没干啥正事，溜着玩

下午去报到，排了 0x3f3f3f3 f 米的队，站了 1h+ 才报上到

试机，有试机题，一个逆天 a+b ，一个逆天构造，一个逆天交互。最后一题不会，要菜死了呜呜呜/ll

晚上颓废，做的事大概是写题，鹿，pokemon，鹿，pokemon，睡觉

Day 1

定了六点半的闹钟，起来后吃个早饭就去考场了，好像到那的时候还有 0.5h 开考。拉屎，罚坐。

开题，诶我草我怎么题没读完就有一群佬开始狂按键盘了啊/fd

先把题都读一遍，为了避免把题忘了，我把概括的题意放这。

A：有一个你自己定的排列和几个限制，每个限制形如规定一个区间递增或递减。输出一个排列使其满足尽可能多的限制。排列长度和限制数不超过 1e6

B：有一堆四元组 (x,y,z,w) ，依次插入每一个，插入一个时查询已插入的四元组中满足 x,y,z 与当前都不同的四元组 w 最大是多少，不存在输出 -1 。四元组数不超过 5e5

C：有一个操作序列和一个初始为 0 的数以及一个自己定的上限。操作有两种：

到最后还会产生这个数乘 3 的贡献。每次问一个操作序列上的区间，你要定一个上限使得贡献最大，询问间独立。序列长度，询问数不超过 5e5

D：有一个操作序列和两个常数 a,b 。 x 初始为 0 ，操作有三种：

  1. x+=a
  2. a+=b
  3. x<<=1

从操作序列中选出恰好 k 个并按照在原序列中的顺序依次执行，问 x 最大是多少，对 998244353 取模

我草 T1 怎么这么简单，差分一下拓扑序一下秒啦，gogogo

（写了一大坨）

诶要是无解输出啥， -1 还是 no solution

诶怎么没说，再把题读一遍

我草我怎么又读错题了，让你满足尽可能多的而不是必须满足全部的，无解个球

那这咋做啊还真不会啊。想了 10min- 无果，只会平方。这时距开考 0.5h+ ，果断往下做

T2 和 T3 感觉比较可做，T4 做不了一点，所以先写 T4 的暴力（

10 分还蛮好写的，交上去也对了

再看 T2 ，没咋有头猪啊我草，别寄了啊我草

考虑特殊性质， w=1 是不是简单的啊，我只需要简单容斥一下就行了。

考虑正解，我是不是开一大堆动态开点的值域线段树维护值域上的区间和，然后询问的时候把那八颗线段树放一块线段树二分出来最大权值就行了啊。时空复杂度都是单 \log

注意到空间只给了半个 G ，算一算发现好像正好过不去，没事我会位域优化，一个节点的信息只需要一个 ull ，再离散化一手把 \log V 整成 \log N 卡一卡应该正好能过，gogogo

（又写了一大坨）

因为要写支持修改和把八个线段树放一块查询最大值的神秘生物，还要用八个 map 一个数组来离散化，以及一大坨恶心的东西，码这个加上 debug 大概用了 1h

调过样例交一发，草怎么 TLE 了

感觉要卡常，我先认为我过了 T2 ，于是精神完全胜利，斗志大幅上升，于是暴炫一大口可乐，借着现在难得的高昂情绪去整 T1

很快就想到了一个和刚才不一样的思考角度，得到了一个新的平方做法。发现我们可以扫描线一手，再拿线段树优化 dp ，做到 n \log n

因为我们要有区间加区间 max 线段树，还要有 dp 有拓扑排序，代码大概有 4 个 k ，还挺长的。但主要是模板，细节不是很多， 0.5h- 就写完了，没怎么调就过了，斗志再次大幅提升

再去卡 T2 。反正最多能交 50 发，把一些地方注释了再交以确定运行时间瓶颈，结果发现我一个线段树函数也不调用就 TLE 了？

合着 5e5 我区区八倍常数的 map 一秒跑不过啊

考虑 unordered_map ，诶我怎么还要用 pair ，还要手写哈希函数，不爽

诶我，怎么还 TLE

急眼， pb_ds 里是不是有个跑的飞快的哈希来着，可惜我不会用啊

注意到我们只需要用八个哈希表，手写的话空间复杂度可以接受，考虑手写

注意到手写的话我们只能开 1e6～1e7 的模数，远小于试验次数的平方，所以我们需要拉链法无错哈希

手写一小坨哈希表，丢进 struct 里再重载一手 [] 运算符，后面就不用改了，好耶

交上去，（这时已经把线段树全注释了，只是用哈希来做 w=1 ），妈的 MLE 了！！！

写上述哈希用了 0.5h+ ，这时我已经急眼了

调小模数到 1e6+eps ，降低了空间占用，同时也降低了效率，终于通过了全部 w=1 的点

但这时哈希已经大大占用了那一点点的 1s 和 512MB ，时空间常数都很大的线段树也寄了，只好用那个 w=1 拼上一个暴力走了， 35 分遗憾离开

爷的复杂度正确的算法！！！/ll/ll/ll

有点急，斗志下降

上个厕所，回来之后暴炫 100ml 可乐，感觉心情调整过来了

接下来的时间大概就是交替搞 T2 和 T3 。先把 T3 暴力打了，然后不甘心，又回去想 T2 ，想不出卡不动又去想 T3

还剩 10min 时突然发现 T3 的所有询问保证 l=1 会做了，要写支持同时维护三个变量的区间加减，区间和，区间 min max ，线段树二分，虽然狗屎，但有高达三十多分呐

gogogo，还剩 10 min 时极限冲完

剩下 10 min 就专心喝可乐吃零食吧～

总共打了 186 分，菜死了。

中午饭学校供的自助，还挺好吃的。

下午去参观清华，参加学科嘉年华。

先有什么活动，让你做看代码猜诗句之类的抽象事，参与两个+可以领奖。可惜人太多了很难排队，到最后只赢了一个

然后去参加啥学科嘉年华，没啥意思，主要在玩手机和社交。

晚上回去，我们学校那边小学过年有啥活动，还要我讲话，有个啥视频，wyq 给我展示了一段。

（俩小学生主持人）

“对了，听说我们的学长羊叫兽同学正在清华大学参加冬令营”

“是啊，他还有些话想对我们说呢“

byd 我咋不知道我想跟他们说啥话。

wyq 给我口胡了段霸气的词，糊弄了糊弄完事了，若至学校，服气了。

看电视，睡觉。

Day 2

起床，吃饭 去考场

今天是傻逼工程题，我要来吃屎辣

开题

今年好像是要手搭大模型一部分的样子

一共七个题，满分七百，按百分比换算成满分三百算。

T1 是若至题，很快 ac 了

T2 是矩阵乘法板子，然而数据范围来到了 1024 。改改枚举顺序，卡卡常，因为担心还是过不去上了指针，交上去发现最慢的跑了 600ms ，我真棒

之后就该抽象阅读题了

冲完 T3 读 T4

逆天清华冬令营，题目里给矩阵乘法的定义，却不动声色地用矩阵转置的记号而不给定义

还有个逆天唐氏儿平时转置只会往右上角加撇，差点没想起来还能这么表示，想了好久为啥非方阵还能有 T 次方

差点暴失一博分，菜死了

T4 神秘 RE 了，调了好久无果，去写 T5

T5 调不出，红温了。但是发现我矩阵乘法是直接贺的 T2 的实现，但调用格式我写错了，可惜改完还是 WA

突然想起来我 T4 也是这么搞的，改完 T4 过了（？）

byd 调 T5 过 T4

到比赛结束也没调出来 T5 ，区区 400 分，操真的红温了

然后吃饭，听废话讲座，没错本文截止至这里全是听讲座的时候写的

颁奖，银牌，菜死了/kk

好像离金牌差不到 20 人，为什么我没调出来第二天第五题啊（大哭