THUWC2024游记
Iceturky
·
·
个人记录
久违的一篇游记
Day -2
whk期末考，历史凭借最后一天晚上翻了翻书抱佛脚，试卷也没怎么考没看过的部分。
数学没有答案出错，化学错了一个傻逼选择，物理错了一个多选（是道好题）
Day -1
临时学了学Linux，找到学长教了一下用g++编译。
没有找到历年真题。
想要补儒略日但刚写完40分机房就要关了，就润了。
摆。
总力战没凹出来暴击，太傻逼了，以后再也不凹一档了。
Day 0
上午 4:40 起床坐车去jn坐飞机。
飞机起飞。
看了南家三姐妹，好看。
飞机降落。
之前没坐过（小时候坐过一次但忘了所以就当时没坐过）
然后坐30分钟的地铁（虽然是在机场向下走了3个很长的扶梯，但是地铁还是一会在地下一会在空中，貌似高度并没有发生多大变化。
whk成绩出了，凭借最后一周拿了6a1c，道法最后没时间背了，摆了。
数学抄错一道计算题，又扣了4分过程分，精准的卡到了a+线下。
语文作文跑题了，只有33.5，竟然拿a了（
化学后面扣了一车分，没细看。
拿着行李吃了午饭。
吃了过桥抄手，有厚厚的香香的油碟，很好吃。
然后拖着行李去巴蜀报道。
地下运动场f22。
地下运动场一股消毒水味，好像旁边有游泳池。
熟悉了一下系统，还是有比较亲民的图形化界面的。比noi linux好用。
做完a+b推了一会t2没想出来。
t2题意为构造一个n*m棋盘状态，下满棋子且无连续k个子。（k子棋）
只想出来一部分情况怎么做。
结果因为一直在想t2没有看t3。
听到随时可以离场就溜了。
听别人在说t3很水。
lxn说里面很冷要买暖宝宝给我贴但没有感觉多冷。
然后搬着行李箱走4个台阶。
一里半山路。
最难蚌的是其中有一个过马路的地下通道，马路一边是两边往下走的楼梯，另一边是往上走的几级台阶。
酒店在地下，而且房间一开始在中间，没有太阳光。
后来换了一个虽然在地下但是能照到太阳光的房间。
从窗户往下看甚至还有25米左右才到底。重庆，很神奇吧
晚上吃的很好。3块钱一大碗的碗豆汤很好喝。
买到了3.6一长条的士力架，非常好。
看到了几个单方面（基本上）认识的dalao，这么菜没人找我面QAQ
家长和lxn去长江边走路，我润回了酒店。
江边直线距离150m，实际路线1.7km。
睡觉。
Day 1
酒店停电了。
洗不了脸。手机只有70%电量。
打灯摸黑出门。
早餐吃了豌杂面，感觉不是很合口味。
外面天还是黑的。
在自己包上写了Iceturky。
入场。
有点冷，幸亏贴了暖宝宝。
发密码条。
先写了缺省源，花了10分钟左右。
开题，被t1难到了。
题意是给定 \{a_{m,n}\} 和 \{c_m\} ，让你从 [1,m] 中选择子集 S，设 b_i=max_{j \in S}a_{j,i} ，求 \sum b-\sum_{i\in S} c_i 最大值。
n\leq 15,m\leq 3000,1\leq a_{i,j},c_i\leq 100
很多一般的背包状态都会有后效性。
想不出来。
开t2，一眼不会。
开t3，一眼不会。
开t4，一眼不会。
回t1。
想了半天想到一个暴力dp。
设 f_{T} ，T 代表选择的集合 S 中已经确定的 b 数组有哪些，f_T 存储 \sum b-\sum c 的最小值。
需要一层枚举当前的数字 [1,m] ，一层子集枚举贡献到哪些位置上。
可以过 n\leq 10,m\leq 3000 的数据。
对于 n\leq 15,m\leq3000,a_{i,j}=1 或 50 则普通的状压背包即可完成。
这样就拿到了 90 分。
这个时候开考70分钟，吃了一口士力架。
开t2。
想了一会会了。
题意是给定一个环形序列，每次操作等概率随机选择一个区间，将其中元素等概率随机打乱。
求 m 次操作后每一个位置的期望值。
n\leq 1.3e5,m\leq10^9
对了半天单次操作每一个位置对当前位置的贡献。发现是自己位置最高，向两边递减且两侧对称的一个东西。
但是发现可以直接 $n^2$ 枚举所有区间所以就懒得找规律了。
每次对每个区间区间加。用差分维护一下。
37分到手。
差不多130分钟。士力架吃完了，掰了一块三角形的里面有坚果的巧克力，好吃捏。
开t3，神秘交互。
有一个01矩阵 $\{a_{n,m}\}$ ，每次可以询问一个子矩阵内是否有1。
~~哪里有1~~
查找两坐标和最大的1。
根据查询次数和每次查询的矩阵长的和来给分。
子任务1 $n,m=2$ 直接讨论。
子任务2 $n=1,m=4096$ 倍增。
一开始写的二分子任务2只得了16分。
两个子任务写完拿了24分。
感觉剩下的不是很可写。不写了。
大概3小时了。每人发了一包切片面包，没吃。
又回t2看 $1e9$ 怎么做。
想了一会发现是矩阵。
可以做 $n\leq 128$ 。
写完调了一会，t2 70分了。
然后发现这个矩阵一直都是循环的。
也就是说在乘的时候只需要把第一行求出来。
这样就从立方降成了平方。
这样的话就可以开 2e3*2e3 的数组，但是vscode抽风了不让我开，与ulimit大战10分钟最终以失败告终。
时间一直都没卡过去。
$2048^2\times \log_2{10^9}$ 。
两秒没跑过去。
卡了好久的常。没卡过去。byd。
被卡掉了20分。/fn
还差55分钟结束。上厕所，发现了一个难蚌的东西。
我的机位旁边墙上画着科比。名字下面写着已故美国篮球运动员。旁边还有个人简介。
在黑曼巴精神的照耀下。
（甚至今天是科比坠机日
回来10分钟敲完了t4 15分。
t4题意是有一个矩阵，两种操作，第一种是在一行上选择一个区间赋为1，第二种是查询从一个位置到另一个位置所走的路线（上下左右）上的格子右侧1最少的格子的1的数量。
$n\leq 1e5,m\leq 10^9,q\leq 3\times 10^5$，赋值操作在 $10^5$ 次以内。
直接 spfa 求点权最小最大。做了$n,m\leq 100,q\leq 300$ 。
感觉其他部分分也都还能做做，但剩下的时间好像不够做了。
到现在已经199分了。
看了一圈放弃t2卡常，看看t3的子任务3能不能多少拿点分。
然后想了一个分块查询，从右下角依次查询 $16\times 16$ 的矩阵。
斜着查，有1就进去一个一个查。
所在斜行有矩阵有1的话就不查下一斜行了。（这里应该也要查，下下行就不用查了，考场上没想到）
然后喜提34分。
非常好。
然后试了试 $32 \times 32$ 和 $64 \times 64$ ，都是36分。
t3在最后关头的骗分骗到了比前面部分分还要高的分（
最终战果 90+70+60+15=235 ，好像不低。
UPD：这个好像是pretest，不是很懂。
出来吃饭，坐对面的[dalao](https://www.luogu.com.cn/user/597798)打了刚好200分，t3 97分，使用的方法是每次找矩形中点，右下角矩形有就递归右下角，没有就两侧。
看起来很容易hack，但97分。很厉害。
ioi赛制，很神奇吧。
图书馆里的书不少。有空调非常好。
去拍照，人挤人，架子上站了4排，地上也有两排。
后面的哥们一直在召唤古神，难绷。
报告没讲啥学科内容，前面是宣传和文艺演出，后面是人工智能科普讲座。
中午没睡觉，睡了十几分钟。
晚上直接在巴蜀吃的饭。
然后很早就回酒店了。
巴蜀校内最外面的一条道好像是对外开放的，看到了好多周围居民走在这条路上。
学校三周都是山，很奇妙的氛围。
但是学生数量好像不是很多，不知道是不是在其他校区或者放假了之类。
现在看一中人好多，地方好大啊（
去长江边走了走，江面太宽了，有一种摇摇欲坠的感觉，然后又在~~虹龙洞~~洪崖洞旁边爬了好长时间的楼梯，累死了。
买了一杯bug牌的柠檬茶，希望明天少出bug。
## Day 2
早上起来后发现身份证消失了，找了好长时间，最终放弃。
吃了重庆小面。lxn给我打印了纸质的身份证。
进考场之后发现身份证在键盘下面。
发下密码条之后打不开设备，等了好长时间。
然后缺省源（虽然没啥用）。
开题，先读了pdf，没看懂。
题目倒是简单易懂，就是四子棋，扣去棋盘上的一个格子，每次只能下在每一列最下面的能下的格子中。
让你实现一个函数来做决策。
然后写了一个傻傻的往8个方向搜索，按照3个，2个，1个的优先级来填。
按理说应该往下搜几层，毕竟棋盘只有 $12\times 12$ ，但是写寄了。
写完第一个测试集竟然得了90分，第二个80，第三个40。
后来又交了几发，都没超过这个分数。
后来写了一些改进，比如思考下完这个位置之后对方能不能直接4子之类，但是没得更多的分数。
最后在后面的几个数据集也都交了一边，没评出来。
比赛现状。
评测大体类似一个交互，但是每次询问的返回时间限制是3秒，总共可能询问70次。
导致跑得很慢。
最后半小时更是直接封榜看不到结果。（因为跑不出来
最后调了几发没调出来。
荣获210分+蓝的pending（最后评测机卡了，pending的字样直接消失了，绷）
中午饭里有一堆黄豆，难吃。
肠粉好吃。
听到旁边身上挂着一堆原神徽章的老哥向他自己学校的人大声宣称自己D2拿了420分。
很厉害。
碰到了He_Ren，狠狠的膜了。
下午wy学长讲了自己的学习，比赛，工作生涯。
感觉好厉害。
关键词：人工智能，强化学习，ICPC，墙，原神。
感觉世界好大。
然后颁奖，拿到了一等。非常好。
感觉自己分数并不算特别高，但是拿一等了，非常开心。
但是晚上还有课和ABC，于是就去吃了跷脚牛肉。
好吃。
然后发现还有「脑花烧豆腐」这样的神奇妙妙菜品，就要了一份。
但是有些辣再加上只有自己一个人吃所以没吃完。
然后就回酒店了。
值得一提的是，9:25才想起来晚上有ABC然后火速看了D做了E没写完F。
EF都好水，水到了一定地步了。
D题都比这两道题难。
（然后赛后尝试写D没调出来，怎么回事呢
------
CQ的物价给我留下了很好的印象，大部分的物品跟WF这个三线小城市一样贵或贵不了多少，还有一些比WF的物品价格便宜。很厉害。
但是路太难走了。