NOIP2025模拟赛6总结

$NOIP2025$ 模拟赛6总结

$T1$

数论题。

gcd(x_1, x_2) = 1

有什么用呢？

部分分

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$ 就一定是最小的正整数解。

$dp_i$ 表示选了 $n$ 个数字，其 $lcm$ 是 $i$ 的约数的方案数。

$tp_i$ 表示选了 $n$ 个数字，其 $lcm$ 恰好是 $i$ 的方案数。

那么显然， $dp_i$ 就是 $tp_i$ 的狄利克雷前缀和，直接反过来搞定即可。

$T3$

图论，加边。

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

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

好像会

60

分了。

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

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

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

然后就放弃了。

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

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

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

然后用

dfs

序和树状数组维护即可。

$T4$

数学期望。

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

正解：

先考虑

k=0

。

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

再考虑

k≠0

。

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

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

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

NOIP2025模拟赛6总结

文章操作