255 - Empodia (IOI 2004)

domen111

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