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

发表于 2018-09-29 更新于 2024-07-29 分类于综合比赛本文字数： 7.8k 阅读时长 ≈ 14 分钟

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

### 流水账，记录下一些大事的时间 | 时间 | 事务 | | --------------------- | -------------- | | 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