查看: 865|回復: 0

[HOJ] 255 - Empodia (IOI 2004)

[複製鏈接]
  • TA的每日心情
    開心
    2015-4-12 10:09
  • 簽到天數: 137 天

    [LV.7]常住居民III

    142

    主題

    686

    帖子

    3559

    積分

    邁向天堂

    蘇多門

    Rank: 8Rank: 8

    積分
    3559

    新手達陣台南一中資訊社程式設計達人 - 2014

    發表於 2015-3-15 02:26:30 | 顯示全部樓層 |閱讀模式

    趕快加入我們來參與討論吧!

    您需要 登錄 才可以下載或查看,沒有帳號?加入我們

    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
    
    蘇多門 domen111
    My Web: https://sites.google.com/site/domenprg/
    回復

    使用道具 檢舉

    您需要登錄後才可以回帖 登入 | 加入我們

    本版積分規則

    快速回覆 返回頂部 返回列表