Day 0(2020.12.4)

今天早上到机房后先把昨天上午考的 T2T3 改了,然后就开始颓废,主要是机房里颓意太浓了,又不想写题,便开始跟着 xfy 和 mzx 两位巨佬颓 MC,中途 xyc 在我们背后的窗户拍照,发现全机房几乎都在颓,很生气,把我们骂了一顿,接着 zml 也发现了这个问题,又把我们骂了一顿,让我们一人写一份考试注意事项,到时候要是谁犯了自己写的错误就收拾他,我第一行就写的左移运算记得开llull,没办法,这个错误太刻骨铭心了。

后来我也没敢怎么颓废了,开始水谷,第五节课下了之后本来想先颓一会再去吃饭的,结果又被 zml 从背后的窗户看到了,只好先去吃了饭再回来颓。

下午还是颓废,红警窗口太大了,不太合适,还是跟 xfy 和 mzx 两位巨佬颓 MC,不过还加了一个楚爷,他弄了一上午局域网联机的问题,最后发现是因为以前用他这台电脑的 WKR 巨佬下了一个 VMware,然后在网络那个地方就不知道为什么多了两个东西,把它们禁用掉之后就好了,气的楚爷大骂 WKR。

晚上请了个假回家,看了一下自己不太熟练的模板,打了一下割点,结果因为没看到是输出一行,用空格隔开,以为是每行输出一个导致第一发只得了 44pts,感觉有点不太对劲了,希望明天不要出这种奇奇怪怪的错误。试了一下今天早上下的 Arcaea,感觉还不错,以后在手机上颓音游就是它了(主要是 Malody 同步下的谱面太麻烦了)。

上次 tg 怀疑是因为中午没睡午觉导致下午脑子不好使,决定还是早点上床,预计九点半到十点左右睡吧。

NOIP2020RP++!!!

1
2
3
4
5
6
7
#include<bits/stdc++.h>
using namespace std;
int main()
{
while(1)
printf("NOIP2020 RP++!\n");
}

前段时间买的机械键盘打起字来真舒服

Day 1(2020.12.5)

昨天晚上睡得不错,今天早上起来第一次没有打哈欠,稍微把东西收拾一下以后就出发去学校了。

6 点 45 分到了之后发现其实都没几个人,大家都是老鸽子了,不过还是有很多巨佬,比如神 hfy 和国集爷 ZJK,把早饭面包吃了,膜拜了一发巨佬之后就上了学校的车,因为跟高中部的巨佬不熟所以并没有人坐我旁边,只好自己拿出 MP3 来听歌睡觉。本来我爸说的是已经把绿码发给了 zml,结果并没有发到我的,看来这家伙又把事情搞砸了,无奈之下只好打电话叫他给我发一个,收到之后又发现辣鸡 2G(是的你没有看错)网络根本没法从微信上把图片下载下来,连短信都不行,只好请旁边的初二的巨佬开了一下热点。。。

现在想想,说不定这就是我考试爆炸的预兆,从早上起来就一直 RP 不足的样子。。。

7 点 30 分到了电子科大之后终于见到了 mzx 巨佬(貌似是因为他坐在车子靠前的座位才没有看到他),在信软楼前排队的时候跟他聊了几句,奶了一口题目,他认为应该是模拟+计数+树+树,我倒是觉得 T4 应该会考图之类的,我希望不要考期望,但 mzx 巨佬说其实有可能,毕竟之前已经考过一次了。

在车上时就有大佬在说 CCF 排考号看来是按学校+姓名排的,排队时才真正感受到,整个 303 感觉就像是被我们学校包了一样(主要是一开始来的人本来就少),全是清一色的绿色冲锋衣。

进考场前稍微看了一下门口贴的考号,发现队爷 LSJ 巨佬就比我小了 2 号(我是 SC-0061),还以为这次说不定能【数据删除】,结果座位是一列一列来的,我刚好是最靠窗那一列的第一个,这下看不到 LSJ 巨佬的代码了。。。

监考员管的挺严的,我左边的左边那位大佬老是想打开 DEV,结果被骂了一顿,我没什么可干的,就开始默默祈祷巨佬保佑。

密码应该是选手加油?

md 键盘上的x键有问题,得用很大的劲才按得下去,还好我不经常用这个字母,但还是感觉很生草。

拿到题后先看了一下,T1 应该是一个裸的 sb 拓扑,T2 没什么思路,不过看样子是个字符串+计数(mzx 大佬还真奶中了!),T3 一看就很难受的样子,还有 SPJ,恐怕是做不起了,T4 也没什么思路,就还是回去做 T1。真的就是一个 sb 拓扑,花了 30 分钟做完之后大致看了一下数据范围,嗯,出度不超过 55,中间经过的节点数不超过 10105125^{12} 没爆 long long(不是这样算的啊喂),然后就去看 T2 了。

