競賽技巧 & 競賽介紹

Introduction to Competitive Programming
2/7

快讀/快出/換行 " \n"[i == n]
GCC pragma
陣列開法(全域變數)&&const
memset(arr,value,sizeof(arr)) -1,0,0x3f3f3f3f
mt19937(hash<string>("
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
"))
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標準輸入略慢一點

快讀/快寫 : 只能處理整數讀入/輸出，但是要比標準輸入輸出函數都快得多。

快讀

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;
}

快寫

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述句，可以

for(int i=1;i<=5;i++){
	cout<<i<<" \n"[i==5];
}

pragma GCC

只需要無腦加在最前面就好，原理為放棄編譯速度/運行速度/代碼大小/指標指向去增加其他東西

#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

#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宣告出來的東西在之後就不能再更改，同時這樣開在全域就也不需要再函式間傳遞也不用考慮初始化的問題。

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>("

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

"))

如果要使用random等函式，不推薦在比賽中使用時間種子碼以及rand，而是推薦使用這個mt19937，產生高性能隨機數，且更為隨機以及可測試一點。

#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
答對一題會有一顆氣球

各種比賽

見連結

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









#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
跟隊友溝通要放什麼演算法
或者如果語法不熟也可以考慮放

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

linux 基本指令







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




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 檔

其他編譯參數








-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 掉

alias [name]='[value]'

等同於 c++ 內的 #define
#define ll long long

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow`

使用 Alias 之後

g++ solve.cpp

等價於

g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow solve.cpp

產生質因數


factor 100

debug

競賽中或者平常寫題目時，如果遇到 bug 不能及時找到
有以下方法

團體賽中，可以把 code 印出來自己到旁邊 debug，給其他隊友上機寫其他題目 (前提為有其他題目可以開)
團體賽中，可以把 code 印出來給隊友 debug， (前提為能有效跟隊友溝通並且看得懂你的code)
好好寫對拍

對拍

步驟

寫對拍的 script
寫一份暴力程式碼 ac.cpp
寫一份產生隨機測資的程式碼 gen.py/gen.cpp

對拍的 script

先將兩份程式碼分別編譯成 ac, wa
不斷用 gen.py 產生測資放到 input 檔案裡面
再把 input 檔案分別為給 ac, wa 兩份執行檔
用 for 迴圈一直跑到 output 內容不同為止
set -e 可以偵測程式 RE 時會停下來











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

跑到停下來後有兩種可能

RUNTIME ERROR

WRONG ANSWER

為甚麼要用對拍

找不到好的 case 能讓他自己跑先寫其他題目
寫暴力程式碼的時間遠比多吃一次 20 penalty 還要來的划算
對拍可以重複驗證程式正確性，de 完原本的 bug 可以再跑一次對拍

因此當比賽時，如果對於錯誤毫無頭緒，
不應該只是盯著程式碼看，而是開始寫對拍才是最有效率的做法

而平時練習、作業找不到bug的情況也應該要先對拍
真的找不到問題對拍也對不到再去問其他電神錯在哪

步驟

寫對拍的 script
寫一份暴力程式碼 ac.cpp
寫一份產生隨機測資的程式碼 gen.py/gen.cpp

寫一份暴力程式碼 ac.cpp

聽起來好麻煩，為了 debug 還要多寫一份 code
而且不一定寫得出來還有可能錯，怎麼辦?

如果連暴力的程式碼都寫不出來那你應該多練練你的實作能力…

如果不知道怎麼寫請參考早上 brute force 講義

善用 next_permutation 以及好好熟悉遞迴
沒有暴力寫不了的程式碼只有你不練不夠實作能力

步驟

寫對拍的 script
寫一份暴力程式碼 ac.cpp
寫一份產生隨機測資的程式碼 gen.py/gen.cpp

產生隨機測資 (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









from random import *

n = randint(3, 6)

arr = [i+1 for i in range(n)]
shuffle(arr)

print(n)
print(*arr)    #輸出 arr 的內容並且用空格隔開

隨機產生一個長度為 n 的小寫字母字串






s = ""
n = randint(1, 10)

for i in range(n):
    s += chr(ord('a') + randint(0, 25))
print(s)

隨機產生一棵樹

每次從比自己小的節點選一個當連接自己的邊







from random import *

n = randint(3, 6)

print(n)
for i in range(2, n+1):
    print(randint(1, i-1), i)

隨機產生無自環無重邊的一張連通圖

無自環可以判斷兩個點不相同
無重邊可以用 dict/map 紀錄哪些邊用過了

連通圖 = 樹 + 一些額外的邊

隨機產生無自環無重邊的一張連通圖

























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++

mt19937 是 c++ 的一種隨機產生器




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++)
















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











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 出來













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;

這樣會有什麼問題 ?

1. debug 完 bug 忘記註解/刪掉

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

2. debug 完把 printer 註解，但沒有註解乾淨

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

3. 好麻煩喔先把所有 cout 都註解la 再把要輸出的反註解

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

4. 喔好像多註解到要輸出的答案了

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

這樣會有什麼問題 ?

penalty += 80(20 * 4)

cerr

debug 時，很常會用cout輸出每個變數的值
在這邊建議輸出debug的值時使用cerr

他輸出的東西只會出現在 Standard error stream
不會輸出在 Standard output stream

答案比對是比對 Standard output stream 的內容
因此就算忘記刪也不會造成影響


// __LINE__ 會輸出呼叫的位置在程式碼第幾行
cerr << "This is debug message on " << __LINE__ << " line : " << x << endl;

cerr 問題

如果沒有刪掉可能造成 TLE

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 的工具












#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
那就會…






#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

在本機 define LOCAL

g++ solve.cpp -D LOCAL

則編譯時就會 define LOCAL

但每次都要打 -D LOCAL 很麻煩…

還記得 alias

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow`

改成

alias g++ = `g++ -std=c++14 -fsanitize=undefined -Wall -Wextra -Wshadow -D LOCAL`

:happymention:

debug 變數

debug(x)

string x = "abc";
debug(x);
int y = 123;
double z = 1.23;
debug(y, z);

debug 範圍

orange(begin, end)





int arr[5]={2,1,4,3,5};
orange(arr, arr+5);

vector<string> strVec = {"Alice", "Bob"};
orange(strVec.begin(), strVec.end());













```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 時不確定有沒有問題用的


assert(x <= 5);














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)\)~~










cin >> n;
if(n >= 10){       // RE
    assert(0);
}
else if(n > 5){    // TLE
    while(1){}
}
else{              // WA
    return 0;
}

Benq's submission
Who is Benq?

溢位
陣列超出範圍
邊界測資 n=1 n=2 n=bound

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.

競賽技巧 & 競賽介紹

快讀/快出/換行 " \n"[i == n]

快讀

快寫

換行 " \n"[i == n]

pragma GCC

實用且常用pragma

陣列開法(全域變數)&&const

memset(arr,value,sizeof(arr))

mt19937(hash<string>(" Image Not Showing Possible Reasons The image file may be corruptedThe server hosting the image is unavailableThe image path is incorrectThe image format is not supported Learn More → "))

for(auto i : arr )

#define int long long

__int128

begin, rbegin, end rend

prev, next

int main(){ int T=1; //cin >> T; while(T–) solve(); }

大學競賽程式賽制介紹

各種比賽

比賽排名

開場

為甚麼要先打 default code 呢?

看記分板 & 看別人的氣球

印code

評估題目

補充血糖

平常團隊訓練

平常個人訓練

25 頁 A4單面紙本資料

DEBUG技巧

為什麼要學 linux 指令 ?

ICPC 國際大學生程式設計競賽

NCPC 全國大專電腦軟體設計競賽

如果我的電腦是 Windows ?

Windows Subsystem of Linux (WSL)

linux 基本指令

編譯檔案

其他編譯參數

Alias

產生質因數

debug

對拍

步驟

對拍的 script

為甚麼要用對拍

步驟

寫一份暴力程式碼 ac.cpp

步驟

產生隨機測資 (python)

隨機產生一組 1~n 的 permutation

隨機產生一個長度為 n 的小寫字母字串

隨機產生一棵樹

隨機產生無自環無重邊的一張連通圖

隨機產生無自環無重邊的一張連通圖

產生隨機測資 (c++)

sample code(c++)

練習產測資

How to Debug ?

Debug –- Print 大法

這樣會有什麼問題 ?

這樣會有什麼問題 ?

cerr

cerr 問題

Debugging template

#ifdef LOCAL

debug 變數

debug 範圍

assert

比賽策略與準備

mt19937(hash<string>("

Image Not Showing Possible Reasons
The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported
Learn More →

"))