THUWC 2019 & WC 2019

THUWC 2019 & WC 2019。

（不要问我为什么有一本约还来 TWC 我也不知道怎么回事想必今年一定是达不到分数线的甚至进不了面试。。。）

被学考折腾了一周，已经不会写代码了。。。

Day $-O(1)$

官方钦点有一道角点检测。。。

Jan. 21st - Day 1

去学校报到，去早了，被挡在门外。

然后签到的时候被告知 Out of Competition 选手啥东西都没有。。。

过了很久搞到了寝室，中间试了个机，OJ 土豆了。。。

下午成功爆炸。。。

开题看 T1，把期望搞掉，然后强上分块 $q \sqrt n$，写一发，很快过样例，然后交上去 MLE。。。

强行卡成 int，不 M 了，但是它 T 了。。。

分析了一波，根据缓存调整块大小把它卡了过去，最后一个 subtask 本机 5s，卡不过。

T2，T3 一开始有点凌乱，认真分析了一波，发现 T2 就是个细节题，T3 第一眼没有思路，然后就开始搞 T2，大概还有 2.5 h。

写了一个多小时，调了一下，然后交了一发，只过了一个点的 60 分。

然后就自闭了。。。。

一个多小时强行续到 30 min，终于发现一个 bug，交上去，终于有 60 了。。。（还过了 Subtask1?）

然后就继续自闭到 end 了。。。

一直以为莫队 $q \sqrt q$ 的，其实是 $n \sqrt q$ 的。然后许多人 T3 高分。。。凉了，还是我菜。。。

Jan. 22nd - Day 2

彻底凉了。

T1 又是 ryz 的签到题。一个 bug 调了半小时。。。

然后看到了 T2 32，T3 51。1h 打完。

然后分数就没有增加了。。。

试图搞 T2，没想乱搞，然后思路局限在动态剖分类似的东西，成功自闭。。。

最后 30min 发现 T3 $n \le 50$ 可做，来不及写了。。。

再次沦为暴力选手。。。

角点检测场。

拿到题面一看，八合一。。。

前两个点出师不利，写得有点慢，T2 被 bitset 坑死，然后跑得贼慢。。。然后神奇地在系统找到了crc32 这个程序。。。

然后是 png 输入输出。看材料看了好久，材料的组织结构好混乱。。。找个东西的定义得花半天。然后再疯狂 getchar 后写完了读入。

然后输出更复杂，还得把两个校验码拖过来，一开始用 string 搞，然后编译的时候告诉我说和 unsigned char 不兼容？？！手动改成指针，然后调了半年，校验码校验区域找了好久。。。

最后还剩 20 min，火速 rush 了 T5（输入输出复制了好久）, 然后样例输出文件总是读不出来，但是测试点的输出能读出来，然后赶紧交了上去。然后比赛结束。后来感觉好像是文件流混用的锅。。。（和求 crc 的文件流重了）

感觉这场完全就是手速场。（XJ 大众水平 4 题，zrf 6 题）感觉对 C++ 熟悉一点能写的快一点（至少可以避免 CE 带来的返工），似乎合理运用 python / 系统库 也能稍微快一点。命题形式感觉还是有点问题，至少对于大部分选手似乎只能完成前 4 个点造轮子的任务。

一直以为出题人会 3h 一道角点检测，结果搞出 8 in 1，有点没想到。。。

Jan. 23rd - Day 3

上午讲题，发现自己 zz 了。D1T3 容斥之后按照套路转成背包，然后需要处理一些细节（仅计算第一次贡献和不同权值的合并）。D2T3 就是考场上想到的 70 分 DP，然后加些前缀和优化。

D2T2 根本没有想到询问是个可重集。然后利用设计重心的一些小性质设计权值搞。

下午又是介绍贵系，又鬼畜了一波弹幕。然后听说北大发一二三等奖，然后就开始打听细节。过了很久之后，终于开始发约，也是一二三等奖，据说分别对应最优惠（原来的一本），省队最优惠，“再来一瓶”。今年高二收获颇丰，xtr, jxc, zzf, zkc 和 xjz 都有一等奖，高一的 zzd 和 xza 也是一等奖，Congratulations。感觉和前两次发的约不是一个数量级的。。。

