競賽技巧 & 競賽介紹 & DEBUG技巧

--- tags: 2023-winterTraining type: slide --- <style> .reveal .slides { text-align: left; font-size:35px } </style> # 競賽技巧 & 競賽介紹 2/17 ---- * 快讀/快出/換行 " \n"[i == n] * GCC pragma * 陣列開法(全域變數)&&const * memset(arr,value,sizeof(arr)) -1,0,0x3f3f3f3f * mt19937(hash<string>(":poop:")) * for(auto i : arr) * define int ll * __int128 * begin, rbegin * prev, next * int main(){ int T=1; //cin >> T; while(T--) solve(); } ---- ## 快讀/快出/換行 " \n"[i == n](Creating note...) 首先分析三種輸出輸入的優劣 C printf/scanf : 需要記%d %f %c %s 等等比較繁複的程式 C++ cin/cout : 較為簡單，不需處理資料類型，但比C標準輸入略慢一點快讀/快寫 : 只能處理整數讀入/輸出，但是要比標準輸入輸出函數都快得多。 ---- ## 快讀 ```cpp inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-') f=-1; ch=getchar(); } while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } ``` ---- ## 快寫 ```cpp void write(int x){ if(x<0) putchar('-'),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); return; } ``` ---- ## 換行 " \n"[i == n] 不需要另外多寫if-else述句，可以 ```cpp for(int i=1;i<=5;i++){ cout<<i<<" \n"[i==5]; } ``` --- ## [pragma GCC](https://www.cnblogs.com/vaughnhuang/p/16737609.html) 只需要無腦加在最前面就好，原理為放棄編譯速度/運行速度/代碼大小/指標指向去增加其他東西 ```cpp #pragma GCC optimize(1) #pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize("Ofast") #pragma GCC optimize("inline") #pragma GCC optimize("-fgcse") #pragma GCC optimize("-fgcse-lm") #pragma GCC optimize("-fipa-sra") #pragma GCC optimize("-ftree-pre") #pragma GCC optimize("-ftree-vrp") #pragma GCC optimize("-fpeephole2") #pragma GCC optimize("-ffast-math") #pragma GCC optimize("-fsched-spec") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("-falign-jumps") #pragma GCC optimize("-falign-loops") #pragma GCC optimize("-falign-labels") #pragma GCC optimize("-fdevirtualize") #pragma GCC optimize("-fcaller-saves") #pragma GCC optimize("-fcrossjumping") #pragma GCC optimize("-fthread-jumps") #pragma GCC optimize("-funroll-loops") #pragma GCC optimize("-fwhole-program") #pragma GCC optimize("-freorder-blocks") #pragma GCC optimize("-fschedule-insns") #pragma GCC optimize("inline-functions") #pragma GCC optimize("-ftree-tail-merge") #pragma GCC optimize("-fschedule-insns2") #pragma GCC optimize("-fstrict-aliasing") #pragma GCC optimize("-fstrict-overflow") #pragma GCC optimize("-falign-functions") #pragma GCC optimize("-fcse-skip-blocks") #pragma GCC optimize("-fcse-follow-jumps") #pragma GCC optimize("-fsched-interblock") #pragma GCC optimize("-fpartial-inlining") #pragma GCC optimize("no-stack-protector") #pragma GCC optimize("-freorder-functions") #pragma GCC optimize("-findirect-inlining") #pragma GCC optimize("-frerun-cse-after-loop") #pragma GCC optimize("inline-small-functions") #pragma GCC optimize("-finline-small-functions") #pragma GCC optimize("-ftree-switch-conversion") #pragma GCC optimize("-foptimize-sibling-calls") #pragma GCC optimize("-fexpensive-optimizations") #pragma GCC optimize("-funsafe-loop-optimizations") #pragma GCC optimize("inline-functions-called-once") #pragma GCC optimize("-fdelete-null-pointer-checks") #pragma G++ optimize(1) #pragma G++ optimize(2) #pragma G++ optimize(3) #pragma G++ optimize("Ofast") #pragma G++ optimize("inline") #pragma G++ optimize("-fgcse") #pragma G++ optimize("-fgcse-lm") #pragma G++ optimize("-fipa-sra") #pragma G++ optimize("-ftree-pre") #pragma G++ optimize("-ftree-vrp") #pragma G++ optimize("-fpeephole2") #pragma G++ optimize("-ffast-math") #pragma G++ optimize("-fsched-spec") #pragma G++ optimize("unroll-loops") #pragma G++ optimize("-falign-jumps") #pragma G++ optimize("-falign-loops") #pragma G++ optimize("-falign-labels") #pragma G++ optimize("-fdevirtualize") #pragma G++ optimize("-fcaller-saves") #pragma G++ optimize("-fcrossjumping") #pragma G++ optimize("-fthread-jumps") #pragma G++ optimize("-funroll-loops") #pragma G++ optimize("-fwhole-program") #pragma G++ optimize("-freorder-blocks") #pragma G++ optimize("-fschedule-insns") #pragma G++ optimize("inline-functions") #pragma G++ optimize("-ftree-tail-merge") #pragma G++ optimize("-fschedule-insns2") #pragma G++ optimize("-fstrict-aliasing") #pragma G++ optimize("-fstrict-overflow") #pragma G++ optimize("-falign-functions") #pragma G++ optimize("-fcse-skip-blocks") #pragma G++ optimize("-fcse-follow-jumps") #pragma G++ optimize("-fsched-interblock") #pragma G++ optimize("-fpartial-inlining") #pragma G++ optimize("no-stack-protector") #pragma G++ optimize("-freorder-functions") #pragma G++ optimize("-findirect-inlining") #pragma G++ optimize("-frerun-cse-after-loop") #pragma G++ optimize("inline-small-functions") #pragma G++ optimize("-finline-small-functions") #pragma G++ optimize("-ftree-switch-conversion") #pragma G++ optimize("-foptimize-sibling-calls") #pragma G++ optimize("-fexpensive-optimizations") #pragma G++ optimize("-funsafe-loop-optimizations") #pragma G++ optimize("inline-functions-called-once") #pragma G++ optimize("-fdelete-null-pointer-checks") ``` ---- ## 實用且常用pragma ```cpp #pragma GCC optimize("Ofast") #pragma GCC target("sse3","sse2","sse") #pragma GCC target("avx","sse4","sse4.1","sse4.2","ssse3") #pragma GCC target("f16c") #pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector") #pragma GCC diagnostic error "-fwhole-program" #pragma GCC diagnostic error "-fcse-skip-blocks" #pragma GCC diagnostic error "-funsafe-loop-optimizations" #pragma GCC diagnostic error "-std=c++14" ``` --- ## 陣列開法(全域變數)&&const const 是固定變數，你用const宣告出來的東西在之後就不能再更改，同時這樣開在全域就也不需要再函式間傳遞也不用考慮初始化的問題。 ```cpp const int N=1e5+5; int arr[N]={}; ``` --- ## memset(arr,value,sizeof(arr)) 時間複雜度是O(N)，可以把整個arr的值都變成value。好處是方便快速，但可賦值有限制 ex: -1 , 0 , 0x3f3f3f3f 同時要使用則要記得引入標頭檔cstring --- ## mt19937(hash<string>(":poop:")) 如果要使用random等函式，不推薦在比賽中使用時間種子碼以及rand，而是推薦使用這個mt19937，產生高性能隨機數，且更為隨機以及可測試一點。 ```cpp #include<iostream> #include<random> using namespace std; signed main() { mt19937 mt(hash<string>(":poop:")); for(int i=1;i<=5;i++) cout<<mt()<<" \n"[i==5]; return 0; } ``` --- ## for(auto i : arr ) 可以直接讓 $i$ 遍歷 $arr$ 裡面的東西，且auto也不用考慮型態，只需要無腦這樣寫，對於實作的方便性很高，直接讓編譯器宣告他的變數型態。 --- ## lambda 匿名函式，在參數有函式的時會用到(例：sort) ```cpp sort(a.begin(), a.end(), [](const int lhs, const int rhs){ return lhs < rhs; }); ``` --- ## #define int long long 在你發現你的代碼需要把很多東西改型態的時候，只需要define這行就可以一次性把所有int變成long long，當然還有其他東西也可以這樣用。不過需要記得把main函數的定義改掉，改成int32_t或是signed都可以 ex : ``` #define int double #define x first #define y second #define rep(a,b) for(int a=1;a<=b;a++) ``` --- ## __int128 與int,long long 沒什麼差別，特點有是超級大的定義域(可以儲存1e36內的數字)，但C/C++標準IO是不認識__int128這種數據類型，cin和cout是無法輸出__int128的，所以我們要自己實現輸入輸出，其他的運算，與int沒啥差別。 __int128能直接做加减乘除赋值 --- ## begin, rbegin, end rend c.begin() 返回一個迭代器，它指向容器c的第一個元素 c.end() 返回一個迭代器，它指向容器c的最後一個元素的下一個位置 c.rbegin() 返回一個逆序迭代器，它指向容器c的最後一個元素(比begin慢) c.rend() 返回一個逆序迭代器，它指向容器c的第一個元素前面的位置(比end慢) 使用這些訪問方式，就可以不用去重新定義它的大小或是重新確認一次，同時也可以訪問那些沒辦法隨機存取的容器類別，可以直接叫出來。 --- ## prev, next prev是指用來獲取一個距離指定迭代器左側 $n$ 個元素的迭代器。 next是指用來獲取一個距離指定迭代器右側 $n$ 個元素的迭代器。假設現在有一個$vector[10]={0,1,2,3,4,5} ; iter=2 ;$ 則會有以下四種 $prev(iter,2), iter=0$ $prev(iter,-2), iter=4$ $next(iter,2), iter=4$ $next(iter,2), iter=0$ 就可以無需使用其他寫法去進行移動迭代器 --- ## int main(){ int T=1; //cin >> T; while(T--) solve(); } 就像是看到的那樣。這樣的寫法可以讓你再換題的時候直接刪除solve函式，不須刪除其他東西，可以有效提高寫題目的效率。 --- ## 大學競賽程式賽制介紹 ---- * 一場五小時 10~15 題 * 三人一隊只有一台電腦 * 一份紙本試題(比賽都是英文題目) * 可以帶 25 頁 A4單面紙本資料 * 可以印 code * 答對一題會有一顆氣球 ---- ## 各種比賽 ![](https://i.imgur.com/PgS0lTH.png) [見連結](https://hackmd.io/@jakao/collegiateCompetitionsProgramming) ---- * OS: windows(NCPC), linux(ICPC) * judge system: domjudge * language: c/c++, java, python, kotlin(icpc) ---- ## 比賽排名先比解題數，再比penalty 那 penalty 怎麼算? 每題解出來的時間加起來，再加上多錯的次數*20 ![](https://i.imgur.com/CTXdOpL.png) 以此記分板來看 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 呢? * 殺首殺 ![](https://i.imgur.com/9Vz37Xt.png) * 每題要開始寫直接複製default code就好，減少寫程式碼量 ---- ### 看記分板 & 看別人的氣球比賽中記分板，記得一定要定期刷新記分板，看大家解什麼題目每題的氣球顏色都是固定的，因為記分板只能從電腦看，但如果隊友在上機看不了記分板就要觀察其他隊的氣球顏色 ![](https://i.imgur.com/BbQZHwe.jpg =500x) ---- ## 印code 比賽中隨時可以印出紙本code 那什麼時候要印 * 當bug找不到的時候 * 寫到一半發現想錯時如果你是主coder 遇到bug 可以考慮給隊友找自己再去開新的題目 ---- ## 評估題目如果一次很多題目會寫，分析一下每題需要時間，根據greedy，先挑時間短的寫比賽只有五小時，很短所以也要隨時注意時間剩下一小時只留2\~3題，最後半小時只留1\~2題 ---- ## 補充血糖比賽有五小時，很長XD 所以要定期去吃點心(建議1~2小時補充一次) 而且NCPC點心很好吃，很快就被搶光要搶要快(X ![](https://i.imgur.com/l0C4DtY.jpg =500x) ---- ## 平常團隊訓練養成良好分配習慣，知道彼此工作賽後檢討彼此疏失或策略修正策略並且補題，也是最重要的，不補題跟沒打比賽一樣不會解的題目還是不會 ---- ## 平常個人訓練多打比賽，增加實作經驗多寫題單，可以跟隊友溝通各自去練什麼演算法多看電神的code，可以看到各種有趣精湛的寫法各自專精擅長或有興趣的比賽也才能發揮各自所長 ---- ## 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