300iq奔北坡

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

实际上是一篇 CTS & APIO 2019(可能 & THUSC )游记。

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 在 20 号之前不能写游记!!!

先写在这怕自己忘了。