The 2023 ICPC Asia Hangzhou Regional Contest-526互联

写在前面
赛时
赛后
写在最后

写在前面

赛时题目按照过题顺序排序，赛后补题按照个人向难度排序。

虽然补题大概要拖到期末之后了。

这学期确实是超负荷了，现在脑子里一团糟，赛时的记忆已经不太清楚了。

省流版：搏一搏单车变摩托，但是怂了。

赛时

M

开局我正开，有中文题面好评。

过了十几分钟发现 M 过了挺多，于是 Nebulyu 拉我来讨论一波，先出了一个假做法挂了一发。

期间 dztle 也加入了讨论，发现可以从给的数列两端依次删数来调整达到最值，优先队列实现即可，三十分钟的时候才过，属于是非常恶劣的开局。

J

在 Nebulyu 写 M 的期间我和 dztle 一直在推 D 但是没出来。Nebulyu 下机看了一下发现用 0 就能很傻逼地凑出来了，甚喜，交了一发发现挂了。又看了眼题发现是不能有 0，三个人一个也没看见，属于是非常低级的错误。

然后 Nebulyu 就去推 D 了，我和 dztle 一块想 J 的交互，发现能确定一条边的存在，再用三次操作就做完了，正好题目限制交互次数不超过 \(\left\lceil\frac{n}{2}\right\rceil + 3\) 次，感觉很有戏。一开始想了个随机算法，随机 \(\left\lceil\frac{n}{2}\right\rceil\) 条边检查是否存在，推了下成功的概率感觉很可行，于是开写开调，过样例交了一发但是挂了。

然后发现题目里说交互器是自适应的，上面那个随机算法的成功概率是在交互器不捣乱情况下才成立的，一时不知所措。突然 dztle 灵光一闪，直接检查所有边 \((2\times k-1, 2\times k) k\in \mathbf{N}^+\) 就行了，因为这样能保证枚举到所有节点，如果是菊花的话这些边中有且仅有一条是存在的，否则肯定是链。于是开写开调，过样例交了一发但是挂了。我去看了一眼发现多打了个等号，又检查了十几分钟交了一发过了，属于是非常低级的错误。

D

时间回到 Nebulyu 写 M 我和 dztle 推 D 的时候。

首先我看到第二个式子一堆乘号，于是想到这玩意乘起来会 tama 的超级大于是这一坨应该都是 1，按照这个思路推了一下发现不太行。

D 挂了一发 Nebulyu 下机之后我告诉了他这个思路，于是他继续按照这个思路推，发现这东西可以化成一个方程的样子，但是推了推发现只能解决 \(n\) 为奇数的某些情况，没什么通用性，于是只得放弃考虑其他思路。

J 过了之后 dztle 下机也按照这个思路推了一下，发现推出来一个很简单的东西。告诉 Nebulyu 之后一开始还很吃惊因为这条路一开始没走通，讨论了下之后发现确实是对的，迷惑！于是上机写了一发过了，感觉莫名奇妙，令人感慨。

这期间我在干什么呢？我推不出来 D 于是就去把 G 开了呃呃。

G

在 Nebulyu 推 D dztle 写 J 的时候我去开了 G，因为有断尾的操作感觉像是个需要大力优化状态的难写的 bfs。

手玩了下大胆猜了个结论，可以把先断尾再移动使得不撞到自己身子，等价成到自己这节身子的距离不小于断的只剩这节身子的断尾次数，于是在 bfs 的过程中要到自己身子的时候对距离取个最大值就行，感觉对的一批。

然后 Nebulyu 上去把 D 写完了，下来之后跟他讨论了下也感觉这个思路对的一批，于是上机开写。

写的过程中觉得只是 bfs 的话可能会挂于是改成了优先队列但复杂度也是对的，一发过了，本场最舒服的一题。

H

在我写 G 的时候决定继续跟榜开 H。

Nebulyu 和 dztle 发现这东西是个基环内向森林，如果只是棵树的话是非常好做的，有一个简单 DP，但是有环出现自身依赖的时候会比较麻烦。

在想怎么断环的时候 Nebulyu 灵光一闪发现由于有严格小于的限制，这个环里面肯定有某些边是无用的，即这些边代表的操作是绝对无法成立的。于是可以考虑直接把这些边断掉，把环分成若干条链分别考虑，处理完环之后再处理环上连的树。

于是开写开调，一发过了，本场第二舒服的题。

H 之后的一个半小时

看了看榜，除掉打星八十多名，和合肥一样。

是了，我们现在已经稳银了。

是了，再过一题是非常有望冲金的了。

是了，所以要再过哪题呢？

在我写 G 的时候 dztle 看了 A 发现非常可做，就是个大力分类讨论模拟但是难写，看了下榜发现就过了一个所以没敢上机。

在 Nebulyu 写 H 的时候和 dztle 讨论了下 E 和 F 都没有明确的做法，难受。

Nebulyu 下机之后看了下 F，出了一个树分块的带根号的写法，因为这时候 A 还是没什么人过不敢写，觉得也没什么事儿干了还剩一个小时写一发 F 说不定能过，于是上机开写。然而用换根写完调完预处理的一半就还剩 20min 了，寄。

这个时候一直把 dztle 晾在一边挂机，把会了的题放在一边来写复杂度假的东西，可谓是非常可悲的失败。

唉。

赛后

咕咕咕咕~

写在最后

然后是谢罪环节。这场从各种意义上都是打得稀烂，最后能把 5 题凑出来守银也算是谢天谢地了。

开局状态很垃圾，卡签到题上卡太久了呃呃，D 没看限制硬送一发，J 多打一个等号硬送一发，快两个小时才把所有签到签完。
中期两个银牌题过得还不是太烂，都是直接想到正解调了调一发过了没掉到铜区，谢天谢地。
后面还剩一个半小时，A 的思路从三个小时的时候就已经出来了，而且复杂度也是对的，但是难写，而且当时只有一个队过了这题，于是宁愿跟榜做 F 写带根号的算法也不敢写，从赛后来看是非常失败的决定。

虽然对于我个人来说，因为有合肥时看了一眼 K 没人过于是转头写 G 赛后发现 K 确实是牛逼题的经历，这次赛时选择一直跟榜倒也是正常的。

dztle 说的对，因为金牌区的神仙随便一道金牌题都会写只是先开到哪道的区别，所以金牌题歪榜的概率极大。当时合肥 I 看起来是牛逼题其实只是个大力爆搜剪枝，金牌爷们都去做 B 了所以过的人不多。我们没有稳金的实力，要想冲金只能靠手气运气和胆量了，靠跟榜就只能保证稳定守银罢了。

为什么会变成这样呢？大概是因为我和 Nebulyu 心态被这学期折磨得爆炸了，超负荷运作了，从合肥到杭州这两周基本没训练都在忙各种屁事，这场从一开始就只是打算能保证稳定守个银算了。

唉。

好想死。

另外感觉自己整场除了把 G 切了一直在睡大觉屁用没有，太废物了，已紫砂。