<style> .reveal .slides { text-align: left; font-size:35px } </style> # 競賽技巧 & 競賽介紹 Introduction to Competitive Programming 2/7 ---- * 快讀/快出/換行 " \n"[i == n] * GCC pragma * 陣列開法(全域變數)&&const * memset(arr,value,sizeof(arr)) -1,0,0x3f3f3f3f * mt19937(hash<string>(":poop:")) * for(auto i : arr) * lambda sort(begin, end, [](const int lhs, const int rhs){return lhs < rhs}); * define int ll * __int128 * begin, rbegin * prev, next * int main(){ int T=1; //cin >> T; while(T--) solve(); } ---- ## 快讀/快出/換行 " \n"[i == n] 首先分析三種輸出輸入的優劣 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也不用考慮型態，只需要無腦這樣寫，對於實作的方便性很高，直接讓編譯器宣告他的變數型態。 --- ## #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://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  ---- ## 平常團隊訓練 養成良好分配習慣，知道彼此工作 賽後檢討彼此疏失或策略 修正策略 並且補題，也是最重要的，不補題跟沒打比賽一樣 不會解的題目還是不會 ---- ## 平常個人訓練 多打比賽，增加實作經驗 多寫題單，可以跟隊友溝通各自去練什麼演算法 多看電神的code，可以看到各種有趣精湛的寫法 各自專精擅長或有興趣的比賽也才能發揮各自所長 ---- ## 25 頁 A4單面紙本資料 * 又叫 codebook * [範例codebook](https://github.com/jakao0907/contest/blob/master/codebook.pdf) * 跟隊友溝通要放什麼演算法 * 或者如果語法不熟也可以考慮放 --- ## DEBUG技巧 ---- - 瘋狂輸出 - linux 指令 - 對拍 - Debugging template - hack測資 --- ## 為什麼要學 linux 指令 ? ---- ## ICPC 國際大學生程式設計競賽 https://icpc2022.ntub.edu.tw/onsite/contest-environment/  ---- ## NCPC 全國大專電腦軟體設計競賽 https://ncpc.ntnu.edu.tw/environment/final.html  ---- - 對開發者較友善 - 更多好用的東西 - 等等對拍也會用到 ---- ## 如果我的電腦是 Windows ? - 雙系統 - Windows Subsystem of Linux (WSL) ---- ## Windows Subsystem of Linux (WSL) https://zhuanlan.zhihu.com/p/47541491 https://hackmd.io/@billsun/BJByCIUHf?type=view <div style="position: absolute; right: 90%;">  </div> <div style="position: absolute; right: 50%;">  </div> <div style="position: absolute; right: 10%;">  </div> ---- ## linux 基本指令 ```shell= cd .. 回到上一層資料夾 cd ../.. 回到上上層資料夾 cd test 到當前目錄的test資料夾 ls 顯示當前資料夾的檔案 cat a.cpp 印出當前檔案的內容 mkdir test 在當前目錄建立 test 的資料夾 rm a.cpp 刪除 a.cpp 的檔案 ``` ---- ## 編譯檔案 g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow ```shell= g++ solve.cpp 編譯solve.cpp的檔案成 a.out 檔 g++ solve.cpp -o ac.out 編譯solve.cpp的檔案成 ac.out 檔 g++ solve.cpp -std=c++14 編譯solve.cpp的檔案成 a.out 檔 並且編譯版本為 c++14 ./a.out 執行 a.out 檔 ``` ## 其他編譯參數 ```shell= -fsanitize=undefined 插入各種undefined behavior檢查，會在執行期輸出錯誤訊息 -Wall -Wextra 把warning都開起來，常能預防bug發生 -Wshadow 當有宣告了相同變數名稱的情形發生時予以警告 ``` ---- g++ solve.cpp -o main -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow ---- 難道每次都要打那麼長嗎 ? ---- ## Alias 可以使用 alias 把原本要打的那串 define 掉 ```bash alias [name]='[value]' ``` 等同於 c++ 內的 #define #define ll long long ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow` ``` ---- 使用 Alias 之後 ```bash g++ solve.cpp ``` 等價於 ```bash g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow solve.cpp ``` ---- ## 產生質因數 ```bash= factor 100 ``` --- ## debug 競賽中或者平常寫題目時，如果遇到 bug 不能及時找到 有以下方法 1. 團體賽中，可以把 code 印出來自己到旁邊 debug，給其他隊友上機寫其他題目 (前提為有其他題目可以開) 2. 團體賽中，可以把 code 印出來給隊友 debug， (前提為能有效跟隊友溝通並且看得懂你的code) 3. 好好寫對拍 ---- ## 對拍  ---- ## 步驟 1. **寫對拍的 script** 2. 寫一份暴力程式碼 ac.cpp 3. 寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp``` ---- ## 對拍的 script 先將兩份程式碼分別編譯成 ac, wa 不斷用 ``gen.py`` 產生測資放到 input 檔案裡面 再把 input 檔案分別為給 ac, wa 兩份執行檔 用 for 迴圈一直跑到 output 內容不同為止 set -e 可以偵測程式 RE 時會停下來 ```shell= set -e g++ ac.cpp -o ac g++ wa.cpp -o wa for ((i=0;;i++)) do echo "$i" python3 gen.py > input ./ac < input > ac.out ./wa < input > wa.out diff ac.out wa.out || break done ``` ---- 跑到停下來後有兩種可能 1. RUNTIME ERROR  2. WRONG ANSWER  ---- ## 為甚麼要用對拍 - 找不到好的 case 能讓他自己跑 先寫其他題目 - 寫暴力程式碼的時間遠比多吃一次 20 penalty 還要來的划算 - 對拍可以重複驗證程式正確性，de 完原本的 bug 可以再跑一次對拍 因此當比賽時，如果對於錯誤毫無頭緒， 不應該只是盯著程式碼看，而是開始寫對拍才是最有效率的做法 ---- 而平時練習、作業找不到bug的情況也應該要先對拍 真的找不到問題 對拍也對不到 再去問其他電神錯在哪 ---- ## 步驟 1. 寫對拍的 script 2. **寫一份暴力程式碼 ac.cpp** 3. 寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp``` ---- ## 寫一份暴力程式碼 ac.cpp 聽起來好麻煩，為了 debug 還要多寫一份 code 而且不一定寫得出來還有可能錯，怎麼辦? ---- 如果連暴力的程式碼都寫不出來 那你應該多練練你的實作能力... 如果不知道怎麼寫請參考早上 [brute force](https://hackmd.io/@LeeShoWhaodian/bruteforce) 講義 善用 next_permutation 以及好好熟悉遞迴 沒有暴力寫不了的程式碼 只有你不練不夠實作能力 ---- ## 步驟 1. 寫對拍的 script 2. 寫一份暴力程式碼 ac.cpp 3. **寫一份產生隨機測資的程式碼 ```gen.py/gen.cpp```** ---- ## 產生隨機測資 (python) ```python= from random import * n = randint(1, 100) # 隨機產生 1~100的整數 ch = chr(ord('a') + randint(0, 25)) # 隨機產生 'a'~'z' 其中一個字元 choiceSet = sample(s, 4) # 從集合 s 選出 4 個不同的元素 choiceSet = sample(range(1, n+1), 4) # 從整數 1~n 選出 4 個不同的元素 shuffle(arr) # 把序列 arr 順序打亂 ``` ---- ## 隨機產生一組 1~n 的 permutation ```python= from random import * n = randint(3, 6) arr = [i+1 for i in range(n)] shuffle(arr) print(n) print(*arr) #輸出 arr 的內容並且用空格隔開 ``` ---- ## 隨機產生一個長度為 n 的小寫字母字串 ```python= s = "" n = randint(1, 10) for i in range(n): s += chr(ord('a') + randint(0, 25)) print(s) ``` ---- ## 隨機產生一棵樹 每次從比自己小的節點選一個當連接自己的邊 ```python= from random import * n = randint(3, 6) print(n) for i in range(2, n+1): print(randint(1, i-1), i) ``` ---- ## 隨機產生無自環無重邊的一張連通圖 無自環 可以判斷兩個點不相同 無重邊 可以用 dict/map 紀錄哪些邊用過了 連通圖 = 樹 + 一些額外的邊 ---- ## 隨機產生無自環無重邊的一張連通圖 ```python= from random import * n = randint(5, 10) m = randint(n-1, n+3) print(n, m) edge = list() #construct tree for i in range(2, n+1): x = randint(1, i-1) y = i edge.append([min(x, y), max(x, y)]) print(x, y) #add extra edge for i in range(m-(n-1)): x = randint(1, n) y = randint(1, n) while x == y or [min(x, y), max(x, y)] in edge: x = randint(1, n) y = randint(1, n) print(x, y) edge.append([min(x, y), max(x, y)]) ``` ---- ## 產生隨機測資 (c++) [Don't use rand(): a guide to random number generators in C++](https://codeforces.com/blog/entry/61587) mt19937 是 c++ 的一種隨機產生器 ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int randint(int lb, int ub) { return uniform_int_distribution<int>(lb, ub)(gen); } ``` ---- ## sample code(c++) ```cpp= mt19937 gen(chrono::steady_clock::now().time_since_epoch().count()); int randint(int lb, int ub) { return uniform_int_distribution<int>(lb, ub)(gen); } int main(){ int n = randint(1, 10); //產生 0~10 之間的任意整數 char ch = 'a'+randint(0, 25); //產生 a-z 之間的任意字母 vector<int> ord(n); iota(ord.begin(), ord.end(), 1); shuffle(ord.begin(), ord.end(), gen); cout << n << endl; for(int i : ord) cout << i << " "; cout << endl; } ``` ---- ## 練習產測資 隨便拿一場比賽練習每一題如何產測資 [2023 I2CP Pretraining Final Contest](https://codeforces.com/group/dnlUA4rsoS/contest/419656/problems) ---- ```shell= set -e g++ ac.cpp -o ac g++ wa.cpp -o wa for ((i=0;;i++)) do echo "$i" python3 gen.py > input ./ac < input > ac.out ./wa < input > wa.out diff ac.out wa.out || break done ``` --- ## How to Debug ? ---- ## Debug --- Print 大法 可能有問題的那段程式碼 把變數 print 出來 ```cpp= cout << "Before" << endl; for(int i = 0; i < n; i++){ cout << arr[i] << ' '; } cout << endl; . . . cout << "After" << endl; for(int i = 0; i < n; i++){ cout << arr[i] << ' '; } cout << endl; ``` ---- ## 這樣會有什麼問題 ? <span>1. debug 完 bug 忘記註解/刪掉<!-- .element: class="fragment" data-fragment-index="1" --><div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="1" --></span> <span> 2. debug 完把 printer 註解，但沒有註解乾淨<!-- .element: class="fragment" data-fragment-index="2" --><div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="2" --></span> <span> 3. 好麻煩喔 先把所有 cout 都註解la 再把要輸出的反註解<!-- .element: class="fragment" data-fragment-index="3" --> <div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="3" --></span> <span> 4. 喔 好像多註解到要輸出的答案了 <!-- .element: class="fragment" data-fragment-index="4" --> <div style="position: absolute; left: 5%;top: 120%">  </div><!-- .element: class="fragment" data-fragment-index="4" --></span> ---- ## 這樣會有什麼問題 ? penalty += 80(20 * 4)  ---- ## cerr debug 時，很常會用cout輸出每個變數的值 在這邊建議輸出debug的值時使用cerr 他輸出的東西只會出現在 Standard error stream 不會輸出在 Standard output stream 答案比對是比對 Standard output stream 的內容 因此就算忘記刪也不會造成影響 ```cpp= // __LINE__ 會輸出呼叫的位置在程式碼第幾行 cerr << "This is debug message on " << __LINE__ << " line : " << x << endl; ``` ---- ## cerr 問題 如果沒有刪掉可能造成 TLE ```cpp for(int i = 0; i < n; i++){ x *= 2; arr[x] += v; for(int j = 0; j < n; j++){ cerr << arr[j] << " "; } cerr << endl; } ``` 原本可能 $O(N)$ 的程式碼變成 $O(N^2)$ 或者常數太大 (輸出數量變成原本的兩倍) ---- ## Debugging template 讓你更好 debug 的工具 ---- ```cpp= [|1-6|7-12|] #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- ## #ifdef LOCAL 如果有 define LOCAL 那就會... ```cpp= #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) ``` 否則就會... ```cpp= #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- 在本機 define LOCAL ```cpp! g++ solve.cpp -D LOCAL ``` 則編譯時就會 define LOCAL 但每次都要打 -D LOCAL 很麻煩... ---- 還記得 alias ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow` ``` 改成 ```bash alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow -D LOCAL` ``` :happymention: ---- ## debug 變數 debug(x) ```cpp! string x = "abc"; debug(x); int y = 123; double z = 1.23; debug(y, z); ``` ---- ## debug 範圍 orange(begin, end) ```cpp= int arr[5]={2,1,4,3,5}; orange(arr, arr+5); vector<string> strVec = {"Alice", "Bob"}; orange(strVec.begin(), strVec.end()); ``` ---- ```cpp= ```cpp= #ifdef LOCAL // =========== Local =========== void dbg() { cerr << '\n'; } template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); } template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; } #define debug(args...) (dbg("#> (" + string(#args) + ") = (", args, ")")) #define orange(args...) (cerr << "#> [" + string(#args) + ") = ", org(args)) #else // ======== OnlineJudge ======== #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define debug(...) ((void)0) #define orange(...) ((void)0) #endif ``` ---- ## assert 他用來判斷一個條件是否成立， 如果條件成立則不會發生任何事 如果條件不成立，則會造成程式RE(Runtime Error) 通常用於 debug 不確定會不會錯 或者想 submit 時 不確定有沒有問題用的 ```cpp= assert(x <= 5); ``` ----  ```cpp= [|10-11|1-7,12|13|] long long fpow(int x, int y){ long long ret = 1; for(;y;y>>=1, x*=x){ if(y&1) ret = ret * x; } return ret; } int main(){ cin >> n; auto [x, y] = solve(n); assert(fpow(x, y) * y + fpow(y, x) * x == n); cout << x << " " << y << endl; } ``` ---- 或者想猜測資，判斷是否大於某個值，就可以assert 再加上 TLE 一起用 ~~每次可以把測資分三半去猜測資 複雜度 $O(log_3N)$~~ ```cpp= cin >> n; if(n >= 10){ // RE assert(0); } else if(n > 5){ // TLE while(1){} } else{ // WA return 0; } ``` ---- [Benq's submission](https://codeforces.com/submissions/Benq) [Who is Benq?](https://www.youtube.com/watch?v=xiDEsX0_MGE)  - 溢位 - 陣列超出範圍 - 邊界測資 n=1 n=2 n=bound --- ## 比賽策略與準備 - https://zhuanlan.zhihu.com/p/438790068 - https://hackmd.io/@sa072686/rke70TNtX?type=view