一个小总结：感觉还是开题顺序有点小问题，D1 对自己码力过分自信，然后死刚 T2；D2 又被计算几何吓怕，反而去搞性质完全没有分析清楚的 T2。也许因为 Unrated，才敢这么玩，正式比赛怎么搞绝对要滚粗了。。。
感觉这场比赛 Medium 居多，然后感觉搞这种题还是有点带不上劲。

题意简述：

D1T1：给出 $n$ 封信，有类型 $a_i$，有 $m$ 个信箱，类型为 $b_i$，区间询问 $c, d, e, f$ 表示将 $[c, d]$ 中的信随机投入 $[e, f]$ 的信箱中，每个信箱只放一封信，求期望有几封信放在了与其类型相同的信箱。 $n, q \le 10^5$ 或 $n \le 50000, q \le 10^6$。
D1T2：给出 $r \times c$ 的网格图，每行每列可以运行一种火车，搭乘一列火车需要一定代价；某些城市有机场，搭乘飞机有固定的代价。有若干个限制，为在一定的前缀时间内，某个点所在行列的火车无法运行，或某个机场无法使用。$q$ 组询问，询问两点间何时连通，以及连通时两点间最短路。$r, c \le 10^5, q \le 10^6$。
D1T3：定义一个操作 $(l, r, v)(1 \le v \le n)$ 表示对 $i \in [l, r]$ 执行 $a_i = \min(a_i, v)$，定义操作序列合法当且仅当依次进行每个操作能够将序列 $A$ 变成序列 $B$，且其所有前缀均不合法。求长度 $\le m$ 的序列数。$n \le 100, m \le 10^9$。
D2T1：给出一棵树，每条边有边权 $(a_i, b_i)$，每个点有点权 $(c_i, d_i)$，从 $i$ 点出发，经过 $j$ 这条边的代价为 $\min(a_j + c_i, b_j + d_i)$，求两两点间代价和。$n \le 5 \times 10^5$。
D2T2：交互题，给出两种询问，询问一个可重集 $S$，对于 $x \in [1, n]，\sum_{i \in S} \text{dis}(x, i)$ 的最小值以及一个可行的 $x$。要求还原树结构。$n \le 4000$，两种询问不超过 $3999, 3997$ 或 $100000, 0$。
D2T3：给出 $n$ 个点，求其形成的所有严格凸包（无三点共线）面积的平均值和方差。$n \le 400$。

Jan. 24th - NOIWC Day 0

早上搬了个寝室，去签了个到（顺便在签到墙上写了 wzz 厉害，然后发现忘写 yzyyylx 了，中午吃饭的时候补了一个。。。）。

晚上开营仪式。

欧盟已经不是那样的英国了（ccf 还是那样的 ccf）
WC 是性价比（价性比）最高的竞赛。
今年有一道传统题、一道提答，和一道交互（三个愿望一次满足）
各种暗示。

Jan. 25th - Day 1

上午松松松来讲评测系统推销评测鸭。理论相对基础，讲了许多故事（再次回到缓存优化。。。各种后台事故，各种神仙选手），再次吐槽土豆 OJ。评测鸭十几分钟成功刷了二十几页评测（一个上午刷了 50 多页）。。。成功抢到小黄鸭。LCA 和松两个毒瘤友好交流。

下午 picks 讲量子计算。几乎一点背景知识都没有，前面还可以处于“离线和在线的叠加态”，后面突然离线。。。

Jan. 26th - Day 2

上午首先是具体数学。连具体数学都没有的我自然是听不懂的，旁边学了半学期具体数学的 zrf 一直在吐槽他讲的内容。

接下来是字符串高级内容选讲。似乎对于这类 technique 并不熟悉（似乎是集训队的基础内容），不久也陷入掉线。

下午松松松也来听课了，就坐在我旁边。给我们看各种不可描述的神奇的东西（新一批鸭子们 are underway），还一起参与讨论。

（松：2 亿 4s 肯定跑不过。讲题人：这个轻松跑过。）

先是 IOI 选讲。我是 9 月 IOI 结束做的题（贺的题解），现在回顾一下，（说实话有些题确实很 NB）。

接下来是 ACM 中国区域赛的好题选讲。前面的题还正常，后面时间有点赶，有点来不及理解。当时在 CF 看这些题的时候觉得可以一做，现在感觉下来确实有许多好题。

（我发现我这两天每天背着电脑跑来跑去，电脑最大的作用是一个移动电源。。。）

（大家去食堂的速度越来越快了。。。）

