2026–2027 赛季

ICPC 网络预选赛1 26/9/6#

6题总排校2 没发挥出来

9题总排192 校2 感觉还挺成功的

依旧开局吴神坐队长机。

三人一起先浏览一下所有题的名字，感觉N名字就很签到，𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 写完就过了。

我又从A开始看，发现 B 很简单。写了个5重循环，结果WA了。又仔细想了一分钟，发现有种情况没考虑到，改了以后过了。

我写 B 的时候，吴神说 I 会了，是个猜猜题。她给 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 讲了一遍，在我写完 B 之后 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 2分钟写完，过了。

我和 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 去看 E ，她看出个结论，给我说了一遍，我觉得没问题，现在要解决如何快速判断两个集合相等。我说可以哈希，每个原序列的数对应一个值，异或起来作为集合的值，两个集合值相等即相同。她上去写了一发，段错误，发现数组开小了，改了以后过了。

然后我去看 H ，看一眼就会了，可以构造使得原序列的逆序对的奇偶性和其他序列的不一样，给 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 说了一下，然后她去写了。她一开始写得有点一坨，我看了一会也没看明白哪里不太对，她调了一会过了。

这里赛后发现 H 想麻烦了，有很多更简单的做法。

我们观察了一下榜，发现 K M J 比较多通过。我看了看 M ，感觉没有什么很好的想法，于是又去看 K ，发现 K 其实不难，都是我会的东西组合一下。吴神说 J 她有个比较暴力的东西，和我讨论了一下，正确性肯定没问题，就是复杂度有点迷，我觉得会 TLE 。

吴神上机写了一会 J ，然后她下机让我去先写 K 。K 是个 DAG + 期望 DP 什么的，我先建反图，又把 Dijkstra 板子抄上，然后写了个拓扑排序。写完发现不过样例，原来是题意读错了，又维护了个最短路计数，交一发过了。

我写 K 的时候能听见吴神和 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 一直在讨论 M ，听起来真得很头晕，组合数什么的，好像是有个式子不会化简（？）。

这时6题，但是总排和校排都比较倒闭。吴神去写 J ，我去和 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 看 M 。我发现卡住的这个式子我会化简：

$\sum_{i=0}^{n}\binom{n}{i}\binom{m}{i}=\sum_{i=0}^{n}\binom{n}{n-i}\binom{m}{i}=\binom{n+m}{n}$

用生成函数可以直接算。或者可以从组合数的角度理解一下：从 $$n$$ 个物品中选 $$n-i$$ 个，再从 $$m$$ 个物品中选 $$i$$ 个，枚举 $$i$$ ，总方案数就是从 $$n+m$$ 个物品中选取 $$n$$ 个。

然后 𝙿𝚘𝚖𝚎𝚕𝚘𝚛𝚒𝚗 给我说了一下已有的思路，把数组去重排序以后用双指针扫，但是得讨论一下子序列长度的奇偶性。想得差不多以后我

写完交了一发结果又 WA 了，我又仔细想了想，感觉刚才改动的这一步还不是完全正确。