竞赛讨论区 > 2020牛客NOIP赛前集训营-普及组(第五场)题解
头像
RUSH_D_CAT
编辑于 2020-11-05 16:36
+ 关注

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

题解

T1 购物

  • 做法 1:从小到大枚举买几件商品,判断是否够。
  • 做法 2:当还需要的商品多于 k+1,一定买 k 送一。答案为

T2 交换

收尾粘起来,形成一个环,求最长全 1 区间即可。可以把原序列复制一遍,也可以枚举是否跨过 1.

T3 最小移动

  • 显然平均数 average 不是整数,输出 -1。
  • 从前往后,依次将每个数调整成 average
  • 考虑 [1,i], [i+1,n] 之间移动次数,有 被选择的次数为

T4 飞行棋

设 dp[x] 为从 x 走到 1,期望步数。

  • ,根据样例猜想 ,具体证明
    • 做法 1:列线性方程组
    • 做法 2:每回合有 的概率结束游戏,每回合之间独立,期望为
  • , 可以前缀和优化 dp。

全部评论

(1) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