ICPC 50th 区域赛（成都）游记

· · 生活·游记

ICPC 50th 区域赛（成都）游记

🐉🧱正式队伍 CAU_CiAllo University 队长。省流：铜了。

文章可能有点小长，主要是流水账式的记录，还有一些自己的解题想法，如果有 vp 的还请自觉跳过。

Day -1

今天下午上了节大物实验，老师人挺好的，两点的实验两点半就做完签字跑路了。晚上七点四十的飞机，太早了，于是就回寝室坐了会。

回寝室坐了一个小时，收拾收拾了一些东西，然后在大概三点半的时候偷偷从学校西门出去坐地铁了。（因为下午四点本来还有课，来不及上了就翘了）

这次去大兴机场，本来想从北京西坐高铁过去的，一周前打开 12306 一看，全是 30 块，和大型机场线的原价都差不多了。没办法，就只有在咸鱼上买了张半价的大型机场线车票。其实也挺便宜的，35 块的价格被砍到了 17.5，和以前坐高铁运转的价格差不多了。

来到机场，大兴机场还是很方便的，大兴机场线出来没走多远就可以值机了。几天前线上选座的时候一看，只有 B/E 这种很难受的座位了，当时就想，反正都没有什么好座位，不如到机场现场选，万一航空公司有很多好座位没有在线上选座放出来呢？结果当天值机我问了一嘴，还有安全出口的靠窗位。我一想，这个位置既靠窗（虽然晚上也看不到啥），还是在安全出口位置，特别宽，毫不犹豫就选择了这个位置。签了个什么知情书然后托运完行李就安检上去等待登机了。

安检完离登机还有很久，我就在机场里逛了逛，突然想起来我带的泡面还在行李箱里，结果就这么一直饿到了民宿......

登机的时候，遇到了一群很没素质的老大爷老太婆，看起来像是刚从北京旅游完准备回成都的，操着一口熟悉的成都方言。登机排队，一个老太婆排在前面，然后突然来了十几个老大爷老太婆往我前面插队，也就是说一个人占了十几个人的队😅😅😅。然后开始登机了，人家商务座旅客有优先登机权，这个时候这群老大爷就不乐意了，一直在骂那几个商务座旅客为什么要插他们队，声音还特别大。我寻思着你插我队的时候咋不反思一下为什么要插我队呢，典型的双标行为，成都老年人的素质这么差的吗😅😅😅。

登完机了，坐了一会，飞机就开始动了，然后就起飞了。降落的时候，这个机长技术估计不太好，落地的时候“砰”的一声，像是重重将飞机摔在地上似的，然后机上的乘客都几乎跳起来了。当时把我吓了一大跳，还以为要挂在这里了。估计是因为下雨的原因，后面刹车的时候也是迟迟刹不住车，但还好有惊无险，最后安全到达了天府机场。

下机后，在行李柜台等了十几分钟，取了行李之后就赶紧跑到成都地铁，想着快收班了，能坐多远就坐多远，实在坐不了了就再打车。到了 18 号线的站台，我看了眼朋友圈，发现🐉🧱的女队也刚刚降落，当时就觉得不会是一趟飞机吧。问了女队她们一嘴，发现就是同一趟飞机，真是意料之外！然后顺便还和女队他们约好了第二天晚上一起吃个饭，大家难得都到成都打比赛了就一起聚一聚。

回到 18 号线，有幸坐到了直快车，从天府到成都南一站不停，33 分钟的时间就跑了 65 公里。但很可惜，还是没能赶上 1 号线的末班车，没办法，随便找了个出口出去打车了。

打车也不好打，等了快二十分钟才打到了网约车。网约车司机挺好的，我打的拼车，但这个司机没有任何歧视和说教，反而特别热情地和我聊天。又跑了 40 多分钟，终于到住的民宿了，这时已经快 1 点了。回了民宿，收拾收拾了一下东西，然后把我带的泡面吃了（没错，这个点才吃晚饭），洗了个澡就睡觉了。

