作者paae0226 (paae0226)
看板Prob_Solve
标题[问题] ICPC 4000
时间Wed May 22 23:51:51 2013
Link:
http://ppt.cc/hM-J
有编号 1 到 N 的球排成一圈
允许一 operation 为任抓连续 4 颗球反转顺序 (头尾对调，中间两个对调)
input 一个打乱的顺序 (顺时钟方向)
问有没有办法利用这个 operation 把它们变成从 1 开始顺时钟看过去
刚好是 1 到 N 的顺序
Constraints: 8 <= N <= 500
--------------------
本来乱猜直接拿 inversion pairs 个数的奇偶来判断
但是画一画有反例
想请大家提供一点提示 QQ
感谢
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.251.209.41
1F：推 sxman:这有玩具 可以玩XD 他其实可以greedy解 最後会分成几种case 05/23 11:08
2F：→ sxman:每个case 在个个击破就好 05/23 11:08
3F：→ paae0226:不好意思我有点不太懂 @@ greedy 解指的是什麽呢 05/23 18:27
4F：→ paae0226:是用某种走法把盘面简化到一定程度之後再做判断吗 05/23 18:29
5F：推 UncleHS:greedy是只比如说先把1换到最左边 再接下去换嘛？ 05/24 23:57