2012年2月27日 星期一

PCOI CCC 2012 Warm up contest

是次比賽共五題,亦是當年小弟第一次參賽CCC的題目。

A: 沒甚麼難度,是一道小心編寫的「輸出格式」題。

B: 沒甚麼好注意的,簡單的邊界檢查題。寫的時候可以考慮一行過的寫法﹕假設橫軸長度是$c$,而位於橫軸坐標$x$需要位移$d_x$,則可以透過一道公式更新位置\[ x := max(min(x + d_x, c), 0)\]緃軸亦然。

C: 直接依據題目要求計算矩陣的張量積即可。雖然直觀算法是$O(N\prod n_i\prod m_i)$,其中第$i$個矩陣是$n_i\times m_i$,但是倒是沒有大數據…就是做。

D: 簡單點說,就是給定一個深度優先的遍歷表,求與廣度優先的遍歷下的來回時間的相差。可以肯定的是廣度優先的遍歷只受最長路影響。假設最長路是$K$,答案則是$10(N - 2K)$。注意﹕題目沒說過起點的名稱必定是Home

E: 給定$N$個遊戲得分順序,求每場遊戲下的排名的平均數。直觀算法是$O(N^2)$,不用說肯定會超時。有三種做法。

(i) 利用平衡二叉樹進行插入及查找,可以用伸展樹,時間複雜度是$O(N\lg N)$。
(ii) 留意我們根本不用「實時」計算排名。若果按分數排序,並且為分數順道記錄其遊戲時序,則順序枚舉遊戲時查找分數比它高且時序比其要早。設符合遊戲數是$K$則其排名是$K+1$。如此一來可以用線段樹查找時序較早的遊戲數量,計得排名後把現時遊戲更新到該線段樹上。由於是Point update Range query,實際上也不是太難寫。
(iii) 同(ii),直接用Binary Indexed Tree,兩行代碼,方便快捷。

注意輸出浮點數往往會有精度問題。例如$44.445$會有機會存成$44.4449999999\cdots$而最終再取位下輸出成$44.44$(然而希望的是得到$44.45$)。為了解決類似情況,可以考慮用「無限小數」修正並輸出。例如該浮點數是$x$則輸出$x+\epsilon$,其中$\epsilon = 10^{-9}$足夠了(記作eps = 1e-9)。