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

原題：TOI2015第一次模擬考試

QA.年終獎金

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

下範例中紅色的是最佳選法：

50	8	50	20
30	90	75	40
13	15	30	80
60	25	65	60

題解：我們可以討論逐排的狀況，來推到下一排。看似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