Day 1

今天早上 9 点开始报名，我 8 点半起的，不是为了去报名，而是为了去看初音未来的大电影。为了抢首映特典，我 9 点半就到影院了，那个老板也是，一眼就看出来我是来拿特典的，让我过去选。结果发现影院没有后日谈，只有海报，那没办法了，就拿了个海报，然后拿了个兑换码，进影厅等着了。

在去影院的路上，非凸在签到处搞了个集赞拿大 fufu 的活动。我在路上偷了两张图，把赞集满了，想让朋友帮忙拿一个，结果 hr 不给，那没办法了。还好后面队友醒了，去到现场玩游戏帮我拿到了个小 fufu。

电影很好看，但确实如果只是奔着初音未来去的会很坐牢，但如果是烤批那就很对胃口。看完出来，发现已经有点晚了，又打了个车去体育馆，这个网约车司机态度就非常恶劣了。我又打的拼车，一开始我找错地方了，结果这个网约车司机先到了地方，刚到就点了个什么等待倒计时（如果倒计时结束还没上车需要额外收费），这个时候就看得出来这个司机已经很不耐烦了。没办法，我怕司机等太久，就跑着去了上车地点，结果一上车，这个司机就数落我为什么要打拼车，然后我打拼车又赚不到💴巴拉巴拉的，搞得像是我有很大的过错一样，态度极其恶劣。那我也不多说什么了，全程不说话，到了地点我就默默给这个司机打了个差评，也祝愿这个司机早点被平台解雇，你不适合干这行。

到了体育馆，和 jiangly 大佬合了个影，换了个 ucup 的吧唧，然后就进体育馆里了。中午没吃饭，队友帮我点了个午饭，是山药蹄花汤和烧白。不得不说还是我们川渝的饭菜好吃😭，汤鲜，蘸水还比北京的好吃太多了😭。

吃完饭了就差不多开始打热身赛了，拿到题一看全英文心都凉了半截了。

D / T4

队友桑神先开的 D 题，问题是让我们输出去年成都闭幕式的背景音乐。桑神说他去年打过，于是就开始找 bgm 去了。

在我还在写 A 的时候成功找到了，一发过了。

A / T1

在桑神找 D 的时候我看了一眼 A，发现是一眼模拟题，只不过细节有点小多。

写的很快，一会就写完了，但是发现过不了样例。调了半天，好不容易过了样例，交上去发现炸了。

后面一想三种符号的做法应该是一样的，但我单独处理的等号。把大小于号的代码复制改了改放到了等号，随便测了测样例，一交，终于过了。

B / T2

这个题桑神写的，他的想法是一开始算出来 \forall x\in [1, A_n], f(x, n) 的值，然后再根据 m 做一个类似前缀和的东西。

时间复杂度 O(n + m)。

一开始我还没懂是什么意思，就先让桑神写了。后面突然想通了，就帮着桑神看了下他的代码，然后顺便给另一个队友讲了一下。

C / T3

这个题桑神说他之前做过，然后他就开始写了。开这个题的时候已经只剩下半个小时，显然是写不完了，但桑神还是决定试试。很遗憾这个题到最后确实也没写出来。

热身赛结束，榜很快就开了，发现是 91 名（没有暗广！），正好卡在银线上。但鉴于热身赛有 D 题这种不友好题，还有很多队伍没参赛，我就觉得银牌估计有点悬了。

出了体育馆，队友们去听华为的讲座去了，我因为手机没电了就回民宿充了下电，顺便回去看了眼电科给的伴手礼。不得不说成都站给的伴手礼是真不错，不仅有一个电科的纪念品，还给了个本次赛站主题的大鼠标垫。六点左右，他们听完了，还顺便帮我把华为的伴手礼领到了，我也骑车去体育馆和他们会合了。

会合之后，我们和女队约好了，一起去青羊万达吃火锅。由于路途较远，我们去和回都打了个网约车。在路上，我们在聊在🐉🧱上课和学习的一些窍门，还有奖学金巴拉巴拉的，很快就到目的地了。