T2 先打了一发 O(n3)O(n^3) 的暴力,即分别枚举 (AB)i,AB,A(AB)^i,AB,A,再判断它是否合法,然后开始想怎么优化,想了一个小时没有思路,就先去把 T3 打了一发最暴力的搜索,整了个迭代加深,以为应该会很不错,结果连第一个大样例都过不了,只能过题目中给的小样例,没管那么多,又回去看 T2,看着看着突然莫名想到了之前看过的 CSP 迷惑行为大赏里有一个写考场心得的,于是也开始写日志,过了一会,突然想到我枚举 AA 的过程其实可以用树状数组来代替,又整了一个 O(n2logn)O(n^2\log n) 的大常数写法,接着又想怎么优化枚举 ABAB 这个过程想了半天后发现只剩 1 个半小时了,于是先花了 15min 把 T4 30pts 暴力打了,又回来看 T2,这次发现可以把枚举 ABAB 放在外层,(AB)i(AB)^i 放在里层,这样就不用每次暴力比较了,遇到不匹配的还可以直接退出,所以虽然理论上来说还是 O(n2logn)O(n^2\log n) 的,但常数小了很多,发现这时候算法的瓶颈变成了快速判断 (AB)i(AB)^i 是否和原字符串匹配,考虑了一下能不能用 KMP,觉得貌似不太行,于是用自己考前看的一点字符串哈希的思路搞了一发,结果连大样例都过不了。。。

还剩 25min 的时候放弃了,开始检查freopen这种东西,又算了一遍 T1 的范围,确认不会炸 long long(不会你马呢啊喂),最后 3min 的时候发现我 T2 如果是只有一种字符的话就不用判断是否匹配了,于是用 2min 写了一个特判,试了一下自己整的一组数据,还没来得及测样例就结束了,只好在心里祈祷不要因为这个特判出什么玄学的错误。

出考场后碰到了 xfy 巨佬,跟他交流了一下 T2,发现我们思路很像,都是枚举 ABAB,然后暴力往后跳,不过 xfy 巨佬说他的代码复杂度是 O(nlogn+26×n)O(n\log n+26\times n),他又去问了一下颜神,结果那个判断原字符串是否和 (AB)i(AB)^i 相同的过程还真可以用字符串哈希,不过颜神说他用的是双哈希,我不会打这玩意,只好放弃了,没办法,太菜了。

在集合的时候又遇到了 mzx 巨佬,他认为这次题出得确实很恶心,这里引用他的一句话

这次的出题人就是不想让任何一个正常人做对任何一道题

上车之后他又问我 T1 有没有用高精,我 tm 当场懵逼了,他说据一位大佬计算,答案位数可以达到 100 位,所以得用高精,没用会挂 20pts,我又问他估分多少,结果跟 xfy 巨佬一样,他也估计能上 200,我即使是最乐观的估计也只有 186pts,希望分数线能低一点,不过 mzx 大佬奶了一口,认为分数线应该在 140 到 170 左右,路上我突然想起来 T4 没判 1-1,估计又要挂个几分了。。。

对了,记得哪位大佬说过 NOIP 从来没有考过字符串,不过还好我之前学了一点点 Trie 和 KMP(然而都只打过板子),有一点点基础,不然 T2 铁定 GG 了。

车上开始打 Arcaea,挺不错的,画面很好看,也很有趣(不过 Present 难度的天空音符是真的有点难)。

回家后在信奥题库上测了一下,T1 挂了 10pts,T2 没有挂分,还是预期的 56pts,T3 爆零,T4 30pts,总共 90+56+0+30=176pts,还是不错了。

第二天早上起来在洛谷上估了一下分,T2 居然拿到了惊人的 96pts,只有最后一个点超时,看来数据还是水了,估分是 90+96+0+30=216pts。

现在看来我在 T2 上花的时间还是太多了一点,以至于 T4 都忘了直接输出 1-1 骗分(甚至连 1-1 的情况都没判)。总体来说这次应该是要比 CSP 考的好一点主要是没有毒瘤大模拟,希望能拿个 1= 吧。

我谔谔大佬的精辟总结。

后续

2020.12.8

草 T1 又挂分了,我还以为当 q=1q=1 时只输出一个 pp 就行了,又把题看错了,挂了 10pts,另外造数据的人你没马,先乘后除居然少了 30pts。

T2 意料之中,还是 56pts,洛谷的数据还是水了一点点,T3 也没啥问题,0pts,T4 因为没有判 1-1 的情况挂了 5pts。

总分 50+56+0+25=131pts,我人没了。。。

果然还是太菜了,等明年吧 /kk。

2020.12.15

分数线是 175pts,我果然还是太菜了,唉。。。

还是那句话,等明年了

不过好在线不是 140 或是 145pts,不然我可能会撞墙的