初赛

去临时的 OJ 用临时的帐号打临时的比赛(误)感觉有点奇怪,把题目存了一份:https://pan.baidu.com/s/1tLYZA2ssDN2lCqiZWqMGqQ,提取码 jnq2

纪录一下第一次,可能也是惟一一次提前半小时 AK。

问题最多的居然是 A 题签到题,刚开始还想逐个数判断是不是完全平方数。后来想想不就是两个边界开个根号的事嘛。另一个 D 题签到题似乎刚考完三个数的现在才问两个数的。

异或出了两题很过分,然而一道是去年蓝桥杯热身赛的原题完全不用想,另外一道似乎是防 AK 题我刚开始还试图交个 n 方看看数据强不强。降维好像也不难吧无非是统计下序列中有多少个数转成二进制之后有奇数个一,多少个是偶数个一。奇数个一的数和偶数个一的数异或结果还是奇数个一。有一说一在洛谷看题解骚操作确实学得多,一个 __builtin_popcount 就完事。

完美数嘛就打表出奇迹。开一个 10000 大的数组把结果先搞出来丢程序里也就代码长了点嘛。于是欢乐数继续打表,还担心溢出加了个 log10 算一下位数。

至于交换字符那一题题目翻译一下不就是 y 可以随便挪位置嘛,反正无论怎么挪 x 和 z 的相对顺序都不会变,那就将全部 y 全部丢到第一个 z 前面其它原样输出就好了。数据似乎很弱我怀疑我漏了情况但我没有证据。

下周石牌校区继续白给。

决赛

第一次是可以带纸质资料进赛场的。刚开始对此是真的毫无头绪,寻思这带过去的要不就是自己早就掌握的,要不就是自己本来就没理解的,那还有什么用。后来也不想考虑太多,去洛谷搜索模板,按照难度排序,从 入门 一直到 提高 只要题目看的懂的就把高赞题解的代码抄下来(还把问题本身也给抄下来了我太机智了)。后来被 CGY 嘲讽了一波(我也想拿区域铜 orz)。周四香农先修班下课后讲课的师兄也提供了一份模板,感觉不会的东西实在太多决定新生赛还是先用自己的。

