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。
投递去哪儿旅行等公司10个岗位