查看: 689|回復: 0

[其他] [IOIcamp2015] 31 - 草莓園保衛戰 II

[複製鏈接]
  • TA的每日心情
    鬱悶
    2015-5-15 22:38
  • 簽到天數: 33 天

    [LV.5]常住居民I

    75

    主題

    302

    帖子

    766

    積分

    版主

    TFcis - 105 附設監工官

    Rank: 7Rank: 7Rank: 7

    積分
    766

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

    發表於 2015-2-24 23:09:44 | 顯示全部樓層 |閱讀模式

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

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

    x
    本帖最後由 jd3 於 2015-2-24 23:12 編輯

    遲早會失效的原網址~~~
    http://judge.ioicamp.org/problems/31


    題意
    問區間中是否有
    1.重複超過3次的數
    2.最大和最小值相差超過51400





    解體
    區間操作先想到的是一些奇怪的線段數
    線段數能輕鬆維護最大最小,重複超過3次卻很棘手

    有個東西叫莫隊算法,據說會過可是我寫的複雜度差一個根號 TLE 了 QAQ
    (等補充)


    接下來傳說是官方解法
    經過一番觀察
    我們發現對於一個左界 L , 他有最遠右界 R
    只要以L為左端,又界<=R則一定是可行的區間

    於是想要對於每個左界往右掃看看能到哪
    這樣的預處理時間複雜度O(N^2)
    輕鬆
    TLE


    接下來這段理解方式不同是正常的
    經過一番精密的觀察得知
    對於越右邊的L, 它的R一定越右邊
    換句話說就是 R[ i ] <= R[ j ]  (i < j)
    而越右端的R, 它的L也一定越右邊
    換句話說就是 L[ i ] <= L[ j ]  (i < j)

    嗯...這有什麼好處呢?
    透過經驗猜想我們需要一個資料結構來維護某些奇怪的資料
    然後從左邊慢慢掃過去

    然後他一臉蟲樣
    看起來就是在爬

    於是乎亂做一通
    從右邊新加進來的元素 i ,如果不能當 最左邊元素 的R了, 那這個最左邊元素的R就是i-1, 然後左端就可以拔掉一個元素
    多維護一個計數用的array, 在加進元素或拔除元素時更新當前有多少個就能判斷加入時是否有超過3個元素

    array可以O(1)加入, O(1)查詢單一元素數量
    可是沒辦法快速找到最大最小


    當然你也可以開個線段數再亂炸一通(不保證常數夠小)
    這裡介紹個multiset的東西
    log(n)插入, log(n)刪除, log(n)計數
    因為內部是個2元搜尋樹之類的東西,是有排序的
    查最大最小就是begin() 和 --end()
    是O(1)還是O(log(n))我就不清楚了

    終於你獲得了一些BUG

    然後盲目的殺了半晌
    終於
    AC


    如果還想要小加速可以考慮把答案塞進string再輸出XD

    以下CODE
    [sojcodepad]d795615d[/sojcodepad]
    <這是個人簽名欄位>
    回復

    使用道具 檢舉

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

    本版積分規則

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