晚上营员交流。LCA 的连续段之前 zzf 说过，前两天想 EC-Final 的 B 的时候也稍微思考了一下。所以前半段至少没掉线。

接下来的 string 内容几乎全员掉线，（三小时的内容强行在 30 min 讲完。。。）samjia 的图染色有点复杂，也没听懂。最后的【可追溯化数据结构】感受了一下它是个啥玩意，（似乎）听懂了前面半段。。。

Jan. 27th - Day 3

上午是“模拟费用流问题”，也就是 UER8 的 B 题及其扩展。其本质就是加速增广。主要是利用了权值的特殊性所产生的不交叉情况，根据这个确定增广方式。在 UER 题前面的东西大多还能听懂（发现好多细节都忘了差不多了）。后面再次开始赶课件。

下午是 IOI Day 2 以及各国 OI 题选讲。IOI Day2 T1 T2 还能回忆得起来，T3 一点印象都没了。。。（LCA 的 $O(n)$ 再次掉线）

接下来一些题讲得也稍微有点赶，根本来不及理解。（俄罗斯的题不像日本的，相对就有点朴实。。。）

下午松松松一直在搞他新送到的鸭子，发出奇怪的响声（有灵魂的鸭子。。。），组织大家按秩序领取。吃晚饭的时候松又没饭票来蹭饭，于是提出了【用鸭子换饭票】的理论。。。和松友好交流评测鸭的故事。。。

晚上试机前和松谈论奇奇怪怪的东西。

试机没啥东西，除了电脑突然死机，在松的建议下和维护人员投诉，获得了加时让我直接强行重启。随便写了点东西，就回寝室了。（听说集训队机房停电了？）

（T2 （CTSC D2T3）题面中的“妹子”变成了 Yazid。。。）

Jan. 28th - Day 4

上午是来自 zzt 的（困难）数论算法选讲。除了几句话以外，基本处于掉线状态。

下午先咕了半个小时，然后开始图的计数。首先是多项式理论，还比较轻松。然后是图论相关生成函数的应用，前面几道题还行，后面几道题就不知道在讲什么了。。。（但是总体来说似乎是掉线率第二低的课？）

（似乎大家冬眠都醒了，开始疯狂鼓掌。。。）

晚餐和松聊起了以前的 OI 和一些历史。

晚上是激动人心的【指令集优化】，掌声不断，也了解到一些从未涉猎到的卡常方式（虽然正式赛不能用。。。）

接着是另一个经典问题——【编译原理】，讲了许多原理性的东西，感觉不是很好懂。。。

然后是关于类欧的一个另类解读——【万能欧几里得】，似乎这个维护 01 串的 idea 很妙，不知道实际好不好搞。。。

Jan. 29th - Day 5 (Contest Day)

又爆零了。。。

（CCF 日常出锅，比赛推迟 15 分钟）

题面好长呀。。。

花了好久才看完题面，T1 （神奇）计数，T2 造分布式计算机，T3 （神奇）交互。

T1、T3 都没啥思路，先搞 T2。

操作贼多（好像大多都没啥卵用。。。），居然不给评分参数。。。先写 Subtask 1，然后调了好久（似乎是因为 checker 输出和题面描述不一致。。。）。然后看了看 Subtask2，发现 2 个寄存器求不了斐波那契，然后想着打表，感觉 $\log n$ 打表有点难写，先写了个 $O(n)$。然后盯了半天调试信息，不知道它怎么跑出来的。。。过了很久，发了个 announcement：T2 checker 正在修锅。

先去看 T3，感觉只返回小于等于有点难搞，似乎不能直接判定，甚至 $n \le 5$ 都没有什么好搞的方法。。。过了很久，一边想 T3，一边等 T2 的 checker。。。然后发现 $n \le 5$ 只会暴力搜索询问方式。。（和我搬的一套模拟赛一样。。。）

然后 T2 checker 修好，调过 Subtask2。顺便写了 T1 一些分（28 + 8）。然后开始码 T3 搜索。还有 1.5 h。

回来写 T1 搜索，以及 T2 的第三个点。还有 1h。

然后魔改了最短路，加了点随机化，第四个点搞出了 15 cycles。然后让它一直跑，最后跑到了 11。

第 5 个点似乎也可以这么搞，写了一发，然后跑不出来，感觉死锁了，就没管它。

然后回头赶了第二个点的二分。。。然后就没多少时间了。。。

感觉全世界都会 T3，T2 subtask 2 居然可以 goto 变量？

