Mirror的演算法筆記

第一次參加codewars，今年入場是送耳機電腦包和Tshirt，本來學弟也會來的，結果他們說不知道怎麼去就不來了。開賽前吃點心根本搶不到，覺得動線配置蠻差的。賽前登入系統的時候不知道為什麼我們這台一直連不上，請工作人員來幫忙換了三四個人才成功。 開始比賽之後我們先刷掉了送分那題，然後讓陳彥宇跟我講「森林村莊分類」的題述，他講的大意是判斷圖中點跟點有沒有連在一起，輸出沒有直接聯通的點對，做完之後提交竟然WA了，那時候覺得這題卡住了就先放在旁邊。那時候我們先嘗試做了「搭建圍欄」，不過在嘗試了兩三次之後我發現那題是凸包+旋轉卡尺，可是我完全不會寫計算幾何QQ。之後陳彥宇和孫文浩就說「刀疤的陰謀」那題是找質因數，於是我們覺得這題比較好解。然後我又跟孫文浩討論了一下「森林村莊分類」那題，結果一聽他的描述我就發現那題根本是判二分圖，然後就AC掉了。再來也順利的AC掉「刀疤的陰謀」。刷掉這兩題後我們決定一次看完全部的題目再決定要做哪題，可能因為太急沒有很認真聽題目導致我們漏掉了一個20分但不難的「刀疤的獎勵」。最後我們是決定開「搶得先機II」，做完多餘的時間再做「星空下的塵砂」，「搶得先機II」那題就bfs走迷宮，不過實做稍微麻煩了一點，但還是確實地拿了下來，這時候因為已經沒多少時間我們就沒有繼續做了。 雖然這場比賽有很多時間感覺都被浪費掉了，也有幾題其實不難的題目我們可能沒有注意或剛好不會寫相關的算法就不得不放棄，有點可惜。但整體來講感覺還是打得不錯啦，以我們高職菜雞而且學演算法沒多久來看我個人認為還算滿意。

丟一個模板在這裡以免忘記 inline char readchar () { static const size_t bufsize = 65536 ; static char buf[bufsize]; static char * p = buf, * end = buf; if (p == end) end = buf + fread_unlocked (buf, 1 , bufsize, stdin), p = buf; return * p ++ ; } template < class T > void input (T & a ) { static char p; while ((p = readchar ()) < ' 0 ' ) ; a = p ^ ' 0 ' ; while ((p = readchar ()) >= ' 0 ' ) a *= 10 , a += p ^ ' 0 ' ; } 可能會用到的題目:TIOJ 1930 , ZJ c223 , TIOJ 2026

I/O優化 https://horikitacoding.blogspot.com/2019/07/how-to-optimize-your-code-in-c.html 離散數學-同餘 https://ithelp.ithome.com.tw/articles/10205727

整體來講這次打得真的是五味雜陳，就把人生中第一次演算法的比賽記錄下來吧 首先早上有一個練習賽，我推測是讓你熟悉環境和比賽方式的 pA 因為測資出包(給假測資)導致在時間結束前十分鐘左右才有人做出來，那題是給你一些數字，將數字合併會花費 a 數字 +b 數字的值，合併到最後只剩一個數字時，求最小花費。其實就是一個 min heap ，每次選最小的兩個數字合併，但測資的輸出結果需要在輸出後加一個空格導致不通靈根本解不出來 再來的題號順序都不記得了，就隨便寫我記得的題目 1. 有一個太空梭，上面有 x 個油箱，每個油箱都帶有 5 個油，太空梭本身也有 5 個油，每個月要花費油箱數 +1 個油，油箱空時可丟掉油箱，問可飛幾個月。就一個簡單的實做題，需要注意的是一次有可能丟掉超過一個油箱，所以要用 while 去判斷要丟掉幾個 2. 給你一個數字，將其分解為所有小於自己的數字相加，問有幾種方法。就無限背包去湊出來 3. 沒看題目，陳彥宇說是 Floyd 裸題就直接 AC 了 4. 給你 n 個項目和 k 投資金額，每個項目有 1 ， 2 ， 3………k 種投資方案，分別對應每個投資方案的收益，問你如何投資才能獲得最大收益。這題沒做出來，還需要再思考看看 早上的時候算上 pA 共 AC 了 4 題，下午就打的超慘的 .... 總共就做出了兩題，而且我還基本上沒看到題目，搞不好錯過了一些有機會 AC 的題目 pA 是輸入多行文字，在這幾行文字中可能會有 // 或 /*  ( */ )   做註解，輸出註解以外的所有文字(含換行)。就純實做題，細節處理好就 AC 了 pB 是給你 a , b , n 代表在快速冪( a^b%n )中所需要乘的次數。也就是 b 一直除二，若不為 0 則答案 +1 ， b 為奇數時答案再 +1 。不過這題也因為範例測資少輸入 n 害我 WA 了兩次 pC 給你 a 個城市， b 條路，從 s 運貨物到 t ，最大可用時間 d ，每條路都給你起點，終點，所花金額和時間，求最小花費金額。應該是 dijkstra 最短路變形，然後我猜我在實做時到每個點的距離沒有更新為最小，導致 WA 了，因為題目也沒了沒辦法驗證，可惜 再來也忘記題號了所以隨便寫 1. 給你 n 個城市與他們的聯通關係，在某城市開商店，與這座城市相鄰的城市(不含當前城市)就...