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 AuAg 多艹。

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=,就去赶火车了..