300iq奔北坡

由于实在想不到这次是什么记了，所以就叫 300iq 奔北坡好了。

实际上是一篇 CTS & APIO & THUSC 2019 游记。

Arrival

因为是去北京所以要二次安检，然后剪刀被收了..一开始还说我有两把剪刀，然后又过了一次安检就没有了..最后的结果是吃方便面的时候撕不开酱料包，用圆规戳开的。

车上先是在熟悉的文章、字符串和 Reverses 三道题上分别自闭，然后开始看题解，看 border 相关论文，然后就开始看 THUPC 的榜，然后不小心被 300iq 看到了 300iq_ben_bei_po。

到了之后，发现 Sooke 就比我们早到一点点——实际上比我们早一趟地铁左右。到酒店的时候办入住排队，Sooke 刚好就在我们几个人前面，然后就愉快地面基了。

下午去试机，现场写了一道我们那场 cf 的题，（证明了如果会做还是可以在场上写出来的）。

然后，从 Sooke 来试机起，简单教了一下 Sooke 用 noilinux，一起吃了晚饭，一起走回酒店，然后发现 Sooke 房间就在我隔壁，然后 Sooke 就待在我房间里了，准备看我打他验的那场 cf。

之前 THUWC 的时候试机坐 pr 右边的右边，这次又是来的时间差不多 + 住隔壁..比较神奇。

晚上智商比较掉线（可能和前一天没睡好略有关系），掉了波分。

CTS Day 1

咕了 5min（为什么 cf 每次都是 35 开始）

开考前就注意到 T1 12s，原来是 10 组数据…（ctr：我本机 1.Xs，评测姬 6.Xs，怎么办啊）

第一眼就觉得 T1 的暴力好像不太会做，阶乘会挂。

然后去看 T2，3min 想到三方做法，然后又花了 3min 去掉一维，然后 10min 左右写 + 调完了 48 分。

T3 是个提答，（可能是雅礼集训那道五子棋的原因），我就直接搞了个估价函数，每次枚举所有可能的位置，选估价函数最大的那个。前三个点都是立刻出结果，第二个点只有 9 分，然后就把后面的点挂着跑。发现第四个点非常特殊，所以就数了一下每种块各有几个，然后直接在草稿纸上算出方案，然后若干个 for 循环输出。

然后，本来以为 T2 $m=0, 1, 2$ 的几个点要大力数据分治，然后发现如果 $n\ge d+2m-1$ 直接输出 $d^n$ 就好了..

然后，发现 T3 后面的一个点跑了 1h 还没跑出来，于是就开始乱搞。先是调循环步长，发现还是跑的特别慢。然后就加了个剪枝，每一行找到第一个可以放的位置就放，快了很多。最后把两个点分别跑出来了 3 分和 4 分。

回去看 T1，发现一个剪枝搜索的方法（实际上和那个七方 dp 思路差不多…），然后写到一半想起来可以打表..最后写了个可以在 1s 内跑完一组的搜索，还是打了个表交上去。

最后是 $10+60+46$，被所有人踩了。

为什么我没想到 T1 的七方 dp 呢..当时脑子里大概是 $12\rightarrow2^n$，然而有三维，要 $2^{nml}$，做不了，不做了…（题解：一看就是指数级多项式算法）

CTS Day 2

又咕了 5min。

第一眼，T1 计几，考场不能开计几。

第二眼，T2 字符串！woc，还是个计数。

第三眼，T3 这是棵树！这边怎么还有反的..

看了一圈还是感觉 T1 最可做…然而我先去推了一会儿 T2，没有任何成果。T3 的暴力也不会写..

冷静了一下想到了 T1 $30​$ 分做法，就写了一个。考场上还算错复杂度了..只不过问题不大。

然后在三题之间轮流自闭，T1 猜到了凸包合并后更优肯定要合并，也写了个两两尝试合并，然而过不去样例三，就没管了。（95 分做法：随机合并，记录过程中最优解，直到快超时。）

快结束的时候写了个 T2 10 分爆搜，发现要跑 4s，然后就写了个字符离散化..实际上可以被类似 bdfhjlnprt 之类的串卡掉，只不过还是过了。

最后是 $10+30+0$，好像还挺大众（

CTS 其它

讲题比较自闭..就记得 _rqy 自己上台吐槽两天四道计数，组题人（同时是 D1T3 出题人）说“我要从五道题里面选六道题，我也很无奈啊”。

另外首师大附中里的有张摄影的标题戳到我了…（不要说我中二）（也不要在意右边，那是手指挡住了）

录了个论文答辩。

