2018CCPC秦皇岛站记录及暑假集训感受

男儿何不带吴钩
收取关山五十州

流水账,记录下一些大事的时间

时间 事务
9月26日 9:30——14:30 南京南——秦皇岛
9月27日 14:00——15:00 比赛开幕式
9月27日 15:00——17:00 热身赛
9月28日 9:10——14:10 正式比赛
9月28日 15:00——16:00 颁奖仪式暨闭幕式
9月29日 8:02——12:15 秦皇岛——北京
9月29日 13:00——14:30 游天坛
9月29日 16:15——21:43 北京南——南京南

启程

获得名额

七场激烈的网络赛尘埃落定,team002 (到目前为止)获得了 1+1 场比赛机会。在比赛还未结束时,我们差不多已把握了 CCPC 秦皇岛赛区的名额。秦皇岛赛区是时间较早的一个赛区, 暑假完后不到一个月就已开始,我们队因为自己还未充分准备,想多补补题,做做题目,加之比赛需要我们请假四天,大三课程紧张,四天要旷课许多,我们队便有了想换赛区的想法,改为 CCPC 桂林站或者是两场 ICPC 比赛。但和老板沟通后,因为如果我们赛区改动,别的队伍将来不及安排,于是我们队选择大橘为重,擎南邮之帜,以“以上队伍成绩无效”之名,进军秦皇岛。

行程安排

青岛网络赛结束后,队友因为数模提前回去,我和八队留在了活动室计划行程。此处省略N字,本来以为是件简单的事情,没想到买个票,订个房这破事能用两个小时,无语|||。

行程定好,我急匆匆赶去易班面试新人,和技术部众大佬一顿吹比之后,回宿舍时已是黑夜。仰观皓月之明,繁星璀璨(瞎编的),心中不由燃起一句诗。

男儿何不带吴钩, 收取关山五十州。

准备

时间紧迫,比赛就在眼前,我们队为了稳定下成绩,自己用课下的时间做了些训练。正式比赛在中秋节后,于是我们利用中秋假期做了两场训练,一场是去年秦皇岛赛区的原题,我们前两个多小时差不多就写好了铜牌题目。开始向银牌题发起进攻。我和葛宇轩各开一题,最终双双开花,都 AC 了, 过掉了五个还是六个题目,记不太清楚了,定在了银牌区。第二场题目是一些银牌题的汇总,对于银牌题,我之前是不敢做的,但接触后发现银牌题蛮好玩的,不像自己想象的那么可怕,(对银牌题产生了兴趣)。做银牌题其实有些不太顺畅的,四个小时最终A出了两道。不过这两道让自己受益蛮多的。

其实,我和时光一直想着中秋能够出去玩下,尤其是我,想带时光在南京转转,因为来了四个半月,我们只一起去过家门口的夫子庙。一直想带她去的老门东都是一拖再拖。我们一直期待着中秋,可我又辜负了中秋。想来蛮遗憾,又有些说不出的难过。

扬帆,起航~

时间来到了乘坐高铁上,我们大家偶尔歇息,大多都是在看算法。三个人在高铁上学习了很多东西,emmm,准确地说是队友学习了很多,wade 看着上次训练的银牌题, Bule_Zst 在看字符串里的后缀数组,我复习了下数位dp, 尽力地去感受下它状态转移的思想,后来又是看了状压dp, 经典的铺砖问题, 看到终点时,仍未理解其意,它用滚动数组来节省空间地记录状态,看了许多都难以真正明白,大概还是自己太菜了。来还看了些图论。将近秦皇岛,心中不禁翻涌起主席的词。秦皇岛外打鱼船、大雨落幽燕、白浪滔天、魏武挥鞭、东临碣石有遗篇、换了人间,一个个没有顺序地往上冒。

在秦皇岛

一些赛前的事

一直以为秦皇岛在河北,会是河北口音,结果下了高铁打的时师傅张嘴一口东北话惊了个呆。后来发现秦皇岛居然是东北口音。看到宾馆房间的一刻,觉得还是蛮好的,三个人只要131一晚,床蛮豪华的,不潮,还有桌子。觉得宾馆蛮好蛮值的。一个队友问“这是什么”,我带着北方人的骄傲自豪说:“暖气”,队友恍然大悟地“哦~”,(晚上,队友突然说“要不我们打开暖气感受一下”, 我, emmmmm, 我应该怎么告诉它暖气要怎么用=w=, 南方人真可爱。)

