竹園論壇

標題: 255 - Empodia (IOI 2004) [打印本頁]

作者: domen111 時間: 2015-3-15 02:26
標題: 255 - Empodia (IOI 2004)
本帖最後由 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

歡迎光臨竹園論壇 (http://forum.tfcis.org/)