<style> .reveal .slides { text-align: left; font-size:30px } </style> # 競賽技巧 一些有(毒)用(瘤)的小知識 --- ## 毒瘤技巧篇 一些可能會讓你程式比較好寫的小東西 ---- ## 常數宣告 常數變數宣告時通常使用全部大寫 ```cpp= // 數字中可以加 ' 方便看出幾位數 #define MXN 1'000'005 // 1e-6 為科學記號 代表 1 * 10^-6 #define EPS 1e-6 // 0x3f3f3f3f為一個接近10^9的數字0x為16進位 #define INF 0x3f3f3f3f // acos(-1) 等同圓周率 #define PI acos(-1) ``` ---- ## auto * 變數宣告時，自動判斷其型別 * 通常型態名稱很長會用 ```cpp= vector<int>::iterator iter = vec.begin(); // 上下兩者是一樣的意思 // 等於後面一定要接東西，才能判定型態 auto iter = vec.begin(); ``` ---- ### 取max  ---- ## 大括號 大括號可以呼叫預設建構子 ```cpp= int arr[5]={1,2,3}; // {1,2,3,0,0} int arr[5]={}; // {0,0,0,0,0} ``` ---- ## 非 0 即為 true 如果是整數型態的變數，放在條件判斷裡面 只要不是 0 就是 true， 0 則為 false ```cpp= int a = -9; if(a) cout << a << "is not zero;"; if(!a) cout << a << "is zero;"; ``` ---- ## 巨集 一種毒瘤的寫法，但可以降低程式碼長度 ```cpp= #define ll long long #define LL long long #define ld long double ``` ---- ## lambda 原本寫法 ```cpp bool cmp(int lhs,int rhs){ return lhs < rhs; } sort(vec.begin(),vec.end(),cmp) ``` 使用 lambda ```cpp= sort(vec.begin(),vec.end(),[](int lhs,int rhs){ return lhs < rhs; }) ``` ---- ## range for ```cpp= vector<int> vec{1,2,3}; for(int i:vec) cout<<i; //輸出為123 // 也可使用auto :D for(auto i:vec) cout<<i; for(auto &i:vec) i=i*10; //修改值記得使用參照 // vec的元素變成 [10, 20, 30] ``` ---- ## 標頭檔 [函式庫內容](https://gcc.gnu.org/onlinedocs/gcc-4.8.0/libstdc++/api/a01541_source.html) #include<bits/stdc++.h> --- ## 壓常數篇 一些壓常數的小技巧 ---- ## IO優化 TLE時除了考慮複雜度以外，常數也是很重要的 記得一定要在每題程式碼開頭加上這兩行 ```cpp= ios::sync_with_stdio(0); cin.tie(0); ``` 並且使用 '\n' 取代 endl 避免因為輸出入常數造成TLE而浪費時間debug ---- ## 位元運算 使用位元運算代替數值運算會快很多 #### 判斷數字奇偶性 ```cpp if(x%2) cout<<奇數; else cout<<偶數; // 上下判斷皆一樣，但下面會比較快 if(x&1) cout<<奇數; else cout<<偶數; ``` #### 將數字乘除2的幕次 ```cpp= x <<= 1 //將x左移1，等同 *2 x >>= 2 //將x右移2，等同 /4 ``` ---- ## 數值運算 在數值運算中，除法跟取餘數的動作超級慢 再來是乘法 #### 乘法取代除法 ```cpp= if(x / y > z / k){...} ``` 改為 ```cpp= if(x * k > z * y){...} ``` 以避免除法精度問題，可以乘法就不要除法 ---- #### 向上取整 $n$ 個蘋果，每個袋子可以裝 $m$ 顆，最少需要幾個袋子? ```cpp= int ans = (n+m-1)/m; ``` 直接多加 $m-1$ 個，這樣除了整除的都會多 $1$ ---- ## 編譯器優化 [unroll-loops](https://zh.wikipedia.org/wiki/%E5%BE%AA%E7%8E%AF%E5%B1%95%E5%BC%80) ```cpp= #pragma GCC optimize("O0")//不優化(預設) #pragma GCC optimize("O1")//優化一點 #pragma GCC optimize("O2")//優化更多 #pragma GCC optimize("O3")//O2優化再加上inline函式優化 #pragma GCC optimize("unroll-loops") ``` [其他](https://codeforces.com/blog/entry/96344) --- ## debug篇 有效的增加debug效率並減少失誤 ---- ## 編譯參數 g++ main -o main.cpp -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow ---- -fsanitize=undefined 插入各種undefined behavior檢查，會在執行期輸出錯誤訊息 -Wall -Wextra 把warning都開起來，常能預防bug發生 -Wshadow 當有宣告了相同變數名稱的情形發生時予以警告 -std=c\+\+14 c\+\+14 版本，前面教的很多語法至少要c++11以上 ---- ## cerr debug 時，很常會用cout輸出每個變數的值 在這邊建議輸出debug的值時使用cerr 他輸出的東西只會出現在command line 不會輸出在standard output 因此就算忘記刪也不會造成影響 否則用cout忘記刪就提交就會多吃一次penalty 甚至以為是哪裡又寫爛而花時間debug ```cpp= // __LINE__ 會輸出呼叫的位置在程式碼第幾行 cerr<<"This is debug message on "<<__LINE__<<" line"; ``` ---- ## assert 他用來判斷一個條件是否成立， 如果條件成立則不會發生任何事 如果條件不成立，則會造成程式RE(Runtime Error) 通常用於debug不確定會不會錯，或者想submit時 不確定有沒有問題用的 或者想猜測資，判斷是否大於某個值，就可以assert 會造成RE的這個性質去做事 ```cpp= assert(x <= 5); ``` --- ## 大學競賽程式賽制介紹 ---- * 一場五小時 10~15題 * 三人一隊 只有一台電腦 * 一份紙本試題(比賽都是英文題目) * 可以帶 25 頁 A4單面紙本資料 * 可以印code * 答對一題會有一顆氣球 ---- ## 各種比賽 [見連結](https://hackmd.io/@jakao/collegiateCompetitionsProgramming) ---- * OS: windows(NCPC), linux(ICPC) * judge system: domjudge * language: c/c++, java, python, kotlin(icpc) ---- ## 比賽排名 先比解題數，再比penalty 那 penalty 怎麼算? 每題解出來的時間加起來，再加上多錯的次數*20  以此記分板來看 penalty 為 35 + 7 + 2*20 = 82 ---- ## 開場 一個人先打好 default code 通常為手速最快或者主要coder ```cpp= #include<bits/stdc++.h> #define ll long long using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); return 0; } ``` 其他人開始讀題目 通常為英文閱讀好、題目辨識難度強的人 ---- ### 為甚麼要先打 default code 呢? * 殺首殺  * 每題要開始寫直接複製default code就好，減少寫程式碼量 ---- ### 看記分板 & 看別人的氣球 比賽中記分板，記得一定要定期刷新記分板，看大家解什麼題目 每題的氣球顏色都是固定的，因為記分板只能從電腦看，但如果隊友在上機看不了記分板就要觀察其他隊的氣球顏色  ---- ## 印code 比賽中隨時可以印出紙本code 那什麼時候要印 * 當bug找不到的時候 * 寫到一半發現想錯時 如果你是主coder 遇到bug 可以考慮給隊友找 自己再去開新的題目 ---- ## 評估題目 如果一次很多題目會寫，分析一下每題需要時間，根據greedy，先挑時間短的寫 比賽只有五小時，很短所以也要隨時注意時間 剩下一小時只留2\~3題，最後半小時只留1\~2題 ---- ## 補充血糖 比賽有五小時，很長XD 所以要定期去吃點心(建議1~2小時補充一次) 而且NCPC點心很好吃，很快就被搶光要搶要快(X  ---- ## 平常團隊訓練 養成良好分配習慣，知道彼此工作 賽後檢討彼此疏失或策略 修正策略 並且補題，也是最重要的，不補題跟沒打比賽一樣 不會解的題目還是不會 ---- ## 平常個人訓練 多打比賽，增加實作經驗 多寫題單，可以跟隊友溝通各自去練什麼演算法 各自專精擅長或有興趣的比賽也才能發揮各自所長 ---- ## 25 頁 A4單面紙本資料 * 又叫 codebook * [範例codebook](https://github.com/jakao0907/contest/blob/master/codebook.pdf) * 跟隊友溝通要放什麼演算法 * 或者如果語法不熟也可以考慮放 ---- ## 比賽策略與準備 - https://zhuanlan.zhihu.com/p/438790068 - https://hackmd.io/@sa072686/rke70TNtX?type=view ---- ## 經驗分享