到达后我们决定找些吃的,和队友一番觅食后找到了一条美食街,又是一番选择,最后两个队来了烤肉店,QAQ,给我们烤肉的小哥哥超帅!或许是我们下午去的,客人还比较少,小哥哥就一直在我们桌这里给我们烤肉,还会夹给我们,QAQ,好评好评,小哥哥站在我身边,总是忍不住偷瞄几眼。

本来我们想吃好六点半回去打场训练赛,可是韩式烤肉这东西,你懂得,贼耗时间,烤半天才吃那么几口,我实在是不适合吃这个 TAT,忍不住馋呀。吃完回去差不多已经是七点半多,我们好像没有打训练赛,而是看起了自己的。我给学长做了几道水题后也看起了之前积累的题目。Bule_Zst看字符串看得很开心,心想,这次比赛如果遇到字符串稳了。

第二天早上喝了羊汤便去报到,匆匆走了遍流程,换上了粉色的衣服,大家在校徽牌下拍了照,传给了老板。(万恶之源从这里开始)结果老板对照片不太满意,告诉我们拍照要离牌子远一些,这样能突出人。然后疯狂暗示,在大群里分享知乎上一些如何拍出好看的集体照的问题,疯狂暗示。我们几个人便谈起老板,于是“建议转为非常规队员/荣誉队员的梗”、“建转非”诞生。这个梗被我们不厌其烦地玩着,直到现在还在一直说。如我和 wade 不约而同地唱起了智斗,他们就会说:“经过大家一致讨论,建议你俩转为荣誉队员,更好地去唱京剧,考虑到ACM协会长远发展,把机会留给需要的同学”(求大家给个标准版本呀,我这个记得不太清楚), 曹老板第二天煎鸡蛋,我们就说建议你转为非常规队员,更好地记享受生活,云云。每次提到这个梗大家都笑个前仰后合,或许别人不知所以然,但A协的估计看到大多会莞然一笑,深领其意。

还有一件事情就是和朱兄面了基,QAQ,开心,聊了一年多,终于见面啦,还有一些小紧张呢。

热身赛

我们队伍赛有一个魔咒,一到热身赛就会懵比,简单的题目会一直WA和T, 或者不知道怎么做。我们仨谓之攒人品,这次热身赛前也想着不小心WA些次,给正式比赛攒点人品。但这次热身赛是真的懵,不知所以。C题是签到题,我看了一眼后就有了答案,1e4的数据,只要找到最大最小值就好,预计两三分钟就能A。然而,1e4的数据,我们扫一遍数组O(n)的算法,在1s的时限下居然T了????简直不敢相信,于是我上场,进行了一波玄学优化,把循环的i 设为寄存器变量,加速循环。Submit, 红色的WA赫然显目。还好是WA,在惊叹寄存器访问速度的同时 wade 找到了问题所在, 题目中说的是 “any two numbers”,任意两个数字,如果最大最小值一样的话我们两个都会选择数组第一个,知道了问题后立即改正,submit, T???当时心态就炸了,尼玛,1e4的数据,我就扫一遍数组,O(n),你告诉我T???题目叙述不清, 数字个数可能为1个,这种情况你让我们输出什么??? any two numbers 是位置不同还是值不同,需要不同吗。心太炸裂,无论我们怎么优化,都是T,偶尔有WA,但我们可以接受。虽然知道是题目的问题,但这种感觉就很不爽,一道签到题过不了就感觉很难受,心里不知道骂了多少次出题人。看着别的队伍一个个AC掉,升起气球,焚心似火。 在之前 wade 一眼看出了B的做法,因为C题耽误了很久,我们选择让 wade 先敲B, 我和 Bule_Zst 打印出C来看,还是那句话,虽然知道是题目的问题,但A不出,真的很难受。 wade 1A了B,我们心里算是有了些底,一起再看C,之后还是T。一道一眼题我们竟签到了两个小时???出题人***去吧。最后几分钟过了C,然后再多次交代码都AC了???然后开始测评测机速度, 循环大概5e8左右, long long乘法取模可以2e8次,评测机还算蛮豪华的,想想自己1e4的数据O(n)会T更是不解。想去知乎上喷出题人。热身赛这么坎坷也算是大攒一次人品吧。热身赛后我问我们背后队伍的小姐姐C题做法,他们是排序下取最大最小,O(nlogn)的算法,过了。????这个方法我们后来也用了,但好像WA了。后来又和8队谈,他们根本没考虑 “any two numbers”,想骂出题人++.