C 语言老师那边丧心病狂地周四周五连续上了八节课,于是我也决定要丧心病狂地划水(不是,周五那天上到最后两节笔记本没电就滚去看紫书了虽然依然没学到什么 周六在补各种作业(写到这里,突然想起有个三代单传大锅下周要出 0.1?)。

比赛当天十点就出发拉到石牌校区了,看时间好像还早就跟着 PYY 去天河城玩去了,靠复印模板还骗到了一顿饭确实香。结果因为校园太大我又路痴还是差点迟到(吹一波南海校区麻雀虽小但五脏俱全)。计科居然还有专门的 ACM 实验室,但比赛现场的机子也确实该升级了,甚至还跑着 Windows XP 系统(没记错的话)

题面 PDF 存档:https://pan.baidu.com/s/1CyhXu-0SZ7axguL64xTcwQ(提取码 4ckt)。

比赛开始前一分钟拿到题面,照例先看 A 题,10 的 100 次方?高精乘除法警告,下一题下一题。相比之下 B 题好像友好很多,差点忘记 d 整除 a 到底是 d % a == 0 还是 a % d == 0 全靠样例解释(不过如果真是前者还做个屁啊)。又是 GCD,交了一发 TLE 开始慌了,马上看榜发现计科已经有人过掉三题了迅速开启根榜模式。发现 J 和 L 题都是良心签到就去秒掉了。然后跑去看 E 题,马上跑去打了个表,我居然从 P == 1 一直打到 P == 63,等了一会不耐烦回到 B 题想起初赛时的 A 题我犯的错误好像一模一样,赶紧开个根号优化一下也过了。表打出来才发现 P 是素数于是又把打出来的数加一 log2 算了一发瞪眼判断是不是素数,筛掉不是的就将题目过了(讲完题解才发现打个屁的表啊题面上都有了)。

接着还是继续跟榜(计科巨佬不带歪榜太良心了),H 不就是 2、3、5 出现的次数分别存一下嘛也没怎么想。F 倒是出问题了,忘记 x % 3 == 0 的情况,又忘记特判 X == 5,吃了两发 WA。终于都过掉之后榜单排前面的神犇过的题似乎都差不多。开始看 C 题和 D 题。D 题又是考异或,想到了要特判 X == 0 忘记特判 X == 1(怎么我每次 WA 都是忘记特判)。C 题看着确实像我带着的线段树模板,但是问的东西和我模板的不一样没法直接套用。当时内心:新生赛哪有可能考这种鬼东西。不是前缀和或差分一律当超纲处理。开始 n 方暴力求解,cincoutstringstream 全部用上,不出意料 TLE。于是又跳到 I 题,刚开始还想着如果 2、3、5 出现的次数全部符合条件怎样分情况讨论,讨论个屁

这时候还剩 A、C、G、K 没过,距离封榜时间也不多了。K 题差点又想贪心完再对连续多天刷同一 OJ 的情况作处理,不过状态转移方程好像很好写的样子(有一说一是真的好写,我第一次看洛谷 P1164 那种题时内心是绝望的)。好的还剩三题(ACG 是啥呀我也不知道呀)。

开始集中火力干 C 题。我当时依然坚信暴力出奇迹,只是出题人想卡常而已。于是 cin 被改成了 scanfcout 被改成了 printfstringstream 改成了对十取模再对数除以十一路累加的做法(还得感谢广工的某位神犇当时点出来了所以印象非常深刻),本想着如果还过不了就再进一步上快读没想到居然过了。封榜之后看 G 题,考图的题本来是应该直接放弃的。但是我又带了单源最短路径和最小生成树的模板决定还是看一下题吧(其实是因为没得挑了)。发现问法和单源最短路径的好像差不多,就三个区别。一个是有向图变成了无向图,另外一个是指明了终点 t,还有一个是它还需要我回答经过了多少个节点。不管三七二十一把模板打上去了先,发现模板最后会输出到达每个点的情况,而我只需要到达一个点的情况,换掉就是了。至于每一条无向边我都直接转化成了两条有向边。而经过的点有多少在算距离的时候似乎可以同时算。居然也过了。感觉这次准备模板还是值得的。A 题这边实在能力有限(我觉得哪怕真的把高精写出来想不出正解估计也是得超时)。

比赛完就去听题解了,师兄讲的飞快,怕是 CGY 速度(只是突然想起了 AK 杯结束后的那个中午)。发现 C 题暴力不是正解刚开始有点幸灾乐祸,后来看滚榜发现靠这题还把计院的 WSD 和 PHS 挤下去了还是感觉自己配不上这个第三名(第一名是打星玩家,第二名是 SJL,感觉都是比我强很多很多很多很多很多的人,毕竟我也只是个暑假才开始入门的萌新),说白了还是时间复杂度没学好(果然无知者无畏)。后来去计院那边的咨询群坦白了自己是暴力过的,出题人验题人反正好多人都主动背锅感觉大家都不容易啊。

不知什么时候自己才能熟练掌握正解呢,无论是 A 题还是 C 题还是 G 题?靠暴力靠模板确实不是长远之计啊,就说 G 题这回还好只是有向变无向,下一回如果像 LZH 说的那样求第二短的路径?第 N 短的路径?或者 C 题时间限制从 2s 改回 1s?

完。


比赛结束后拍了一张自己的座位,那是真的乱得一批。顺便吐槽一句发过来的气球刚开始还是充好气的,后来就不充气直接贴桌子上了,再后来就干脆不发了。

以及... 第一次看滚榜。

最后修改:2020 年 05 月 01 日 12 : 10 PM