2018TOI入營考

想起高一來時幾乎甚麼都還不會，只有20分
沒想到高三學測後還有機會參加校隊，這次的成績也算是對得起自己了哈哈XD



- pA
分解化學式，元素照字典序輸出個數
有括號，元素可能是一個大寫或一個大寫+一個小寫
ex:
                input:           C6H12O6
                output:         C:6
                                      H:12
                                      O:6

                input:           Ca(CH3COO)2
                output:         C:4
                                      Ca:1
                                      H:6
                                      O:4
-
括號比較煩人
我是遞迴+stack紀錄
應該有更好的作法，總之先AC再說
前前後後寫了4,50分鐘，有點耽誤到我的時間


- pB
給定一由字母組成之字串，問他是該系列之字串的第K大
K mod D 後輸出，從零開始算(最大的K = 0)
ex:
input: 50 CBA
output: 5
ABC 0
ACB 1
BAC 2
BCA 3
CAB 4
-> CBA 5

ex:
input: 5 BaaC
output: 2
BCaa
BaCa
-> BaaC
CBaa
CaBa
CaaB
...
-
賽中擺到最後幾分鐘才寫，沒有甚麼想法，暴力拿10分
後來聽說好像是數學吧，算組合數還什麼的


- pC
變形費式數列，給定x1, x2, a, b, n
x3 = a*x1 + b*x2
x4 = a*x2 + b*x3
... 求 xn mod 1000000007
-
矩陣快速冪，數字代換一下而已，這題是第一題AC的


- pD
給定一矩形長寬，與N(N<=3000)個格子點(0<座標範圍<=10^6)
問最多可框住幾個點，矩形可平移，不可旋轉
-
賽中也沒想法，小測資拿20分
另一筆30分的小測資好像也很好拿，可能是我看太快忽略了，可惜
賽後我問朋友解法，他說可以用greedy想想看


- pE
給定N個數字，N次詢問，每次詢問L, R之間之最小值
(N<=10^5)
- 解
線段樹我不是很擅長，總之寫了sparse table過這題
太久沒練習，中途bug一直冒出來，但還是順利AC了

在賽中穩定拿下三題AC很開心了，雖然這次題目的確不難
330算是可以接受的分數了，如果寫快一點應該可以試著做pD
最後ranking27名，恭喜前20名進入TOI選訓營!