ICPC 50th 区域赛（武汉）游记

· · 生活·游记

ICPC 50th 区域赛（武汉）游记

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

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

Day -1

这次要去武汉大学，从网上买了五把痒痒挠在武大去发。

今天下午由于是晚上八点半的车，不急，于是上完了最后一节复变函数与积分变换再走的。

由于🐉🧱不给报销差旅，那就只有能省一点是一点了，这次选择坐的 10 个小时的动车卧铺去的武汉，在车上睡一觉，起来就到武汉了，还省了一天的住宿费。

上车后才发现，D37 上好多从北京去武汉打 xcpc 的群友，可惜本人是社恐，没敢去和群友面基。

Day 1

早上 7 点左右到了汉口站，出站后拍了个照就去坐地铁了。武汉地铁也是真贵啊，坐了不到一个小时花了我 6 块钱😡。

出地铁了，早就听闻武汉有着“红绿灯可以挑一个自己喜欢的走”的传闻，再武大门口的十字路口，挑了个最喜欢的红灯走，还好没被车创。

八点十分左右到的武大，在计算机学院签到领资料的时候等了半天，才把物资拿到了。这次的物资没有成都的给的好，就一帆布包和一个蒜鸟玩偶，衣服还得自己报尺码然后去拿。

在计算机学院又有非凸的活动，8 点半开始的，我一开始就去玩了投沙包，结果最后还是拿了个小 fufu，与大 fufu 就差五分。然后去华为那里抽了个奖，结果啥都没有（华为是真 tm 抠门啊）。

在计算机学院还看到了若叶睦的 coser 和一个很好看的男娘小姐姐，也找他们集到邮了（开心o(￣▽￣)ブ），还和很多群友互换了吧唧，痒痒挠也发了三把出去。

没啥事干了就出校吃早饭去了，大概 9 点过的样子。在群友们推荐的蔡明纬吃了武汉特色热干面和面窝，面窝不错，热干面也挺好的，可惜我不吃麻酱所以不太能吃得惯。

吃完早餐就回去了，等到队友在武大的同学下课了就去武大食堂了。不得不说，武大食堂（指定的）离计算机学院是真远，去过一次我是肯定不会想去第二次了。

在学三食堂吃了个猪扒咖喱蛋包饭，非常一般，一股很重的预制菜的感觉，还花了我 17 的餐券，剩的 8 块拿去买了两杯绿豆汤。食堂里有个奶茶店，排了巨长的队，本来说高低想试试的，结果听说至少要排半个小时的队，那不排了。

在食堂还和学弟面了个基，给了他一个吧唧，聊了聊然后就到酒店办入住了。

办完入住，休息了一下，就到体育馆准备打热身赛了。热身赛给了中文题面，这点好评。

A / T1

简单多测 A + B 问题，不多赘述。

由于我的另一个队友是大一新生，就让他上来练习敲代码了，我就没有动手。

B / T2

构造题，不难注意到，按照 1, 2, 3, ..., m, m + 2, m + 3, ..., 2m, m + 1 这样的构造方法能够通过此题。

官方答案是按照副对角线的方法一点一点填，这样也是可以的。

时间复杂度 O(n^2)。

C / T3

交互题，不难注意到，我们可以通过询问 + 0, + 0，+ 0, + 1，+ 1, + 0 三次来判断两个数最后一位的奇偶性。

然后以此类推，从最后一位开始逐步询问出两个数每一个二进制位上的值，总共花费约 180 次询问操作。

D / T4

应该是 ICPC 49th 昆明区域赛原题，鉴于当时场上只过了 5 个队，于是我们也没深究了。

当时做完热身赛，一看三个有效题目居然有两个构造题（交互也算是一种构造），又听说黑冰茶最喜欢出构造题，再加上热身赛两个构造题几乎都不是我想出来的，我就感觉第二天的比赛估计很坐牢了。

热身赛不想打了之后，我们就出去把签到时没拍的照拍了，然后就和桑神吃饭去了。

我们选择吃的是武汉特色黑鸭煲，味道怎么说呢，感觉和周黑鸭就是一个味道，不过那家店的炸土豆条不错。

吃完了回去体验了一把武汉公交车，只能说武汉公交的名声不是吹的，两个站让我体验了陆地飞行器的感觉，甚至比重庆出租车还猛。

回到酒店玩了会手机就休息了。

Day 2

今天正赛，早上七点半就起来了，洗漱完收拾箱子就退了房，然后去昨天早上吃的蔡明纬去吃早餐。这次点了一份三鲜豆皮和一碗蛋酒，三鲜豆皮吃是好吃，但是油太大了很腻，蛋酒好喝。

吃完饭了就从珞珈门进去准备进体育馆了，原以为已经可以进去了，结果主办说要 9 点才能进，不得不在外面坐了十几分钟。

进体育馆之后，拿出棉花娃娃，坐着休息了几分钟，就开始比赛了。

F / T6

这题是桑神写的，不难发现，如果一个区间能包含另一个更小的区间，那么这个区间可以省略不考虑。去掉所有这种区间后剩下的就只有收尾相交的区间了，暴力决策如果这个区间没有被处理过，就在区间尾的位置处理这个区间。将各点连成一棵类似二叉树的结构，得到的就是最小层数。

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

一开始这个题我并没有看懂什么意思，差点还把队友给误导了🥹。

E / T5

这题巨 tm 恶心，纯结论题。

手玩一下你就会发现下面的结论：

