THUWC 2019 游记

THUWC 2019 游记

Day 0

乘高铁至广州。一切正常。

复习了会儿费用流模板。

祈祷，能取得理想的成绩。

Day 1

       走进广二校园，试机、合影。

校园环境颇佳——大门两侧，可看见绿树成荫、听得水声潺潺；中间，则是空旷的广场，背后THUWC的横幅在阳光下格外耀眼。

不过，一心都在这对我OI生活意义非常的考试上，也就无暇顾及了呢……

       13:30，准时开考。

       Text Editor不自动缩进差评。

       看T1，开T1。抱着“打个60~70分过”的念头，推了三五分钟式子，却发现是个区间向量和点积——怕不是莫队裸题。最后一个subtask, n <= 5e4, q <= 1e6？忽而想起使用均值不等式调节分块大小即可将时间复杂度降至O(n * q^(1/2))——于是，嘴巴AC。

       20min会T1，信心满满。

时间还很充裕，先看看其他题吧——T2极长的题面令我望而生畏，倒是T3的计数，看起来更可做些。

推T3，隐隐感觉存在一个O(n^6)做法——O(n^4) DP，接着球O(n)个O(n^2)次多项式的卷积——虽不一能AC此题，不过至少能得不少部分分吧。于是，心里踏实了。

比赛已开始一个小时，细节仍未展开，便去写了T1。

1.5 h，过样例提交，TLE。

又过了约十分钟，发现了块大小可能是0后，PP(pretest passed)——幸亏是IOI赛制，不然后果不堪设想呢。

       于是便去做T3，想了近一个小时，却没发现任何可优化的地方。只好把O(n^6)微调成O(n^2 * m * (n + m))，预估分75。

       3h，T3 PP。

       觉得100无望，便暂时跳过只有10分的O(n^6)做法，去肝T2。

       这题分两个subtask——好不容易读懂了题目，便觉得60分的subtask 1比subtask 2简单得多。稍作思考，认为是重构图整体二分 + DSU，在草稿纸上构造了一波建图的方式，便开始写subtask 1的整体二分。

       4h，过样例，提交，全WA。

       发现了一个显然的错误，再交，全WA。

       仔细研究题面，忽然意识到雷雨并不会直接影响机场，修改，再交，全WA。

       有些自闭了——总觉得，以这次THUWC D1的难度，得200分才可以稳……于是，心情变得无比紧张。不停地手造数据。

直到当比赛倒计时进入30min后，程序，在手造数据上WA啦！

发现是建图方式的锅，rush一波，15min，57.6。

最后一个subtask的60%，WA？

苦苦思索，不知为何。

分数，定格在232.6 = 100 + 57.6 + 75。

T3 O(n^6)未写。

比赛结束。

赛后才得知T2 WA是数组开小的缘故——仔细算了两遍节点个数，可还是少算了2e5。

       问了问周围选手的成绩——LK 210 = 100 + 100 + 10，MYH 239.6 = 100 + 39.6 + 100（顺带结识了两位神仙）。YHT不太理想，175 = 100 + 0 + 75。

       看来比赛的确不难，题题都有人A呢。

       自己的成绩，想必虽不是特别理想，但也还行吧。

晚上切了道水题，便睡了。

Day 2

       本以为会变得很难，谁知T1还是一眼秒的题——直接线段树合并。

       有些担心n = 5e5的线段树合并不靠谱，便继续思考了一会儿，意外发现：离线 + BIT也能得到一样的时间复杂度且常数更小。

       于是写，1h PP。

       开交互题T2，想T2。

       第一眼以为是点分治，却一直没有思路。突然发现subtask 5中的询问次数是线性的，便改变思路，按层次遍历去找每个节点的parent——便会了前58分允许第二类操作的subtask 1~5。加上subtask 6的暴力，2.5h时70分到手。感觉100有些困难，便开T3。

       披着计算几何外衣的DP题？

       决定上下凸壳分别DP，O(n^4)，58。隐隐感到可以用类似斜率前缀和的方式优化，以为不可写，也就没细想。至于奇怪的subtask 3——写完DP后再说吧。

       3.5h，写好，提交，WA。

       手测找不到锅，突然发现有大样例，于是打开，WA4。

       然而怎么调都调不出来。

       4h。

       4.5h。

       4h45min。

       越来越慌，不知所措。

       绝望地，写了个暴力。发现自己球出面积零次方和没有问题，一次方和却不对。

       再想起先前自己手测的数据，尽是三角形、四边形——

       思路豁然开朗。

       4:59:30。

       发现问题所在！

       4:59:59。

       比赛结束……

       问题，竟是我用每相邻三个顶点的面积之和当成了多边形的面积。

       惋惜，悔恨，不知所措……

       问了一些人的分数。LK 180自称爆炸，YHT 100 + 100 + 64.8恐成最大赢家。

       至于两天最高分之类的，暂且没有管——毕竟，还有Day2+呢。