讲道理今天前场游戏体验真的很差，（特别是做非传统题的，）听说集训队考场锅更大。真是继承了 CCF 去年的传统。。。

下午成绩又咕了。（从 3 点咕到 4 点咕到 4 点 45。。。）

松松松考试结束开始发鸭子器官，在等成绩的时候开始用器官表演简单的乐曲。。。校园内充斥着鸭子的声音。（有点吵？）

集训队成绩先出。zzy 169, fls 150 多，似乎十五人队很稳？听说 T2 Subtask 2 只测了 $k = 0$，似乎要重测？

然后开始复评，48 + 52 + 31 = 131，T2 Subtask2 FST 成零分。不知道哪里写挂了，正式评测用 spj 没有任何提示，然后我又跑了遍调试用 checker，输出一点问题也没有，问了下松，他把出题人给拉了过来，然后他也不知道什么情况，我又测了一下 $O(n)$ 的东西，然后和其他同学一样 A 了。这时重新下发了 T2 spj，然后发现两个 spj 跑出来结果不同？？？赶紧去找出题人，然后在后台（和一些人一起）搞了好久，最后 zgg 的回复是会统一处理。然后群里又吵翻了。。。赶紧去听讲题。

因为已经到饭点了，然后讲题非常仓促。。。

现在是 19:49。讲题结束后大家一直惦记着文艺汇演，但是似乎没有官方回应。。。19:20 群里提出要自己办文艺汇演，19:30 我们闻讯赶来时已经完成很多协调工作了，19:40 就已经敲定了，开始各项准备工作了。好强的行动力！

晚会着实精彩。个人觉得最出彩的便是相声。融合了 OI 界许多老梗（CCF 的连坐与扣省队，CTSC 单人房，丢程序考 Day3，OI 动物园，“无私的奉献”，以及许多小梗），情景叠加也非常自然，成为全场一大高潮。

除此之外是经典的填词环节，依然是来自大连 24 中的作品，还有来自南宁二中的作品，带来十分强烈的共鸣。《我的一个 OIer 朋友》的 Review 也超赞，虽是一年前的填词，却依然动人。

另外还有许多 dalao 上台献唱（以及跳舞），虽不及专业水准，却展现了 OI 选手文体两开花的综合素质。

（当然某些节目放上来着实不妥，我也不想多说什么了。。。除此之外，）文艺汇演还是那么 fantastic，毕竟是一年一度的联欢。又是一年奇迹般的起死回生。。。

Jan. 30th - Day 6

社会活动前往广东珂科学中心。

相比科技馆里有什么大家都清楚，但是我深深感到了自己物理要凉，已经啥都看不懂了。。。

（又是一天辛苦的跑腿。。。）

接着是闭幕式。

性价比 $\times 2$。
金牌还是在强省，但是令人欣喜的，在银牌中也有像广西、新疆、黑龙江的弱省。

祝贺 fls、zzy 进十五人队！

似乎全体重测了？再次踩线 Au。。。jxc rk4！被一片人吊打。。。感觉无缘 ZJ 省队

该你了
不忘初心（地收钱）
灯光暗点（道出了所有人的想法）
杜老师，你的钱挣得还不够多
以赛养赛
（居然网上的传言是真的）真的是收费的问题。NOI 不会不搞。该干什么干什么。

Jan. 31st - Day 7 - 总结与随想

又一年的 WC 结束了，似乎离我退役也不远了，CCF 还是那么地出锅。似乎整场 WC 从讲课到比赛到汇演全员出锅。OI 似乎变得十分 fragile，一点风吹草动都牵动着大家。。。

然而这次体验依然 memorable，和志同道合的 OIer 们，一起自闭，一起复读，一起咕咕咕和被咕，一起享受禁竞赛……一段欢乐的旅途。

从技术层面来说，万年踩线 Au 的事实似乎无法掩盖，暴力选手的标签也不是说没就没的。NOIP 季的一切说明不了什么，接下来的省选才是真正的关键。以现在的水平进队还有点困难，要么靠提高实力，要么靠乱搞 RP，哪个靠谱一目了然。

整个旅途中都没有到广州市区，似乎也没有真正感受“食在广州”，确实有些遗憾。广二十分大，（逛一圈要十分钟）。关于伙食，有些人觉得一般，我并没有感觉（也许是自己学校食堂吃多的原因）。

— 完结撒花 —