2019CCPC吉林省/东北四赛记录

总算也是参加了一次正规的编程竞赛,于是来写一个记录。

DAY 1

起了个大早去长春站赶火车到吉林。中午教练请吃饺子,19人点了28盘,不得不感叹东北人作风真是剽悍Orz…

下午到了东北电力大学。第一天主要是签个到,然后打个热身赛。吐槽下发的原谅色T恤,材料实在是一般。不过东北电力大学的食堂好评,菜挺好吃的hhh

关于热身赛,学长说随便玩玩就好。之前好像还出过“出题人喜欢甜豆腐脑还是咸豆腐脑”这种题。除了水题之外,发信息题讨论出是Tarjan缩点+DFS,后来发现DFS也不用,统计出度1的点就行。B就是算24点,刚开始还不让交,限制交20发,大概就是猜答案的压测题。不过10题猜起来还是比较难,于是我写了个暴力BFS跑出了前7个长度为5,剩下3个靠穷举(反正就8种)。坑爹的是,前7个和样例是一模一样的Orz。E题看不懂,场上也没什么人交。赛后听说夏威夷吉他的解几乎就是正解了,夏威夷吉他nb!

DAY 2

赛前我和队友说,上来三个人看首、尾、中三题,肯定能命中一个水题。加上名字叫送分题,于是上来就看的J。队友火火看到题目带LCA就兴奋的跑去看了,@MakiseVon去看了A。看完题撇了一眼榜,发现I才是签到Orz,然后主程火火秒A。

然后我看着J标题是送分题,以为是很简单的那种n一大答案就固定的题,于是打表了前面然后贡献了一发罚时Orz。此时@MakiseVon说G是水题,于是换位看题,发现E是水题,于是开始推公式。帮着检查了下G,然后A了。我E也差不多了,于是换我A掉了E。然后帮队友确认了下D的题意,就去看其它题体面了。简单推了下A,发现操作次数远大于数据范围,于是感觉可以对部分情况特殊处理。然后队友问我若干堆物品不同堆取多个能不能搞,推了下其实就是2^{k} - k ,听队友讲了下D感觉可以,然后换火火码。然而上来就是WA,然后火火立刻发现问题,然后又WA了。检查了半天,@MakiseVon发现是初始化没搞。

然后撇了眼榜,和队友交流了下决定搞A。和队友简单说了下我之前思路,我说从出现1开始,然而队友推了下,感觉只有一个1的时候很难弄,两数相等的情况也难搞。

于是回到J,打算先打个大表,由于大数Java,于是换最熟悉的我打。打完表第一时间的想法竟然是求差值,然而找不到规律。转换思路,从式子\left\lfloor\cos ^{2}\left(\frac{(n-1) !+1}{n}\pi\right)\right\rfloor推出\left( p-1 \right)! \equiv -1 \pmod{p}。队友秒看出就是威尔逊定理,之前三个人对着素数表竟然没人看出来Orz…火火说线性筛怕写炸,于是换我写了个线性筛A了。

F看数据就想到Floyd,然而没讨论出什么,于是讨论转向处理环什么的。然后上厕所的时候我想到,魔改下Floyd就完事儿了,于是也A掉了。

然后又捡起了A题。队友推了下,否定了特殊处理就一个1的情况。我试着写了下边界数据,结合A题过的人真的很多,于是让队友写了个暴力+两个1的时候特判,然后就过了23333

H看到题就发现是高中数竞的折线计数问题,李胜宏老师书的例题。然而想不起来公式,就去看B。我开始想了个O(n)的算法,讲完本来都打算写了,结果@MakiseVon发现锅了,题面是树上路径而不是父子链。之后虽然想了几个算法,但复杂度都不行。

封榜后基本上在搞H。我想了个补矩形法,然后作差减去多余的路径,然而样例都过不了。于是最后封榜期间也没交题。赛后发现其实这就是斯特林数,我推的那个式子其实减错矩形了,改一改然后Lucas就行。

最后7题,封榜前12名,侥幸拿了个金。虽然我演了队友一发,但其实作为第一次正赛还是很满意的。黑框眼镜两小时多就9题几乎AK,之后开始扫雷。夏威夷吉他第三。学长nb!

晚上就是四省赛热身,开始队伍数据好像录入有问题,之后甚至所有人都交在team001。晚上脑子有点转不动了,于是也没怎么想,放弃思考。

DAY 3

四省赛完全陷入自闭。刚开始A完签到题J,队友说C是计算几何,由于我只准备了计算几何,于是我就来搞C。火火去开E了。C的算法基本上很快就出来了,然后换我码。然后我就开始疯狂演队友了,WA了一发之后,发现结果计算有点小问题,改了之后队友给了几组数据都ok,但是还是WA。和队友讲了一下算法,感觉是完全没有问题的。后来又整理了一遍,修改了几处可能错的地方,然而还是WA。这时候我的心态已经完全崩掉了,完全是恍惚的状态。

火火跟我讲了下E,讨论了下具体细节,感觉可以做于是换火火写E。我打印了下C,和@MakiseVon开始查。然后又是一波演,E没初始化WA了2发,好在之后A了。我搞C的时候队友好像推了下I,但是暴力T了(暴力也显然不行XD)。

我把剩下题目过了一遍,F没查找的化单次其实就是做个差分,于是我和队友说了下朴素可以搞,试试看能不能优化,然后我就去写C的对拍了。其实当时几个人心态都没了,已经完全不想打了。于是队友跟榜去搞B,B想的是贪心,但是具体搞不出来(赛后发现我题都看错了)。C的对拍拜托队友写了个式子,但是好像式子也是错的。之后队友试着玄学改动、部分重写然而都没能逃过WA的命运,然后就结束了。

其实C的算法确实没什么问题,唯一可能炸的应该就是判重是通过排序和循环。当时修改算法后要是改用map说不定就可以了。最可惜的是F,其实只用树状数组维护差分的两个前缀和就行。然而赛事心态崩了,根本没去继续想F,队友也没怎么看。如果当初C能早点A,F完全可以过,然而并没有如果。

总之非常自闭,最后由于罚时也就拿了铜。说到底,还是一WA大家的心态就完全崩了,没法冷静思考。连续比赛也很累,感觉完全没办法顺利思考。非常对不起队友,由于我的C影响了整场比赛。可以说是很遗憾了。

发布者:KAAAsS

喜欢二次元的程序员,喜欢发发教程,或者偶尔开坑。(←然而并不打算填)

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注