我们到的早，就先去火锅店取了个号，然后在美团上买了个券，六人餐 360。等了一会，女队也到了，然后大家就在开吃了，顺便交流了一下各自的情况。总的来说，大家吃得很高兴，也相互了解了彼此的情况。

回到酒店，由于第二天就是正式比赛了，收拾收拾洗了个澡就睡了。

在床上翻来覆去睡不着，主要还是担心第二天万一打铁了怎么办，要是拿不到银又怎么办。结果导致当天晚上也没睡好，第二天早上起来头晕状态还不好。

Day 2

早上七点就叫队友们起床去体育馆了。由于带着很多东西，我们最后打了个车去的体育馆。到了体育馆，附近一点早餐店都没有，又怕点到雷了，就只好点了 KFC 当早餐，顺便把美团卡花完了。

行李只能存放在体育馆外面的一个小室里，空间很小，我们来的早，就放的比较里面，放完了就去安检进体育馆坐着了。

本来一开始我不是很想吃早饭，结果队友的外卖到了，发现居然多给了一个汉堡，我就顺便吃了一个。

到了 9 点，比赛还没开始，因为还有很多选手卡在安检，于是晚了 10 分钟开题。9 点 10 分，比赛正式开始，拿出题一看，发现全是英文，没办法那就只有跟榜做了。

G / T7

这题我做的，当 m = 0 时，不难发现 k 的 GCD 为 k，2k 和 3k 的 GCD 为 k，4k 和 5k 的 GCD 为 k，以此类推。然后 m \not= 0 时把不是 k 的倍数的数改成 k 的倍数就行。

时间复杂度 O(1)。

写起来有点恶心，但是其实还好。十分钟写完，调了五分钟，交了，一发就过了。

J / T10

这题也是我写的。题目真的很简单，他说要选出尽可能多的能过通过的论文。显然如果论文本身就能通过，那就不去重评了。然后对于一开始不能通过的论文，去算一下他们重评后的分数，把重评后能过的拿去重评就行了。

时间复杂度 O(nm)。

本质简单模拟题，五分钟写完交了，一发就过了。

A / T1

在我写 G 和 J 的同时桑神在看 A。这个题本质是个推式子题，如果给定了 d%，那么很显然 b 的范围应该为 [d\% - 0.5\%, d\% + 0.5\%)。

如果 \sum d\% - 0.5\%\leq 1 < \sum d\% + 0.5\%，则说明答案存在，否则答案不存在。

构造时，假设所有数都取最大值，然后调整一些数取最小值和一个数取中间值，使得所有数之和恰好为 1 即可。

时间复杂度 O(n)。

写起来细节挺多的。但依靠桑神的细心程度，我们也是一发就过掉了此题。

B / T2

桑神写 A 的同时，我和另一个队友在看 B。一看到 n\leq 6 就感觉大概率需要状压了。考虑用 S 表示上一轮攻击完后有哪些技能上次被使用过了，T 表示下一轮攻击使用了哪些技能，我们就很容易能算出本轮造成的伤害值 A 和本轮的花费值 C。

由于 R\leq 10^9，显然需要使用矩阵快速幂加速 DP 过程，这个题就做完了。但是由于我们当时脑子抽了，没想到矩阵快速幂可以处理 \max 操作，于是我们使用的是倍增优化，其实本质与矩阵快速幂大同小异。

时间复杂度 O(2^{3n}\log R)。

写起来也是一大坨，但是其实还好，我花了二十分钟左右的时间就写完了，又花了大概十分钟进行调试，过样例之后就交了上去，最后还是有惊无险一发就通过了此题。

L / T12

实际上 B 题五分钟就想出来了，在等桑神搓 A 的同时我又同时看了眼 L。实际上 L 也是一眼启发式合并就做完了，但是当时并没细想就写 B 去了。

后来我把 B 写完了之后桑神推了个式子说这个题可以用线段树合并做，是线段树合并的板子，于是桑神就上去写 L 了。