晚上训练

热身赛后的晚上我们小训练了下,做的是去年 CCPC 哈尔滨场, 一个毒瘤场,2题铜。

第一个题目是让你构造从 1 到 n 的全排列,使对于 $i \ge 3时, a_i \equiv 0 \pmod {|a_i-a_{i-2}|}$ 。我先想出了n到10时的情况,发现并找不到规律。一番思索后,和 wade 同时想出了答案。(我拿起笔准备写的同时, wade 给我要笔,结果看我写完说他要写的也是这个)。我们的方法就是把n分成两段, 然后间隔输出。如1到10就是分成1~5和6~10, 答案就是 1 6 2 7 3 8 4 9 5 10 。AC。

第二个题目是有n堆石子,每堆石子数量告诉你,每次操作只能从一堆取一个石子移到另一堆,要把这些石子操作成每堆石子的数量都是一个数的倍数,问最少的操作次数是多少。首先可以很明显地想到要对石子总数求其因子,这也是队友的想法, 枚举因子是 $O (\sqrt{sum})$ 的时间复杂度,之后要求出对于每个因子最少需要的操作次数,在求操作次数时队友遇到了小麻烦,因为我们不能够预先知道当前石子需要填补还是移到别的石子中, 比如 “2 2 3”我们需要移动 4 次, “2 6 6 11”在让每堆石子数是5倍数时操作数为3,(分别从6,6,11拿一个移到2上)。我们找不到解法。这时,我有一种感觉,这是我擅长解决的题目。我也不知道哪来的感觉,但就觉得这是自己所擅长的。一开始,我陷入了和队友一样的困境,无法考虑当前石子最优的方法选择,感觉dp,贪心什么的都没有方案。看到 $O(\sqrt{sum})$ 有些大,可能会 $T$ ,灵感闪了下, 感觉不用枚举全部因子,枚举素因子就好,给队友说“因子的倍数必是素因子的倍数”,一语中的,三人恍然大悟, 自己也是兴奋不已, 站起来喊了声 “崔明浩牛逼!”。这样就把算法优化到了 $O(log sum)$ 。然后又开始了对操作次数的思考,久久思索,不见答案,但总觉得自己可以解决。一瞬间,又是一闪灵光。瞬间想到了答案,对于刚才”2 6 6 11”的情况,写下了”2 1 1 1”,之后(2+1+1+1)/5=1, 5-2=3, bingo! 得出答案。我们先用每堆石子对当前情况下的素因子取余, 把余数相加,其必是该素因子的个数,(别问我为什么,自己想),将和除以该素因子 $p$ 所得商为石块归并后的堆数 $m$ ,之后对余数排序,选出最大的 $m$ 个, $a_1, a_2, ……, a_m$,$\sum_{i=1}^m (p-a_i)$ 即为 $p$ 情况下的最少操作数。把作法告诉队友,站起了又喊了声 欢迎hack~ ,AC。两个小时的时间做完了铜牌题,信心大增,十分地振奋。 后来,“崔明浩牛逼!”和“欢迎hack~”成了新梗,队友称之为自信二连。

正式赛

正式赛的早上在宾馆吃了自助餐,虽然照在上海吃的宾馆自助餐差很远,但我觉得种类虽然少,但还蛮可以的。8队的曹老板惊奇的发现了煎蛋器和烤面包机,曹老板将他的富有生活情趣发挥到了极致。煎个鸡蛋,烤个面包,美滋滋。

到东秦体育馆后有些想上厕所,结果这时候男厕居然破天荒的排起了队= =,比赛很快就要开始了,队伍还很长。这时有老师说另外一边还有一个给我们开放了,我们便跑了过去。之所以说上厕所这事是因为在去的路上,我看到了气球!我发现有黄、浅绿、蓝三种颜色气球比较多,心里大概有了底,可以做三题,然后发现黄色的最多,那应该就是签到题了。回来告诉了队友自己的发现。比赛推迟了10分钟,虽然不让动键鼠,但已经有人敲起了模板,我们也敲了起来,对面有个队伍竟然已经打开了题目册,这个不能忍= =。

