主页
搜索
最近更新
数据统计
赞助我们
系统公告
1
/
1
请查看完所有公告
[NOIP2020] 移球游戏
最后更新于 2025-06-15 14:49:21
作者
WeLikeStudying
分类
个人记录
复制 Markdown
查看原文
更新内容
- 这题对我来说可以说尤其地困难啊！ - 感谢[奆佬](https://www.luogu.com.cn/user/58543)对我探究性学习的指导和帮助，我也要尽力避免思维的死胡同，寻求契机。  **[题意](https://www.luogu.com.cn/problem/P7115)** - 有 $n$ 种颜色的球，每种各 $m$ 个混乱地放在 $n$ 个架子上，你可以利用 $n+1$ 个架子（一开始空着），每个架子最多可以放 $m$ 个球。 - 你的操作是：将架子顶上的一个球放在另一个架子的顶上。 - 在 $n\le 50,m\le 400$ 的情况下，你只能操作不超过 $8.2\times 10^5$ 次。 **分析** - 你会做 $n=2$ 的情况嘛，反正我一开始是不会做的。 - 但是这并不妨碍我们胡思乱想啊，比如说，如果能够把球用线性次操作大致均分成两类，那么就可以用分治的做法，用线性对数的时间完成这个问题。 - 那么怎么做 $n=2$ 呢？我们观察题目给的第二个大样例，发现它实现了一个简单明显的做法： - 对于 $1,2,3$ 号架子，我们将 $2$ 号架架顶与一号架中黑球等量的球移到三号顶，那么就可以将一号架中黑球与白球分离到 $2,3$ 号架顶，此时一号架空，将 $2,3$ 号架顶中先黑球后白球移到 $1$ 号架，再将 $2$ 号架中剩余的球移到 $3$ 号架，再将 $1$ 号架中白球转移到二号架，最终彻底实现黑球和白球的分离。 - 对于分治做法，可以采用类似这样的实现，不过每次只能够将一个架子上的球恢复有序，那就是多的那个，[代码](https://www.luogu.com.cn/paste/xlhrcsxf)。
正在渲染内容...
点赞
0
收藏
0