综上，对于一个序列，我们先统计奇偶数字的个数。如果一开始就存在一组 x, x + 1，那么我们可以现根据结论 2 和结论 3 将一对数 2k, 2l + 1 连起来，最后形成的一定是满足结论 2 的长度为偶数的结构 n - 2k, ..., n, n + 1。循环执行上述操作，最后剩下的一定是奇偶性相同的数，再根据结论 4 将他们全部变成同一个数 n + 2，于是我们最后构造出了 n - 2k, ..., n, n + 1, n + 2, ..., n + 2 的结构作为该序列的唯一标识。

因此，对于一个奇偶数的个数为 x 和 n - x 的序列。我们最后可以构造出长度为 2\times\min(x, n - x) 的 n - 2k, ..., n, n + 1，然后后面会跟着长度为 n - 2\times\min(x, n - x) 的 n + 2, ..., n + 2。再简化一下，只要 x 相同，构造出的序列就一定类似。

因此这个题的步骤就出来了。先判断两个序列是否存在 x, x + 1 的结构。如果都不存在，暴力判断是否相等；如果只有一个存在，一定不可能构造成相同序列；如果两个都存在，那么只需要判断奇数个数是否相同即可。

时间复杂度 O(n\log n)（对于第一种情况需要排序）。

这题我们推了一个多小时才真正推出来，实际上实现特别简单。

M / T13

这题也巨 tm 恶心，纯结论题。

不难注意到下面的行列式的值为 \sum a_i + 1：

\left| \begin{array}{ccc} a_1 + 1 & a_1 & \cdots & a_1 \\ a_2 & a_2 + 1 & \cdots & a_2 \\ \vdots & \vdots & \ddots & \vdots \\ a_n & a_n & \cdots & a_n + 1 \end{array} \right|

于是我们直接根据题目给出的 a_n 构造上述行列式就可以通过了。n\leq 18 的范围是给 Special Judge 使用的。

记得 \mod 998244353。

这题是桑神给的一个猜测，在我验证了 n = 1，n = 2 和 n = 3 都满足时就觉得应该就是这个了，写一发果然就过了。

C / T3

又是 tm 的构造题😅。

我们强制让 m 为 3 的倍数，如果不是，交换 n, m 的值。

手玩一下，对于 n = 3 的情况，你可以构造出以下循环节为 6 的样例满足条件：

011220|011220|...
102102|102102|...
220011|220011|...

然后对于 n = 6 的情况，只需要在上述基础上将上述样例上下翻转贴在下面即可，那么对于所有 n = 3k 的情况我们就做完了。

对于 n \not= 3k 的情况，对于前 \lfloor\cfrac{n}{3}\rfloor\times 3 行，按照上述构造方法进行构造。保证最后三行为 n = 3 的情况所示，如果不是，则对前 \lfloor\cfrac{n}{3}\rfloor\times 3 上下翻转后得到的最后三行就是 n = 3 的情况。接下来分类讨论：

接下来特判特殊情况：

于是这个题就做完了，写起来就是一大坨。要注意这个题输出没有空格！（有铸币因为擅自加空格吃了一发罚时）。

花了一个多小时写，吃了 3 发罚时，但还好在 259 分钟过了。写到最后我甚至手都有点软了，生怕还过不了，但看到 Correct 的那一刻，我悬着的心就放下了。

滚榜

259 分钟把 C 过了之后，HK 两个题一点想法也没有，其他的更开不了，没事干了，就看了看各队的队名以及评测队列（我们就坐在主席台下）。原神启动队在最后几分钟疯狂交题，赛后听说用了脚本交的，一看居然交了 103 发。

我们最后几分钟多交了几发 C，吓了一下正在看榜的同学和教练，还把其他没写的题都交了一遍。

考完了先去找学弟交流了一下，然后一起到计算机学院拍了个照。他说他们应该铁了（因为他们只过了 3 题），然后收拾东西就走了。

滚榜，不出意外还是铜了，看了眼学弟所在的队，遗憾的是他们成为了铁首，只差一名就可以拿铜了。我还注意了一下，如果我们没把 C 冲出来，我们最后也只会是铁首。

这套题有趣的是，我们在正式排名中排名 193，与哈工大一队排名只差 5 名，罚时只差 14 分钟。也就是说我们要是少吃一发罚时甚至比哈工大一队排名还高，这也能看出来这套题的个人差巨大，如果对不上脑电波就真完蛋了。

拿到铜牌后，按照惯例，我们三个人在计算机学院门口拍了个合影，然后就各自散了。

赛后

群友说武大第一炒酸奶好吃，我就顺路过去试了试，确实不错，然后就出发去华科找高中同学了。

再次感叹武汉公交车太猛了，50 分钟的车程直接给我干晕车了。

下了车，高中同学就带我去江汉路逛了逛，然后逛了一下二次元圣地 X118，喝了杯奶茶，然后一起吃了个晚饭。他说他晚上还有宵禁，就先打车走了，我由于是晚上 11 点半的火车，还早，就在江汉路逛了一会，大概十点左右就坐地铁去武昌站等火车了。

上了火车，发现和以前比较不同的是，我买的是绿皮车，但硬卧车厢和动车非常相似，一看，是呼局的车，那就见怪不怪了。

上车发完动态，突然有另一个学弟联系我说他就在武大读书，这时我才想起来好像确实是有这么一回事😥。但是上都上火车了，只能遗憾离场了。

总结

这套题广为诟病，构造题数量太多，个人差太大，如果对不上出题人的脑电波那就做不了。也正因如此，有很多强校强队最后坠入铜银。本场比赛，也侧面反映出我们练习的构造题太少了，如果我们能够训练足够多的构造题，成为 CF 大佬，那么我认为拿到银牌应该是没问题的。

下周就要打 CCPC 哈尔滨了，听说强度很低，希望能拿到第一块银牌吧🤗。