<style> .reveal .slides { text-align: left; font-size:28px; } </style> # 2022 Ocean Cup ## 收心賽 --- ## 龍崗組 - A. 國際大學生程式設計競賽 - B. 倒垃圾 - C. 獎品保鑣 - D. 組隊 - E. 好想大吃一頓阿 但我更想免役 - F. 數量平分 - G. 密文解鎖 - H. 一筆畫問題 ---- ## 開版 ---- ## 封板前記分板  ---- ### 第二名 ## 少了邱葵把拔不會飛 獲得熱身賽小紅包 ---- ### 第一名 ## 晴天娃娃 獲得熱身賽小紅包 --- ## 消波塊組 - A. Prize Protection --- Geometry - B. Heavy Roy --- Math - C. Make it Equal 1 --- Cost Flow, KM - D. Make it Equal 2 --- Implementation - E. Game Master --- DP - F. Sewage Treatment Plants --- Tree, DFS - G. Make String --- DP, String - H. Machine Learning Battle Topics --- Bitwise - I. Crazy Arcade --- Data Structure ---- ## Wrong in Contest 一些在賽中觀察到的錯誤 ---- ## Wrong in Contest - problem F for flow N 個點, N-1 條邊 並且圖連通 這好像是什麼特殊的圖? ---- ## Wrong in Contest - problem F for flow **It is a tree!** 直接 DFS 回傳答案給父節點即可 O(N) AC! ---- ## Wrong in Contest - problem B $O(N)$ B 的數量級到 $10^{15}$ 機器一秒的運算輛通常只有 $10^8$ 左右 時間給一秒，因此不能慢慢用迴圈加上去 **請好好算數學用 $O(1)$ 解** 沒有判斷 $W = T$ 的情況 ---- ## Wrong in Contest - problem A doesn't using long long int int 的範圍只有到 2147483647 因此要使用 long long int 而如果使用 double 型態會造成浮點數誤差 ---- ## Wrong in Contest - problem E DP沒好好判斷是否可以轉移 DP[i] = max(DP[j] + $p_{ij}$ + $(t_j-a_{ji})*k_j)$ 從 關卡$j$ 轉移到 關卡$i$ 如果滿足以下條件即可以轉移 - $j < i$ - $t_j \ge a_{ji}$ - **DP[j] $\neq$ impossible** 大多隊伍都忽略了第三個條件，沒有先判斷關卡 $j$ 本身有沒有被走到 ---- ## Wrong in Contest - problem H Memory Limit Exceed caused Runtime Error 記憶體限制只有 1 MB -> 只能存下 $250000$ 個 int，很明顯 2'000'000 是儲存不下的 ---- 以上除了複雜度的問題，大部分都可以跑對拍對到錯的測資 尤其 problem $A, B, D, E$ ---- ## 開版 ---- ## 封板前記分板  ---- ### 第五名 ## YHY_Team ---- ### 第四名 ## orZ1han ---- ### 第三名 ## daidaiclub 獲得熱身賽小紅包 ---- ### 第二名 ## ladyfingers 獲得熱身賽小紅包 ---- ## 第一名 ## minEnglishestillbed 獲得熱身賽小紅包 ---- ## 抽獎環節 ---- 獎品於正式賽發放 記得來參加及領取 預計於 11 月舉辦正式賽 會陸續宣布精美禮品 也需要大家多幫忙宣傳海洋盃~ 謝謝大家的參與，我們正式賽見