2023 杭州站 ICPC 现场赛

背景故事

故事的开始

大概在 7-8 月份的时候，得知了杭州站要开的消息，开玩笑的问我的一个退役了好多好多年的同事说，要不要去申请一下当志愿者去玩一下。结果同事说：要不我们申请个外卡名额去玩一场吧

而后，就组成了三个已经退役多年的队伍，甚至已经有人退役了 6 年之久

嗯，就是这样一个没有板子没有脑子没有训练的队伍，甚至没有人会数论，准备参加 2023 的杭州站

开赛前的准备

虽然说都是退役多年，但我最近也一直在刷 codeforces，虽然也就周末写两场 codeforces，而且也是点到为止，不过多深入写题，难题就直接摆烂的那种，毕竟我写题的目的也只是为了消遣

但是我们没有板子，我倒是可以折腾一些板子出来，但是毕竟是一个数论基础为 0 的队伍，得整点数论的板子吧，于是开始找学弟找找我当年的板子去哪了，然后就领到了一份他们多余的纯英文的板子……可惜我英语也不好啊，本来还想让他们帮忙带一份字典之类的

有一个比较重要的插曲就是，这两天恰好是双十二，于是热身赛打到一半，就又回公司去值班双十二了，结果就导致杭师大给我打的 84 块钱一分钱没花

比赛

比赛开始之后就是找签到题，我从 A 题开始看起来的，看了一眼 A 题感觉就是个简单的模拟题，想法是把每一个队伍改到最好或者改到最差两种情况下，金牌队伍有哪些，然后统计就行

直到我看到了样例：TS1

只能说不愧是出题人，还很好的暗示了一下宁理

M

题面

然后就看到开始有人过了 M 题，果断刷了一眼 M 题的题意，发现其实很简单，只需要考虑三种情况就行了

整个数组都要
V 图左边只取最小的，右边取全部
V 图右边只取最小的，左边取全部

然后对这三种情况找最优解就行了

D

题面

很快就发现了 D 题也有很多人过了，于是决定投入一个人去解决，剩下的继续看看别的题

J

题面

然后就两个人去跟榜了 J 题，一开始确实很难有头绪，不过自从有了热身赛的 C 题的经验之后，很快就有一个解决想法：

每两个相邻节点做一次询问，比如 1, 2 询问一下，然后再 3, 4 如此询问
如果都没有边，说明了绝对不可能是菊花
- 毕竟菊花一定有一个点与所有点相连，那么必然在这次遍历中一定会出现菊花中心点和其他点的连接情况询问
如果有任何一条边的情况下，那么就可以考虑一下是否是菊花了（因为我们找到一条边了）
- 随便再找两个点，看看是否和得到的这条边的某个点是否都连接，如果是的话，那么就是菊花
- 如果有任何一个点不是的话，那么就看看另外一个点是否有这个特性
- 如果都没有这个特性，那么就是链

H

题面

H 题队友看了之后表示是一道概率题，大概率是写不出来的，毕竟三个完全不会数论了，加之过的人也不多。所以决定都去刷刷 D 题，看看能不能写出来

研究了一个多小时之后，我放弃了，决定去瞄一眼 H 题看看怎么样。稍微看了一会，感觉好像不是很难，是一道图论题

建图
- 若 A 依赖 B，且当前 A 的糖果比 B 多，但是在 B 获得糖果之后，A 就比 B 少的情况下，建立 B 到 A 的边
- 若 A 依赖 B，且无论 B 是否获得糖果，当前 A 的糖果比 B 多的情况下，将 A 的概率(p)标记为 0
- 若 A 依赖 B，且无论 B 是否获得糖果，当前 A 的糖果比 B 少的情况下，将 A 的概率(p)标记为 1
拓扑遍历所有的点
- 若这个点已经被标记为 0，则不再继续拓扑接下来的节点
- 若这个节点已经被标记为 x，则为其下面的节点的概率(p)标记为 (x+1)

最后，再求解每一个值，为 $(a_i + w_i * \frac{1}{A^p_p}) mod M$

为什么是这样算的：

假定 A 通过和 B 进行比较糖果，才能确定其是否能拿到糖果的场景下

无论 B 是否获得糖果，当前 A 的糖果比 B 多的情况下，那么必然一定拿不到糖果，那么 A 的拿到概率就是 0，那么答案就是 $a_i$
无论 B 是否获得糖果，当前 A 的糖果比 B 少的情况下，那么必然一定拿得到糖果，那么 A 的拿到概率就是 1，那么答案就是 $a_i + w_i$

