很久沒有寫了，今次的題目是Mini comp 3，可能你會奇怪，為何mini comp 2沒有在這裏出現，其實話說有另外一個人寫了，但很久很久還沒有upload上來，所以大家先看到的會是mini comp 3的解題。
今次的題目相對比以往的難，最少比較難得到滿分。此外，由於大家似乎對MST不很熟，特地出了一條模板題，讓大家有心理準備，這一類data structure是應該隨手可以code出來的。
分數方面，我是頗為失望的，一條模板的MST，竟然沒有人得到滿分！而出席的人當中，有不少更是有機會代表香港出賽的選手，大家似乎要加把勁了。
HKOJ1142 - Jump Across the River
第一題便是我自己的作品。一條挺明顯的DP，state是[到了第幾格][上次跳了多少步]，時間為O(NK2)。可能有人會問，既然可以向後跳，為何可以用DP？
事實上，我們可以證明最優的跳法是可以不用向後跳的。首先，如果向後跳的格數和向前跳的一樣，其中一個最優解可以是之前向前跳少一步，而所用的energy是一樣的。如果向後跳的格數和向前跳的不一樣，我們也可以很直接的推斷到在之前用1 energy跳短一點也可以做到相同效果。因此，這題會有最優的部分解。
此外，這題也可以用shortest path來解決的，方法與DP的相似，只是搜索順序不同。
仍然過不到的人，請再仔細看題目。
HKOJ1143 - Density Index
這題考的是數學基本功，基本上用中學學過的algebra，列出題目中的式子，拆開再用電腦快速計算便可以O(n)的時間解決。
HKOJ1144 - Minimum Spanning Tree
真的是基本功，一定要懂，不懂的請參考http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure，這裏不說了。注意的是文中的rank其實可以不寫，因為總的來說，用的時間也是接近O(n)。
HKOJ1145 - Lucky Bin Packing
最後一題是我找到很有趣的一題ad-hoc加少少math的題目。很多case，因此很難得滿分，所以連sample solution都錯了，但是我個人認為這題是值得思考的，而且可以訓練各位的小心程度。
下一次比賽便是APIO，再來就是TFT了，很緊張呀！注意，在寫這一篇文前，TFT的題目還沒有出好，所以大家不用有任何的揣測，這個絕不是放水的地方。但是一個永恆不變的道理，要在TFT上表現得好，不單要做題目，還要積極和認真參加比賽，得到實戰經驗，才可百戰百勝。
