2024 THUWC 游记

Nine_Suns · 2024-01-27 20:53:15 · 个人记录

抱着旅游的心态来的。

在车站刚好遇到 zyc，坐了一上午火车，下午到了重庆。

去巴蜀中学报道，打了试机赛，然而 T3 不会（哭）。

晚上吃重庆火锅，完全吃不了辣锅，，，

半夜发烧了，很难绷。

磕了药，打了车才到了考场，然后发现参赛证丢了，好在能补办。

一共 \rm 5h，4 题。

先开 T1，前 \rm 25min 随机枚举算法，想到了特殊性质的 \rm 13pts，接着继续按照这个思路想，差不多半个小时想到怎么写了，搞了个 O(3^nm) 的状压，改了一下优化到 O(2^nm+3^n)，交完发现只有 \rm 77pts，觉得还行，先写 T2 去了。此时大概过了 \rm 1h。

T2 是个期望推式子的题，问给定一个环形数列，求将“选择一个区间，并将其随机打乱”操作执行 m 次后每个位置的期望值，看到 \bmod 998244353 和 m\le 10^9 往多项式快速幂上面想，但推式子挺抽象，把 O(n^2m) 的 \rm 52pts 打完就润了。时间没看。

T3 交互，大意是让你猜一个 0,1 矩阵中 x+y 最大的 1 的点，每次查矩阵中是否有 1，马上想到四分树那一套东西，然而完全不会用交互库，只能自己硬测试 + 调试，好在很快调出来，直接 \rm 90pts 了！然后就没管。

T4 很复杂，看数据范围应该是个数据结构，但有 \rm 15pts 的暴力很无脑，决定最后再写。

回过头写 T1，又尝试了思考 T1 的正解，发现不会之后决定开始拼特殊性质，很快 \rm 90pts 了。

接着再看 T3，发现 \text{Sub 1,2} 的分很无脑，但竟然没全拿到？赶紧微调了一下代码，一交，\rm 97pts，好，不管了。

接着很快把 T4 的 \rm 15pts 暴力拿下，尝试推一推 T2 的式子，想写 \rm 18pts 的矩乘，最后不出意料的没推出来。

赛后跟 zyc 讨论，结果发现 T1 的正解就是 O(2^nm+3^n)！？我的代码原来是常数大 T 了，难绷。zyc 切了 3 题 orz。

发烧直接好了。

猜测今天可能是串串和数数，于是先打了板子。

结果开题，嗯？工程题！？

题目让你写一个类似下四子棋的代码，并和 50 个策略程序对抗，编号为偶数的用来自测，奇数用来评测。并且给出了关于对抗问题的背景知识的 ppt。