THUWC2024 游记
Lucky_Xiang
·
·
生活·游记
Day -10
可能是我太菜了，只拿到了 THUWC 的门票。
Day 0
到达重庆！拿完通行证、纪念品开始试机，距离试机结束还有 40 分钟。速通，启动！
T1
link
为了充分熟悉规则，我在 AC 这道题后开始调戏 OJ。交了几发错误代码后，发现了几个性质：
- subtask 捆绑。
- 题目得分取
提交的最高分。（更正：各 subtask 在所有提交中的最高分之和）
- pretest 很水，
我开 short 都 100 分。
调戏完了以后开始看 T2。
T2
link
构造题。当时时间不够了，我先打了个部分分，就去测 T3 交互题了。测完 T3 只剩 20 分钟了，于是再回头看这道题。
我很快找到了构造方法，开始折磨的调试环节。怎么调不出来呢？怎么一直 WA 呢？直到试机结束还没有调出来。
赛后复盘：输出写反了。
T3
link
打了个暴力，就回去打 T2 了。
Day 1
T1
给定序列 a_{i,j} 和 c_i(i\in[1,m],j\in[1,n])，试选择一个集合 S，使得 (\sum_{j=1}^n\max_{x\in S}a_{x,j})-(\sum_{x\in S}c_x) 最大。
莫名其妙的题。先开始感觉没思路，打了打暴力，发现暴力可以被剪枝成正解，就喜提 100 分。
好像还有人 $O(nm2^n)$ 过了。听说正解是 $O(m2^n+3^n)$。
补充：稍微证了一下，发现我的做法确实是 $O(m2^n+3^n)$ 的。~~难得写一次正解。~~
### T2
> 给定一个长度为 $n$ 序列 $a$（下标从 $0$ 开始），每次随机选择 $p\in[0,n),l\in[1,n]$，并将 $a_{p\bmod n},a_{(p+1)\bmod n}\dots a_{(p+l-1)\bmod n}$ 随机打乱，求执行 $m$ 次操作后序列每一项的期望。
>
>$n\le131072,m\le10^9$。
>
>部分分：$n\le128$。
>
>特殊性质：$n\le2048,m=1$。
我先打了 T3、T4 的暴力再看的 T2。转移矩阵真难写，调了我一个多小时，喜提 70 分。~~听说打表能有 90 分。~~
### T3
>交互题。有一个 $n\times m$ 的 $01$ 矩阵 $A$，保证一定有 $1$。你不知道它的结构。你每次可以询问它的一个**子矩阵**中是否包含 $1$。你需要找到最大的 $i+j$ 满足 $A_{i,j}=1$。
>
>设你询问的矩阵大小依次为 $R_1\times C_1,R_2\times C_2,\dots R_k\times C_k$，计 $S=\sum_{i=1}^k\max(R_i,C_i)$。题目将按照 $k$ 和 $S$ 两个标准单独计分并累加，$k$ 和 $S$ 越小分数越高。
>
>subtask 1（4 points）：$n=2,m=2$，满分标准 $k\le 2,S\le3$。
>
>subtask 2（20 points）：$n=1,m=4096$，满分标准 $k\le 12,S\le4096$。
>
>subtask 3（76 points）：$n=4096,m=4096$，满分标准忘了。
我先打的暴力能拿 39 分，~~不会真的有烧杯不会做 subtask 1 吧~~。做完 T2 后再回头看，突然会做 subtask 1 了，变成 40 分。subtask 3 由暴力改成了分治，可惜只有 53 分，怎么卡都不能上升了。
~~听说大把的人写 90 多分的错解，希望他们 FST。~~
补充：按照出题人赛后的态度，应该是没有卡。~~太难受了。~~
### T4
> 有一个 $n\times m$ 的 $01$ 矩阵，初始全为 $0$。你需要维护两种操作（操作数为 $q$）：
>
>1. 将 $(x,y_1)\sim(x,y_2)$ 的格子全部变成 $1$。
>2. 询问从 $(x_1,y_1)$ 到达 $(x_2,y_2)$ 的所有路径中**安全值**的最大值。
>
>**安全值**：当格子 $(x,y)\sim(x,y+c)$ 全部是 $1$ 且 $c$ 最大时，格子 $(x,y)$ 的安全值为 $c$。特别的，当 $(x,y)$ 为 $0$ 时其**安全值**为 $-1$。一条路径的**安全值**为其经过所有节点的安全值**最小值**。
>
> $n,q\le10^5,m\le10^9$。
不会。打了个暴力 15 分走人。
----------
pretest：$100+70+53+15=238$。
真是菜死了。
## Day 2
>有一个 $n\times m(n,m\in[9,13])$ 的棋盘，其中有一格不能落子。双方轮流下棋，率先连成四颗子的人获胜。但是，每个人下出的子必须贴在棋盘底部，也就是说它正下方的**所有位置**必须是棋子或障碍格，不能有空位。
>
>请你编写一个下棋的程序，要求**每一步**运算时间不超过 3 秒。出题人有 50 个有强度梯度的程序，其中 25 个发给选手本地测试，25 个作为后台评测。你的程序将与每个程序对战两次（交换先后手），每次战胜得 10 分，平局得 5 分，共 500 分。
等我研究清楚怎么过编，已经过去 1.5h 了。写了个简单的代码，能够吊打 `2.so`，但是被 `4.so` 吊打。充分发挥人类智慧和暴搜技术，打 `4.so` 的胜率成功提升到了 $4\%$。于是不断调参、加随机化，还是打不过。已经过去 3h 了，迫不得已交了一发，拿了 50 分。剩下的时间加入了各种乱搞，分数就等不到了。
赛后直接心态炸了，听说直接交出题人给的 native sample 都能有 90 分，而别人写的爆搜能拿 140 分。还听说有人拿 `4.so` 跟 `6.so` 对战，结果 `4.so` 胜率 $100\%$，~~真是有梯度啊~~。据说真的有人实现了 ppt 里的蒙特卡洛算法，拿了 340 分。真的是输麻了。
三等奖，没脸见人了。