查看: 808|回復: 1

[競賽分享] TOI2015第一次模擬考試 個人題解(非官方)

[複製鏈接]
  • TA的每日心情
    慵懶
    2015-4-10 14:18
  • 簽到天數: 78 天

    [LV.6]常住居民II

    176

    主題

    612

    帖子

    3959

    積分

    管理員

    Rank: 9Rank: 9Rank: 9

    積分
    3959

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

    發表於 2015-4-5 18:42:32 | 顯示全部樓層 |閱讀模式
    原題:TOI2015第一次模擬考試

    QA.年終獎金

    解題方向:DP / 位元壓縮DP / 輪廓線DP
    題目大意:有一個[tex]N%5CtimesN[/tex]的數字矩陣,在其中圈選一些數字,滿足圈選的數字不相臨(包含左上左下右上右下),求圈選的數字和最大是多少。([tex]N%5Cleq22[/tex])

    下範例中紅色的是最佳選法:
    5085020
    309075 40
    13153080
    60256560

    題解:我們可以討論逐排的狀況,來推到下一排。看似2^22次方種狀態很驚人,但其實合法狀態只有40000多種,容許我們完成這一題。


    QB.混淆密碼
    解題方向:多項式乘法(FFT/D&C)
    題目大意:求最長孑孓子字串(先看題目敘述吧)。
    我們可以分開討論所有字母,找尋同樣字母中,有多少對距離差是相等的。考慮字母[tex]C[/tex],我們構造新陣列[tex]M[/tex],若原陣列同位置[tex]i[/tex]的字母相同,[tex]Mi[/tex]就為1,反之為0。考慮該轉置陣列[tex]M'[/tex],以及[tex]R=M\times M'[/tex],會發現R的第i項為[tex]R%5Bi%5D%3D%5Csum%20M%5Ba%5DM%27%5Bi-a%5D%3D%5Csum%20M%5Ba%5DM%5BL+a-i%5D[/tex],其中[tex]i,L[/tex]為定值,恰等於距離為[tex]i[/tex]的配對個數!,於是我們取所有乘積相加中,係數最大的項就是答案。

    參考資料:https://www.cse.ust.hk/~dekai/271/notes/L03/L03.pdf

    QC.遊戲
    解題方向:資料結構(樹堆/STL之類的)

    題目大意:給你一串數列,每個不同的數字代表一種顏色,要支援下操作:
    • 修改單點的顏色
    • 詢問區間內,不出現指定顏色c的最長連續長度


    題解:我們可以把所有顏色分開,用某種資料結構維護同顏色之間的距離,我個人用的是「紅黑樹套分裂合併式樹堆」又稱「map套樹堆」,前面的名子看起來比較炫而已XD,其實離線離散化顏色後就不需要map了。有人用map+set就過這題了,我覺得頗奇葩的。算是簡單題。

    QD.機器人
    等同IOI2013機器人,可參閱站內文章
    http://forum.tfcis.org/thread-954-1-1.html

    購買主題 本主題需向作者支付 30 枚金幣 才能瀏覽
    回復

    使用道具 檢舉

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

    本版積分規則

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