NOIP2025模拟赛6总结

· · 个人记录

NOIP2025模拟赛6总结

T1

数论题。

部分分$ x_1 - x_2 = 1 $又有什么用呢？ 想到同底数幂的乘除法，可以用类似$ exgcd $的方法去减少指数。 而$ gcd(x_1, x_2) = 1 $就说明最后指数一定可以变为$ 0 $和$ 1 $。 然后就过了。 ### $T2

还是数论题。

看着很像 CRT ，好像还是 EXCRT 。

但是 CRT 我都不会，不过可能和这个没太大关系。

要求最小的正整数解，这该怎么做呢？

列了一下样例，没发现什么规律，于是就跳了。

最后打了 5 分。

正解是：

当 x \lt lcm(m_i) 时， x 就一定是最小的正整数解。

$ tp_i $表示选了$ n $个数字，其$ lcm $恰好是$ i $的方案数。 那么显然，$ dp_i $就是$ tp_i $的狄利克雷前缀和，直接反过来搞定即可。

T3

图论，加边。

想到如果有一个合法的环，如果在环上加一条边，一定不合法。

于是想到缩点，动态维护这颗树。

好像会 60 分了。

发现好像如果路径中有一点为缩过的点，一定不行。

然后开打，调了很长时间大样例后发现，假了。

可能在环上一点到连在该点的链上一点连边可能合法。

然后就放弃了。

正解是离线下来，先按时间顺序建生成树。

对于其它边，考虑路径上的异或值，再考虑标记边。

具体来说，可以设一个数组，表示从根到该点所经过的标记边的个数。

然后用 dfs 序和树状数组维护即可。

T4

数学期望。

赛时没思路，感觉不可做，非常复杂。

正解：

先考虑 k=0 。

若第一个人失败，那下一个人要么用上一个人的钥匙开其它锁，要么用其它钥匙开这个锁。

再考虑 k≠0 。

决策依然类似，变化在于你的钥匙可能是假钥匙，转移有变。

最后再前缀和优化一下就好。

用时两个下午加两个晚上，终于过了。