上面两种情况都挺容易解决的，接下来是剩下的那种情况：B 要是拿到了糖果，那么 A 也可以拿到糖果，否则 A 也拿不到糖果

在这种情况下，我们希望得到的是，让整个随机排列顺序的时候，尽可能让 B 在 A 之前被处理，这样的话，我们就可以得到 A 的概率就是 $\frac{1}{A^2_2}$（这非常容易证明，因为这需要最终排序的结果中，仅出现 B 在 A 前面的排列）
当然，一般依赖也不可能只有那么简单，B 可能也会依赖 C，这个时候 A 的结果就变成了必须要出现 C、B、A 这样的顺序，也就是 $\frac{1}{A^3_3}$
依次类推，可以得到距离最终的根节点有 $x$ 步，则就是 $\frac{1}{A^x_x}$ 的概率
如果成环了怎么办？也非常简单，当真的成环了之后，那么必然环内有一个节点是最终排序后，最先被处理的，那么必然不能拿到糖果，然后其依赖的节点也就拿不到糖果了，也就等于所有人都拿不到糖果了

G

题面

写出 H 后感觉状态大好，看到 G 题也有不少人过了，决定也热热手，稍后再去看 D 题

去了个厕所回来看了一会 G 题，感觉就非常的简单，出题人很巧的把题意隐藏了，实际上是非常简单的题目，可以说是最简单的 BFS 练习题了

这道题最重要的是理解蛇缩短的能力，因为蛇本体会阻碍移动，所以可以通过缩短的方式去“等待”蛇身体离开想要到达的点，然后再走过去

接下来就是要考虑等多久的问题，同时需要注意的是，蛇的每一步移动都是会让蛇往前走一步。即每经过一个时间单位，无论做什么，蛇身就会缩短一节，使得释放出一个格子被允许走到，释放的顺序就是蛇的反向顺序

为什么不用考虑因为额外移动带来新的节点被阻塞的问题：因为新的节点如果被阻塞了，那么必然是已经到达过的节点了，无需重复到达

故可以得到如下结论：蛇身初始所在的每一个格子都有一个基本的费用，其费用等于这个点距离蛇尾巴的蛇上距离，即需要到达这些个节点就必须要满足实际时间大于等于这个基本费用才能到达，其他格子毫无限制，可以直接 bfs 到达，搞个优先队列即可

D

最后还是回到 D 题

最终想到了一个问题，对于 $a_1 \times (a_2 + a_3) \times (a_4 + a_5) \dots$ 这个式子，如果这其中存在两对相加起来的值不为 $1, -1$ 的值的情况下，那么必然就会越乘越大，无法救回来，也难以构造

那么必然，$(a_{x} + a_{x+1})$ 的结果一定是 $1, -1$ 的，或者至少最多只有一个不是！

那么继续构造，如果要满足这种情况下，最简单的就是 $2, -1$ 和 $1, -2$ 这两组了，这个时候，可以得到乘积结果都是在 $2, -2$ 之间了，那么不妨就尽可能相加的结果接近 $0$，这样的情况下，$0 + x = 1 \times x$，这是最优雅的解决方案

所以给出下面的解决方案：

若给出的 $n$ 是奇数，则最开头的两个值是 $1, 1$
若给出的 $n$ 是偶数，则最开头的四个值是 $1, 1, 1, 1$

接下来根据情况进行补充

如果前一个值是 $-2$，那么为了保证下面的和是 $1, -1$ 的话，就必须补充 $1$
如果前一个值是 $2$，那么为了保证下面的和是 $1, -1$ 的话，就必须补充 $-1$
如果前一个值是 $-1$，那么为了保证上面的乘积是 $2/-2$ 的话，就应当看情况补充 $-1,1$，比如之前构造了一个 $2$ 出来，那么就要补充一个 $2$ 来生成一个乘积为 $-2$ 的结果去抵消前一个构造得到的 $2$
如果前一个值是 $1$，那么为了保证上面的乘积是 $2/-2$ 的话，就应当看情况补充 $-1,1$，比如之前构造了一个 $2$ 出来，那么就要补充一个 $-2$ 来生成一个乘积为 $-2$ 的结果去抵消前一个构造得到的 $2$