趕快加入我們來參與討論吧!
您需要 登錄 才可以下載或查看,沒有帳號?加入我們
x
本帖最後由 domen111 於 2015-3-15 02:29 編輯
problem: http://hoj.twbbs.org/judge/problem/view/255
正解AC: http://hoj.twbbs.org/judge/judge/submission/31447
一開始寫了一個自己覺得會錯的假解,想說上傳看看能騙到幾分,沒想到直接AC! 後來打算要證明那個解法是對的,卻直接被我找到反例,沒想到IOI的測資那麼弱,估計是隨機產的(周強表示會退化成O(n^2)的code還是AC)
想法:
假設數列每一項為a[ i],計算dis[i ]=a[ i]-i
若每一個框段為a[l]~a[r],dis[l]必須等於dis[r]
然後用dis分類
相同的放到同一個vector裡面
做爬行法,用線段樹檢查是否合理,算出框段
用map把不是障礙段的框段刪除
爬行法那邊不太正確,會寫出AC的假解,問了別人之後知道是改成維護單調性就會對了
正解AC code: (希望真的是正解)
[sojcodepad]c6d1233f[/sojcodepad]
幾組debug用不錯的testdata:
[Plain Text] 純文本查看 復制代碼 11
0 10 9 1 3 2 4 7 6 5 8
i: 0 1 2 3 4 5 6 7 8 9 10
a[ i]: 0 10 9 1 3 2 4 7 6 5 8
dis[ i]:0 9 8-2-1-3-2 0-2-4-2
10
0 6 2 4 3 5 8 7 1 9
i: 0 1 2 3 4 5 6 7 8 9
a[ i]: 0 6 2 4 3 5 8 7 1 9
dis[ i]:0 5 0 1-1 0 2 0-7 0
10
0 2 1 4 3 5 8 7 6 9
i: 0 1 2 3 4 5 6 7 8 9
a[ i]: 0 2 1 4 3 5 8 7 6 9
dis[ i]:0 1-1 1-1 0 2 0-2 0
10
0 3 2 4 6 5 8 7 1 9
|