最后闭幕式的时候 wh 和 dzd 的讲话还是非常精彩。譬如：知识点涵盖了容斥原理，动态规划，概率论……为什么要去掉这个 C 呢？没有钱是干不了这个活的，收的钱也不一定够

dzd 还抱着好像是某位博士的女儿上了台..

在 cf 上抢了个评论。上午答辩完就差不多猜到了名单，然而不敢提前发，就提前写好了评论，一公布立马发出去了。感觉的确可以从答辩判断名单，某个 twr 硬是觉得有黑幕还被 up 了我就很没有办法。

cf 出题组全员 Ag。

APIO 讲课 Day 1

上午缓存管理，下午 PJ dp ？？

APIO 考试

开场 5min 就交了一发 WA..把 A 的暴力交错题了，一看发现纸质题面和实际顺序不一样（好像是翻译的时候还没给题目顺序…）

评测系统果然是不需要数据分治的，每个子任务分别提交就可以了，会分别在所有提交中取 max。只不过如果出现特殊情况，要由 CCF 来收题，这样写可能会比较惨..

先把 T1 的暴力和无修改写了，然后把 T2 的 10 分写了，然后把 T3 暴力、询问长度一、零变一写了，然后把 T1 链写了。这些分好像都比较水..过程中想了会儿各种正解，写完的时候大约是 3h。

然后，感觉 T1 的树应该可做，然而不会做。T3 的修改在询问前好像也不太会。然后去看只有 10 分的 T2，怎么这么多 subtask，我一个都不会啊..然后，我发现好像有循环节，然后就是本场比赛最蠢的一个地方，我把循环节暴力跑出来，然后用 map 判下标..然后想了个特别麻烦的 5 分做法，一直调到考试结束…

最后分数就是前 3h 写的 $43+10+60$，一出考场发现所有人都是 243 / 203 … 说好的 100+ Au 呢？以后再也不能按往年分数线打比赛了…

APIO 讲题

• 考虑让大象写题解
• 大象写了一篇题解
• 讲完了

APIO 讲课 Day 2

上午是 THUWC 时来过的 lzj，又是图像渲染。

下午是四场讲题里最正常的一场（树上线性问题），前半部分是 希望的超详细题解 自顶向下 dp + 长链剖分，后半部分，后半部分是什么啊..好像是各种神仙题，比如树上线性（不带反阿克曼）并查集……

APIO 颁奖

五页 113 艹，成功压线 Cu。

四页 203 Au 比 Ag 多艹。

Ag 前几都是神仙艹。

THUSC Day -1

THUSC 电脑的用户名是 THUSC Day 0-Test、THUSC Day0、THUSC Day1-1 和 THUSC Day1-2。（为什么 Day -1 要提 THUSC 电脑用户名？因为今天是 Day -1。）

收到选手须知，划重点：WireShark，O3，python，Ubuntu 16.04，没写考试安排。

学一波 WireShark 好了。

结果颓了一整天

晚上 11 点睡了，好像很久没睡这么早了..

THUSC Day 0

为什么 tdoj waiting 显示满分啊..一开始我还以为 pt 是假的（

试机自闭了，sb 字符串二分想了无限假做法，开始怀疑自己的智商。

开营式全是硬广，感觉还是 THUWC 的有意思些，哦不对，那好像是闭幕式…

一进考场就发生了一件很神奇的事，94 和 96 中间没有 95..于是我换了一台机子。

比赛咕了 $40min$（传统艺能）。

开场看 T1，很快发现了（在没有操作 3 时）取空的情况只会发生不超过 $n$ 次，20min 的时候已经完全构思好了正解，然而不知道为什么以为操作 3 会破坏复杂度，就写了个 60 分..第一次尝试在草稿纸上完整地写下要维护哪些量，每个操作各要具体怎么修改怎么询问，写了半张草稿纸，然后写代码极其顺畅，1h 的时候就把 60 分部分分 1A 了。然后发现 $l=r$ 也很水，就写了个 $80$ 分的数据分治，然后各种挂，又过了 $40min$ 才写完，共 $6.2KB$。

然后看了眼 T2，$k=20\rightarrow2^k$，$\min\rightarrow minmax$ 容斥 $\rightarrow$ 不会做（鬼知道我怎么想的），然后去看 T3，侧信道攻击是什么啊..OI 题名全是骗人的.jpg。往后一看，好像还真是题目背景里说的那回事..好像不太可做，回去看 T2。woc 这不是个 sb 题吗…在最短路上就是 $dis[u][k]+dis[k][v]=dis[u][v]$，然后随手写了个 $3^k$——对每个救援队记录哪些点可以。然后发现改成对每个点记录哪些救援队可以，就可以轻松 $n2^k$ 了..pt 1A，然后就没管了。