但是桑神写了 45 分钟左右，一直调不出样例，于是我们就让桑神先休息一下，然后我试着把 L 的启发式合并做法写了写。

根据 b_0\geq\sum\max(0, a_i - b_i) 这个表达式，我们在启发式合并的时候维护 a，b 和 \sum\max(0, a_i - b_i) 的值，然后在每个节点判断一下上述不等式是否成立即可。

时间复杂度 O(n\log^2 n)，如果使用 unordered_map 可以降至 O(n\log n)。

思路很简单，写起来就是依托💩。大概花了我 45 分钟的时间才写完 + 调完。但所幸交上去一发就过了。

C / T3

这个题从我们开始写 L 就开始在想了。后面是在封榜后，另一个队友说考虑二分 + 倒着做才想出思路来的。

我们先考虑二分最终答案，然后用最终答案一步步往前推。显然在往前推的过程中，如果对岸有人，就一定从对岸运人过来后再把这边的人运过去。如果在推到某一个人的时候，时间 t 已经小于这个人到达港口的时间了，那就说明二分检查失败。

实际上，通过这样倒着做，我们发现实际上船夫只会有两种运人方案，即最终停留在左岸和最终停留在右岸，暴力找出这两条路径然后正着做，找出最小时间即可。

时间复杂度 O(n\log n)。

但很可惜的是，我们想出这个思路已经只剩 30 分钟了。尽管只花了 15 分钟时间就写完了初版代码，但提交上去毫不意外地 WA 了。最后 15 分钟也没能调出来，只能遗憾收场了。

第二天复盘的时候，才发现忘考虑船夫需要空载回来运同一边的人的情况了。

D / T4

其实桑神在还剩一个小时的时候就想出来这个题的做法了，但鉴于时间不够，再加上这题非常的💩，于是我们都没敢写。

滚榜

在整场比赛中，我们的最高排名其实到了 39 名，封榜前我们排在第 79 名。全程也是一发罚时都没吃，成功来到了 5 题首的位置。

一开始我们和马哥（我们的学生教练）交流的时候，他说我们离银尾线还差 17 名，没有这么多封榜战神，我们的银牌应该是稳了。

结果在滚榜的时候，一堆队伍封榜后哗哗过题，我们也是从 79 名被硬生生挤到了 103 名，来到了铜首的位置，遗憾错失🐉🧱近代 ACM 史上的第一块银牌。

赛后

铜牌拿到后，我们就离开赛场了。由于成都离我家挺近，我的家长就从重庆开车过来和我聚了一下。晚上一起吃完饭过后，我就自己开车去了天府机场。

值机流程和来的时候是一样的，就不多赘述了。天府机场很有特色的一点是天府机场登机不用登机牌，直接扫脸登机即可。

到了大兴机场，由于是晚上十二点半才到的大兴，近机位没地停，就给我们拉到远机位，然后用摆渡车拉过去的。

本来想坐大兴机场夜班巴士然后坐夜间公交回去的，结果一问夜班巴士价格，50！这比大兴机场线还贵！后面发现可以花 35 坐到北京南，一想到直接打车回去的话得花 200，没办法，最后还是妥协了，坐到了北京南。

到了北京南，本来想坐夜间公交回去，结果夜间公交比我们提早 4 分钟离站，下一班估计还要 36 分钟才能发车。加上当时北京晚上又冷，没办法，最后还是打了个网约车。这次打的网约车还挺便宜，42 块就给我拉回了学校，并且司机的态度非常好，还帮我拉行李之类的。

回到学校已经是半夜三点了，也是体验了一番凌晨三点的北京。

总结

总的来说，这次成都站留下了很深的遗憾，如果能把 C 赛时过掉，就能稳稳拿到🐉🧱近代 ACM 史上的第一块银牌。不过虽然没能拿到银牌，拿到的铜首离银牌也已经不远了。

还是自身实力不够导致的，只有在后续的武汉站和哈尔滨站再接再厉了。