竞赛讨论区 > 【题解】2020牛客NOIP赛前集训营-普及组(第二场)

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

头像
鸡尾酒QAQ
编辑于 2020-10-21 20:30:40 APP内打开
赞 7 | 收藏 1 | 回复3 | 浏览1635

总结

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

3条回帖

回帖
加载中...
话题 回帖

近期热帖

等你来战

查看全部

热门推荐