2031| 1
|
[競賽分享] TOI2015第一次模擬考試 個人題解(非官方) |
原題:TOI2015第一次模擬考試
QA.年終獎金 解題方向:DP / 位元壓縮DP / 輪廓線DP 題目大意:有一個[tex]N%5CtimesN[/tex]的數字矩陣,在其中圈選一些數字,滿足圈選的數字不相臨(包含左上左下右上右下),求圈選的數字和最大是多少。([tex]N%5Cleq22[/tex]) 下範例中紅色的是最佳選法:
題解:我們可以討論逐排的狀況,來推到下一排。看似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之類的) 題目大意:給你一串數列,每個不同的數字代表一種顏色,要支援下操作:
題解:我們可以把所有顏色分開,用某種資料結構維護同顏色之間的距離,我個人用的是「紅黑樹套分裂合併式樹堆」又稱「map套樹堆」,前面的名子看起來比較炫而已XD,其實離線離散化顏色後就不需要map了。有人用map+set就過這題了,我覺得頗奇葩的。算是簡單題。 QD.機器人 等同IOI2013機器人,可參閱站內文章 http://forum.tfcis.org/thread-954-1-1.html
購買主題
本主題需向作者支付 30 枚金幣 才能瀏覽
| |||||||||||||||||