【题解】2020牛客NOIP赛前集训营-普及组（第二场）

总结

T2 初始题意有点问题，但是一开始就看到很多选手 AC，所以我就以为这个题没锅。后来仔细读了一下才发现会有一些奇怪的情况，这才改了题面，消除误解。赛前以为只是个简单签到，就没有多想这个题，实在抱歉。

T3 一些人没有拿满分，是忽略了 m<2 的情况，这时候还没有开除绩效拿 C 的人，最终答案要加上这些人。

A 面试

按题意模拟即可

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263530

B 纸牌游戏

如果当前有 Q 个人，且每个人的 都大于等于 Q-1，那么他们每个人都可以从其他所有人手中拿一张牌，游戏可以无限的进行下去。反之，若其中至少有一个人的 小于 Q-1，那么其他人可以一起拿他的牌，一轮下来他就会减少 Q-1 张牌，而他又只能补充 张牌，几个回合之后他就会被淘汰出局。充分必要性得证。

根据上述结论，先对 排序，然后枚举 Q 即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263525

C 调薪

由贪心可知，绩效得 C 的人一定是初始薪资最少的人。其他人的薪资都 *2 或 *3，他即使被开除也无所谓。

其他人的薪资用快速幂算出即可。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263521

D 变换

20pt

两个数字一定是变为它们的 gcd，求一下它们到 gcd 需要几次操作即可

40pt

如果可以发现“将所有数字变小直至相等”的效果等同于“将数字变大直至相等”，那么可以枚举最终的数字

或者进行一些 dfs 乱搞

另外 20pt

值域很小时，最终变成的数字 Q 的范围也会很小，我们可以枚举 Q 的范围+剪枝，然后看看其他数字变成 Q 需要几次操作。

D 变换

20pt

两个数字一定是变为它们的 gcd，求一下它们到 gcd 需要几次操作即可

40pt

可以枚举最终的数字

或者进行一些 dfs 乱搞

另外 20pt

值域很小时，最终变成的数字 Q 的范围也会很小，我们可以枚举 Q 的范围+剪枝，然后看看其他数字变成 Q 需要几次操作。

100pt

将一个数字不变，其他数字乘 x，等价于其他数字不变，这个数字除以 x，其中 x 为这个数字的一个素因子。

题目等价于每次可以将一个数字除以 x（x为其素因子），问多少次可以将所有数字全部变成一样的。

易得，我们将所有数字都变成他们的 gcd 就行了，我们求出所有数字的 gcd，让所有数字都除以 gcd，然后再算出所有数字的素因子个数和即可。

可以对上述操作进行一些优化或者预处理，使之能够通过全部数据。

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=45263514