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。