2024 ICPC区域赛上海 游记

Day.0 热身赛

0.

上海站的行程是最紧的，当天中午飞机落地，就要立刻去赛场签到，然后是热身赛。紧接着第二天比完赛闭幕式估计都来不及就要返回机场。来的飞机还因为天气原因晚点了40分钟，但直到前一天晚上11点才发布消息，所以我直到早上4点半起床时才知道晚点。本来因为没睡好就会头晕，到机场的路上还有点晕车，差点就撑不住了。基本到飞机上还没起飞就开始睡，落地以后已经是中午。从浦东到宝山也要1h左右，领队老师简单请吃了午饭后，就去酒店入住，等到终于可以签到时，开幕式和裁判讲话应该是已经结束了，直接就进场热身赛了。
上海站早上发了fufu和warma挂件什么的，在路上看到了群里的热烈讨论，等我们到了果不其然已经一件不留。不过发的外套感觉质量还不错，上海大学也很慷慨的发了60元临时校园卡，决定不在食堂吃晚饭的我们最终把钱都花在了超市买零食和饮料。
晚饭在上海大学附近转了转，吃了小杨生煎，然后发现我有点不会吃生煎，不过味道还是很好的。之后照常在校园里面散了散步。不过不同于成都站的松弛，上海站的行程可能实在是太累了，穿过校园看了看就坐地铁回宾馆了。不得不说允许共享单车进入校园之后真的到处都是共享单车，同时再一次感叹我们学校真是楼挤楼的设计。

A.

基本上是队友过的，我看了题意。主要是发现n只有500，而对于操作3最多进行30次，所以序列变为相同时变为的数实际上是可以枚举出的。

*B.

赛场未过。数论题，本质上不难。结论很快就推出来了到解决奇数偶数分配的形式，然后误以为两个线性相关的方程（其实本质上是一个方程）是两个不同的方程，试图解出答案时发现除0RE才发现错误。最后试图发现实际上可以是exgcd，然后抄了板子还是WA了，细节上实现可能有问题，但是是热身赛而且也到时间了所以就没太改了。

C.

应该是最简单的一道签到题。我们看了A之后看榜就开始看了，很快就发现了结论就是计数相差1的下降子序列个数，顺利AC。

D.

应该属于诈骗签到题。注意到进位的次数实际上与加法的操作顺序无关，直接都加起来即可。

Day.1 正式赛

0.

遗憾打铁。明显感觉上海站的题目压力比之前大了很多。前期签到题出师不利导致心态影响，多少也导致了后面实现上出现很多问题，封榜前过掉的两道签到题成了最后的通过。虽然参赛方发了看起来还不错的食物，可惜完全没有心思吃。到后期手上有3道题目BDG，如果算上已经通过的IC其实成绩是很不错的。无奈D的构造后面来看出现问题而没时间检查，B和G的思路也均正确。还是策略和时间的问题。

C.

结论博弈论题。前面是队友在看，推了几个小结论。后来我发现两人各自倍数固定，于是就想贪心拿自己对应的倍数和对方对应的倍数，但是贪心策略还是很难出。后来决定暂时放下I后，队友来看C，发现可以通过堵死后方的奇数来构造必胜策略。于是直接判断区间内最小奇数的二倍是否在区间内即可。

I.

最简单的签到。实际上也是跟榜本场最先看的题，先是队友在看然后写实现，我看了之后是发现就是乘法分配律所以直接贪心选即可，结果实现WA了。查了包括什么数组越界什么爆int（都不该出现因为数组开得很大而且define int long long），还改了初值未取模结果还是WA。我上机造了好几组数据也没有构造出hack。连续WA了几发后我们决定暂且放下此题去看C。后来C过掉之后队友发现是数据可能取模下毒，我们的实现判定过程中为0则视为全局为0，数据范围大于模数，如果给到刚好模数的数据就会被卡。赛后发现好多人卡这题，还有很多人被这道题机翻的英文题面硬控，由于其用了一大段来说明答案需要取模，导致很多人没看明白以为是要求取模后的最大值（我们队连续WA以后也一度认为题意有误）。

*B.

赛场未过。其实是实现模拟题。直接按题意模拟dfs，如果找不着就建边。队友先去写的版本是特别注意了不连通的时候，如果一个连通块被遍历完，那么可以任意地找下一个连通块。但是这个版本比较不好写，我们想了用并查集甚至我还想要不要上Tarjan，不过最终这些都没有用上。在实现过程中我发现其实根本不用那么麻烦的判定什么连通块，直接建立一个超级源点即可，不过我说了之后并不能解释为什么现在的版本过不了样例，而且发现错误点应该是在遍历完一个节点的儿子之后返回的阶段，由于我完全是只习惯链式前向星，所以看队友 vector存图的代码也看不出来什么。期间队友还上去写了第二个版本，这个版本赛后发现离AC就差少写了一行，当时后期不断的轮换人写D和B，不同的B的两个版本也是改来改去。队友的第一版判定方式是动态修改度数，最后我们换了一个等价的写法，删去几行之后惊讶发现竟然从WA变成了RE，到最后也不知道是什么原因。后来也发现我们想法和题解完全一样，只是实现有误差。

*D.

赛场未过。构造题。我们首先发现了靠00分块，如果串包含00，则00前面的子串无意义。然后我们接着考虑无00后缀，发现长度大于等于5必有解。之后就是在长度4的时候枚举，不过这里枚举错了没想到1可以往回拉。正解是“粘性活塞”，感觉是很精妙的理解方式。

*G.

赛场未过。我们看榜后先的看G再看的D，然而D看起来实现容易一些，导致即使手里有了正确的G的思路，封榜后的一小时也选择了优先开D而不是G，如果策略是一小时时暂时放弃B和D的话过掉G再修B说不定还是很有希望的。我们看到最大化中位数首先想到是二分答案，中位数仅需有n/2小于它。n/2大于它即可。check函数里的话，队友一开始的想法是把x解出，得到若干对于x的约束条件，把这些条件也进行一个二分看看哪些在一侧的n/2，哪些在另一侧的n/2。但是时间复杂度很大，感觉疑似过不了于是并未第一时间开写，而且疑似在check函数的二分中思路里出现了一些错误，于是继续去在D和B之间反复横跳了。后来队友想到了一个用二分套优先队列的优化方法，并没有来得及实现。赛后发现写的是可以AC的。