9点10分,比赛开始。

我们打开了题目册,三人读题,登录账号,发现B有人提交,三人一起看B,签到题确认无疑。B题就是一个时钟,给你两个时间,问两个时间过程中时针和分针相交次数,左端点重合算,右端点重合不算。一番考虑,11点内不分重合,所以不算11点,23点就好,试了些样例,sumbit, 1A。心里有了些底,虽然验证耗了些时间,但我们觉得值得。

我和 wade 开G题,看了一会后发现暂时没了思路,看了下榜,B题通过人数在上升!分析了下环境,G应该是蓝气球,B是黄色气球。我们转向B题,很快有了思路,字典序枚举答案就好,用全排列 6*6 = 36 种可能。之后再用枚举的答案去匹配它给的串,匹配成功就返回。Bule_Zst 敲好代码,我们测了几个比较苛刻的样例,通过,Submit, CE??????一脸懵比,这个平台又不能看编译错误在哪,本地没有问题。。看了一眼榜,居然有-1,woc?CE居然算罚时,打开问题板,发现大家都在说B题CE的问题,管理回复说已经rejude重测,看了一眼状态,提交的那发WA了。有些难受,三人秒调整心情,找WA点,但卡了好久,这时候,wade 和 我打开了红牛。。wade说红牛买假了,喝了犯困= =,后来我看了红牛罐,发现上边标着Fe,突然一种不祥的预感,但不能告诉队友,怕涣散军心。。就瞒着这件事。看着周边的队伍一个又一个过了B,升起了黄气球,看了下主页,大约百个队伍过了B,又是焚心似火, 不过又有些安慰,因为看队友状态,我感觉这题能过。时间分分在流逝,突然 wade 找到了WA点,我们的字典序有问题!会有重复,去重之后再提交,AC!心情稳定了下来,有了底。

我们便去rush G。G题题目是给你一棵无根树,问你他是不是一棵K叉满树。如果是,输出最小的K。虽然写B的时候我和 wade 没有想G,但现在回来看竟然有了一致的思路。我给 wade 说起了思路,我们把点分为根结点,叶子结点,和中间结点。如果他是一棵K叉满树,那个根结点度为K,叶子结点度为1, 中间结点度为K+1。我们统计这三个度数的个数,一般情况下,找到数量为1的,就是根结点,那么我们获得了K,已经知道了它是K叉树,然后获取度为1的结点的数量,其必有 K的n次方, 这样我们就可以获得树的层数,为n+1,然后我们可以算出理论上度为K+1结点的个数,再和实际的比较,如果相等,那么它就是K叉满树。这是一般情况,其它特殊情况判断下就好。 wade 让我去指引 Bule_Zst 敲代码, = =, 真的,太痛苦了,看Bule_Zst的代码命名和花括号居然不换行,我有想打队友的冲动=w=,我指引写代码坎坎坷坷,wade 看我俩费劲忍不住亲自来敲。敲好后我们测了自己的样例,通过,这时我更改了下出的3叉满树的样例,将一个叶子结点连到了根结点下,结果程序还是输出 3。成功Hack!我发现这组样例根结点变了,由1变成了4,这时提出了想法,将树根换为4重整树!我和 wade 很快的发现了问题,我们这样判断的,是它是不是一棵K叉树!并不能判断其满树情况。于是 wade 开始敲验证满树代码,G题我们用了很多时间,Submit, 红红的WA震惊了三人。我们一直有个疑问,就是结点数为1时,我们输出 -1 还是1, 这也是出题人被喷得最惨的地方,下面会详述。。我们用了很长时间检查了代码,觉得思路没问题,唯一的问题就是结点数为1,又是一番纠结,改为1后, Submit, TLE!一阵心惊,三人很快互相鼓气,说没事,稳住。我们分析了数据范围和算法的时间复杂度,觉得可以过,将问题移向了vector的使用和一些初始化操作(clear及memset操作的耗时),将树由 vector保存转为了 前向星写法,将memset改为for循环来清空。submit, 心中默默祈祷,AC!三人长舒一口气。