犹豫了一下，决定还是先别侧信道攻击了，回来看 T1。woc 我又 sb 了，操作三不破坏复杂度啊，每次单点加最多把一个空的变成不空，所以还是只会有不超过 $n+m$ 次取空..于是在 $60​$ 分代码的基础上只加一个函数，其它全都不用改，就 pp 了。

然后去看 T3，这个 $10$ 分，可以枚举 $w$，枚举 $y$，枚举 $q$……诶，询问数超了，那就 get_w().. woc，直接 for (i = 0; i < 500; ++i) Qs[i] = i; 不就可以了吗，我又 sb 了..把枚举删掉，写上 for 循环，一交，怎么爆零了？woc，没设置 $u$ 和 ​$v$…那后面的分怎么做啊..先 get_w() get_y() 吧..二分一下 $q$..怎么过不了啊..哦，是快速幂，所以 $time$ 并不关于 $q$ 单调..那就以二分结果为中心往两边爆搜吧..$subtask2$ 拿了 $16$，继续各种乱搞，拿不到分了，考试结束了。

感觉好像比较大众分啊..可能会被 T3（& 可能比较弱的 pt & 把 THUSC 当成 IOI 赛制打的选手）区分出来了。

大约在宾馆见识到了真正的“抽水马桶”…不是按，不是转，是抽..

晚上睡得比前一天还早（

THUSC Day 1-1

94 和 96 中间还是没有 95…

比赛又咕了 $30min$。

开场，T1 不是 sb 题吗 $\rightarrow$ 没过 pt $\rightarrow $ 读错题了？$\rightarrow​$ 草，只有灯塔可以点亮..（鬼知道我为什么在点亮数轴（大约是以为每个点都有灯塔，只是一部分有游客吧..

于是 20min 才把 T1 过掉（

然后去看 T2，前两个 subtask 好像挺好写的..继续看 T3，考场上好像不能开计算几何来着（

然而我还是开了..emm..这玩意不用取模诶..哦，好像每种本质不同的划分都可以用一条两圆公切线表示。但是，怎么求公切线啊..用各种方法算了一个小时，算出来的结果都很麻烦，感觉会算错，于是就没管了（然而降智的效果已经达到了

先写了前两个 subtask，然后发现好像可以处理出每个右端点向左种类数增加的地方，然后写了个假做法写自闭了，最后大致上想到了单调栈做法，然后好像是以为假掉了，也可能没太想清楚，最后写了个 $\mathcal O(nm^2)​$ 交上去…

成功被计几 & 自己的假做法降智，被区分了，白给 $48$ 分。

THUSC Day 1-2

果然是网络题..

有了 WC 的经验，没仔细阅读学习手册直接开始做，还是写了 $1h$ T1..

T2 的 $8$ 分是 CRC32，WC 写过，然后..写了 $1h$，WA 了 $1h$。学习手册里的 CRC32 样例过了，输出中间结果 data 转 01 看起来也没什么问题..不知道怎么回事。

大众分好像是 $48$，㕛被区分了。

THUSC Day 2

听说线 428 ？emm..成功被白给区分了。

只不过也没什么白给不白给的，就是不熟练才会白给，会做也没用啊.

网传线假掉了…

我妈在八点半接到我爸的电话，说我爸接到了 THU 电话…

然后，赶去西郊宾馆，等了 2.5h，好像是分块后按字典序排？中途还见到了在其它 SC 游记里听说过的搭矿泉水瓶。

面试大约是自我介绍 + 提问 + 嘤语阅读。毕竟我也是受了其他人游记一定的帮助，简单说一下需要注意的问题..

1. 自我介绍不需要提 OI 成绩。我一开始说我的 OI 成绩被打断了，好像是考官有成绩..（其实是看别人游记说教官提问“你的 OI 最好成绩”我才说的 qaq
2. 提问会和自我介绍相关。反正我是这样的..比如，我自我介绍的时候提了一下对人工智能略有了解，就被问了有哪些了解、有什么看法之类的。所以建议自我介绍可以提一提自己熟悉的计算机科学领域，然后在相关方面准备一下可能的问题回答。
3. 嘤语阅读要尝试看懂。大约是计算机科学专业文章，一开始会给你 $30s$ 左右看一遍，然后我当时只是想了想应该怎么读，没有仔细看。读了一遍之后他问我看懂了什么，然后就 GG 了..个人感觉这个部分是我面试挂的最惨的地方（

下午讲题 + 科研 / 科协 / 蒜算协 介绍，感觉不如 WC 有意思..可能是时间比较短，而且也听过一遍类似的内容了..（有个人工智能简笔画妹子挺有意思的）

然后，荣获 3=，就去赶火车了..