$2020.04.22$2020.04.22【$NOIP$NOIP普及组】模拟赛$C$C组$28$28 总结

这次比赛考了$150$150分，$22$22名，下次要继续努力！
这次比赛考的是$2009$2009年的$NOIP$NOIP提高组。

第一题：潜伏者

题目

解题方法

直接用桶来模拟。
时间复杂度为$O(|s|)$O(∣s∣)。
注：$s$s表示一条加密信息，$|s|$∣s∣表示$s$s的长度。

得分情况

比赛时$100$100分。

第二题：$Hankson$Hankson 的趣味题

题目

解题方法

对于$50$50分的做法

我们可以知道$x\in[1,b1]$x∈[1,b1]，所以直接枚举判断。
时间复杂度为$O(n\sum_{i=1}^{b1}f(i))$O(n∑i=1b1​f(i))。
注：$f(i)$f(i)表示求最大公约数和最小公倍数的时间复杂度。

对于满分的做法

我们可以知道$b1$b1是$x$x的倍数，也就是$x$x是$b1$b1的因数。
所以我们只用枚举$b1$b1的因数就可以了。
现在提供两种方法：

• 直接枚举$1$1到$\sqrt{b1}$b1​，一次计算两个，这种方法很容易超时，要开$O2$O2才能满分。
• 直接分解质因数，这样显然会快点。

得分情况

比赛时$50$50分。
改题后满分。

第三题：最优贸易

题目

解题方法

这道题直接用动态规划或者$spfa$spfa。

得分情况

比赛时没做。
改题后满分。

第四题：靶形数独

题目

解题方法

直接搜索。
注意细节。

得分情况

还没做呢。