Day2+

       怀着满心憧憬打开了这道【学习型题目】，却立刻有了一种要凉的预感——似乎纯粹是码农题，考察点不明。

       硬着头皮看完了整篇材料（不包括References），才发现最后几个点还是有算法含量的——只是担心自己没时间写到那里。

       ——也的确没时间写到。

       看完论文，时间已过去一小时有余；而当我写完前两个送分subtask时，比赛已进行一般了。

       对比subtask 3, 4，觉得subtask 4更容易判断正确性，便开写。

       经历了各种我都不曾想到的调试，1个小时后，PP——虽无法及时提交，可既然subtask 4的内容是点阵转PNG，那么只要返回的PNG图片可以打开且不是乱码，就说明程序没锅了吧。

       剩下半小时，试图写subtask 3，以RE失败告终。

       得分100/300。

       问了下几位认识的选手以及WC群，发现大众分100。（不过大家似乎大都是subtask 1 + 2 + 3？）

       QZR 190，orz。

       题外话：建议以后的学习型题目增加考试时间或适度降低代码量——至少我认为，这题原先设定的区分目的并未达到。

Day3

       上午面试。自我介绍，顺带提了下我对THU的向往。英语短文朗读 & 翻译，猜到blockchain是区块链并凭感觉（似是而非地）译了一波。（可能是因为我初二）我并没有被问到奥数题。

       一个下午，看YHT打CS【雾】。接着就是颁奖——收到一张【一等奖】以及一份【最优惠】协议——据称这和从前的【无条件一本约】等价，不过，鉴于未来几年的自主招生政策仍是未知，我也不知道这张纸能否让我有学上【雾】。

       放松一下，准备迎接次日的NOIWC 2019。

       自此，结束了人生中第一场THUWC。

       并没有像预想中一样思绪万千。

总结

       这次THUWC，收益颇多。

       除却那张【一等约】，作为我首次参加的全国性的高端OI比赛（尽管队爷们不打），THUWC 2019本身就是一次缤纷的体验——结识LK, MYH等知名OIer；第一次在体育馆进行OI比赛；第一次与THU的老师近距离接触……无疑是我OI生活中弥足珍贵的。

       至于我的比赛情况，只能说，“说得过去，但称不上出色”。总结几点：

1. 比赛过程中并未出现致命的细节失误（如忘写文件等）；
2. 比赛策略基本无误，暴力&正解，思考&写码的时间分配基本合理。

以上，我的发挥还是比较稳定的，想必与先前对稳定性的训练及对“中国式OI题”的适应训练有关吧。

然而也有不足之处：

1. 提前几天才开始熟悉比赛环境，有些仓促；导致不会用各种自带IDE/代码编辑器不说，Text Editor也不是非常习惯，使编程速度下降。
2. 可能是前几天的题都咕着没写的缘故，写代码的一次性正确率不高，导致debug用时长、后期几乎没时间去想正解；同时，多题未能一次性PP，虽然在近似IOI赛制的THUWC中影响不大，但若是NOI赛制则可能导致崩盘。

所以说……

以后非假期拒绝各种颓，好好写题吧。（愿flag不倒，捂脸。

最后

以上就是专注毛衣为你收集整理的THUWC 2019 游记的全部内容，希望文章能够帮你解决THUWC 2019 游记所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。