作者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