看了下榜,I过题人数比较多,我们开始rush I题。我和 wade 有了不同的想法,wade 觉得是满流的最大流问题,但是要求求出多解的方案数,不会,我们先让 Bule_Zst 敲Dinic算法的模板, 我的想法是状态压缩+暴力搜索。后来大家觉得我的做法比较可靠,便放弃了最大流,转为状压和部分和搜索。 Bule_Zst的撸代码能力着实让我吃惊,在我还构思的时候他已经在很快地敲上,感觉一气呵成。虽然思路还不明确,但着实让我震惊。I题我们没有很明确的思路,所以只能试着碰碰运气, Bule_Zst最后代码结构也乱了,能感觉出来,这里改改,那里改改,很容易失去结构。我们只能靠着样例来判断,可程序会爆segment fault, 改改,过了第一个样例跑第二个,最终终是无能为力。。(晚上 Bule_Zst 说在最后半小时的压力真的让他承受不住,要崩溃了。)

比赛结束。

我觉得三题拿铜没问题,而且我们错误的提交比较少,封榜前是95名,离铁牌区还有着50多名的距离。再说如果后边的人真的厉害,早就过题了。但 wade 蛊惑人心说可能铁,想想自己在红牛上看到的 Fe(比赛结束也告诉了他们),自己也有些虚。mark(写着Fe的红牛= =)

赛后问了后面队伍的小姐姐他们I 题怎么过的,小姐姐告诉我说是个很复杂的 dp, 他们用了好像三四层for循环。一瞬间有些后悔,因为自己一开始也想了状压dp,但后来改向了更暴力的搜索。自己有些内疚的,因为队伍里dp的话一般是由我来想状态转移,这次没能 rush 出来。三个人的心情也有些坦然,没过多地去后悔代码没能写出,因为写出来等待我们的也可能是T。

比赛时状态还是会受周围一些影响的。比赛时向右看了下,突然发现了jls居然在我们这一排。jls有些可爱= =,瞅他了很多次,有次他敲代码时还是会敲指甲,和 World Final 直播里看到的他简直一模一样。偶尔凑巧看到前边队伍笑得很开心,自己好像也有动力去想题目。最后的时候复旦的拉格朗过了D,看到AC的时候他们队沸腾了,全场都在看他们,其中一人跳着说 夺冠了!而当前我们还在写 I 题,压力让我有点羡慕他们。

颁奖前的小等待

比赛结束到颁奖仪式有 50 分钟的时间,我就在赛场晃悠,有时找朱兄去玩,有时去看看别的队伍。找朱兄的时候队友QQ告诉我打铁了,心中寒了下,很快地回到自己座位,原来是在逗我,志愿者通知过了,我们是铜。一瞬间压力释放了些,但却没有开心,更多的是有着很多的不甘。这些等写下面总结的时候写吧。

震惊!女朋友居然会看榜!!女票说她看我们95名时我简直惊了个呆,这货居然快成行内人,会看榜了!mark 热身赛后举办方采访我们,让我们比手势说 “CCPC, 耶!”, 采访的时候我就有些不详的预感,果然。。。结束后放视频居然有我们。。放到的时候我捂着 wade 低下头想不被人发现我们。过去后后面队伍的小姐姐对我说:“我看到你了。”????嘤嘤嘤。然后= =,女票, = =居然看到了这视频的照片,嘤嘤嘤嘤嘤嘤嘤嘤!mark

颁奖

嘻嘻嘻,队友简直是天选之人,铜奖最后一批上去,站在了最中间。从两边向中间开始发奖牌,到队友那里刚好没有了。队友在上面一脸懵比,看着他的表情,我笑得不行。也不知道要不要拍照,哈哈哈,上台了没有奖。队友:虽然我没有牌子,但也要努力地笑出来,尴尬而不失礼貌。mark mark

如何看待 2018 CCPC 秦皇岛站

赛前王和兴老师会在群里问大家需要的 IDE 和 编辑器,觉得还是蛮好的。

出题人是真的垃圾,出题题意说明不清让人来猜是真的该被喷,热身赛的C真的让我恶心到了,后来好像还rejudge fst了, -27, 呵呵。mark mark mark

暂时写到这吧,一些感想等下更。未完待续……

2018年9月29日


于高铁上

❤采之欲遗谁,所思在远道。❤
0%