# 111 選手班 - 競程入門
###### tags: `宜中資訊` `CP`
## 自我介紹
[FB](https://www.facebook.com/Ccucumber12/)
## 競程介紹
- 競技程式 (Competitive Programming)
- 題型
- 技能
- [List](https://hackmd.io/@Ccucumber12/rkrPMogS_)
- 資料結構
- 演算法
- 技巧
- 思考
- 經驗
- 分析
- 用途
- 興趣
- 動腦
- 未來
- 實際應用
- 賽制
- OI 制
- ICPC 制
- 題型
- Batch (傳統題)
- Output Only (輸出題)
- Communication (互動題)
- TwoSteps (通信題)
- 評分
- Special Judge
- 聯集給分
- 連續給分
- 結果
- AC (Accept)
- WA (Wrong Answer)
- TLE (Time Limit Exceeded)
- MLE (Memory Limit Exceeded)
- RE (Runtime Error)
- CE (Compile Error)
## 競賽列表
### 臺灣
- 8: 成大暑期高中程式邀請賽
- 8: YTP
- 8: ISSC
- 10: HP Codewars
- 11: NPSC
- 8~12: 學科能力競賽
- 校內
- 東區
- 全國
- 3~5: 資訊奧林匹亞
- 初選
- 1! 2! 3!
### Online
- Google Code Jam
- Google Kick Start
- Facebook Hacker Cup
- Codeforces
- AtCoder
- USACO
## 資源
### 網路資源
[便宜的演算法比賽網路資源整理](https://hackmd.io/@pr3pony/HysEHoYe8?fbclid=IwAR2GaSpKV-wpHesS2BATwYrRDa_cFnBo7F78p6DDbXrj8kdXdk5T0HKovJE)
- [從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/)
- [cppreference](https://en.cppreference.com/w/)
- [cplusplus](https://cplusplus.com/)
- [AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)
- [板中資訊講義](https://sites.google.com/site/pcshic/zi-xun-pei-xun)
- [附中資訊講義](https://cp.wiwiho.me/lessons/)
- [建中資訊講義](https://tioj.ck.tp.edu.tw/articles?era=2021)
- [宜中資訊講義?](https://vjudge.net/article/2291)
- [IO wiki](https://oi-wiki.org/)
- [演算法筆記](https://web.ntnu.edu.tw/~algo/)
- [資訊之芽](https://www.csie.ntu.edu.tw/~sprout/algo2022/)
- [CP Algorithms](https://cp-algorithms.com/#navigation)
- [USACO Guide](https://usaco.guide/dashboard)
- [CodeForces EDU](https://codeforces.com/edu/course/2)
### 營隊課程
- 資訊之芽
- APCSCamp (臺大)
- PCCA Camp (交大)
- IONCamp (清大)
- IOICamp (臺大)
- AA競程
### Online Judge
- 宜中 http://infor.ylsh.ilc.edu.tw/
- 中文難題(建中) https://tioj.ck.tp.edu.tw/
- 中文經典題(南一中) https://toj.tfcis.org/oj/info/
- 模板練習 https://judge.yosupo.jp/
- 線上競賽 https://atcoder.jp/
- 線上競賽 https://codeforces.com/
- OI題 https://oj.uz/
- 中文題庫 https://www.luogu.com.cn/
- 老題庫 https://onlinejudge.org/
- 老題庫 http://poj.org/
- 主題練習 https://cses.fi/problemset/
- 主題練習 https://csacademy.com/
- 數學趣題 https://projecteuler.net/archives
## 複雜度
### 時間複雜度
- 大 $O$ 符號
- 1s $\approx 10^8$
- 常數 $O(1)$
- 線性 $O(n)$
- 指數 $O(2^n)$
- STL 複雜度
- `strlen()`
- `lower_bound(mp.begin(), mp.end(), k)`
- `void func(vector<int> v){}`
- `vector::erase()`
- 均攤分析
- 遞迴剪枝
- 常數
- 函式本身
- `unordered_map`
- `queue`、`vector`
- 算法本身
- Segment Tree / Treap
- Locality
- quick sort / merge sort
- Floyd-Warshall
- 矩陣乘法
- 分治法 (std::sort)
### 空間複雜度
- `int`: 4 Bytes
- 512 MiB $\to 512*2^{20}/4 = 134217728$
- 滾動陣列、動態開點、持久化技巧
## 比賽策略
- 考前
- 平時
- 學習新技術
- 複習、練習
- virtual
- 接近
- 不要碰新東西
- 複習模板
- 喇分
- 2020TOI pB
- 小測資
- 提示滿分解
- 時間策略
- **不要有 $0$ 分的題目**
- 時間
- 讀完所有題目
- 不用從頭寫到尾
- 了解自己能力與目標
- 不要鬼打牆
- 子題與滿分解
- 心態
- 適時換題
- 不要管別人在幹嘛
- #相信
- 其他
- 讀題時標記難度想法
- 吃東西尿尿
- 最後一分鐘都可以翻盤
## 你應該知道的東西
### `*` 和 `&`
#### 指標 (Pointer)
`int *ptr = &k;`
- 樹結構
- 動態記憶體
- Linked List
#### 參考 (Reference)
`int &ref = k;`
- 簡化實作
- 副函式傳入參數
#### 解參考 (Dereference)
`cout << *ptr << endl;`
- 取得(指標 / 迭代器)的值
#### 取址
`int *ptr = &k`
- 取得變數記憶體位址
### 三元運算子
```c=
int a = 3 ;
int n = (a % 2 == 1 ? 10 : 20) ;
// n = 10
// <statement> ? <if true> : <if false>
```
### Struct
```c=
struct point {
int x, y ;
info (int _x, char _y) {
x = _x ;
y = _y ;
}
point operator+(const point &a) const {
return point(x+a.x, y+a.y) ;
}
int square () {
return x*x + y*y ;
}
};
```
### 位元運算
- OR: `|`
- AND: `&`
- XOR: `^`
- NOT: `~`
- shift: `<<` / `>>`
### 迭代器 (Iterator)
- vector / set / map
- next() / prev()
```c=
#include<iostream>
#include<iterator>
#include<vector>
using namespace std;
int main(){
vector<int> ar = { 1, 2, 3, 4, 5 };
vector<int>::iterator ptr;
for (ptr = ar.begin(); ptr < ar.end(); ptr++)
cout << *ptr << " ";
}
```
### Stringstream
```c=
#include <sstream>
strinstream ss ;
string s ;
getline(cin, s) ;
ss << s ;
int n ;
while(ss >> n) {
cout << n << endl ;
}
```
### Random
- rand() *
- random_shuffle *
- mt19937
```c=
#include <random>
#include <chrono>
unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(seed);
uniform_int_distribution<ll> dist(1, 1e18);
int main(){
cout << rng() << endl;
cout << dist(rng) << endl;
shuffle(arr, arr+n, rng);
}
```
### Fstream
```c=
#include <fstream>
fstream fin, fout ;
fin.open("file_in.txt", ios::in) ;
fout.open("file_out.txt", ios::out) ;
int n ;
fin >> n ;
fout << n + 1 << endl ;
fin.close() ;
fout.close() ;
```
### C++ 11
- using
- auto
- range-based for
- lambda
- tie
- tuple
## 常見錯誤
### WA
- int, long long 比較
- operator 計算順序
- `a >> 1 + 2`
- `a & b == 1`
- 未初始化、歸零
- 0 / 1-based
- 輸出格式
### RE
- 戳到陣列外面
- 數學運算錯誤 (除以 $0$)
- local array 大小
- undefined behavior
- `int a[n];`
- overflow
- `1<<62`
- 自定義 `sort` 出現等號
```cpp
bool cmp(int a, int b) {
return a >= b;
}
```
### TLE
- 想錯了、寫錯了、算錯了、看錯了
- 遞迴沒有終止
- 搞錯函式確切複雜度
## 常見技巧
### 輸入輸出優化
```c=
ios::sync_with_stdio(false);
cin.tie(0) ;
cout.tie(0) ;
#define endl '\n'
```
### Define
```c=
#define F first
#define S second
#define ALL(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<(n);++i)
#define REP(i,a,b) for(int i=(a);i<=(b);++i)
```
### Debug
```c=
#ifdef local
#define debug(...) cerr<<"#"<<#__VA_ARGS__<<" = ";dbg(__VA_ARGS__);
#else
#define debug(...)
template<typename T> void dbg(T x){ cerr<<x<<endl; }
template<typename T, typename ...A> void dbg(T x, A ...y){ cerr<<x<<", "; dbg(y...);}
```
### Assert
```c=
assert(...);
```
### Using
```c=
using ll = long long
using pii = pair<int,int> ;
using pll = pair<ll, ll> ;
```
### 常數
```c=
const int INF = 0x3f3f3f3f ;
const ll LLINF = 0x3f3f3f3f3f3f3f3f ;
const MOD = 1e9 + 7 ;
```
### <bits/stdc++.h>
- include all libraries
- not always available
### Default Code
- 線上賽
- 東區學科
- ICPC
- https://pastebin.com/nft7fWe6
### Type Casting
```c=
int a = 1, b = 2 ;
ll c = 1LL * a * b ;
double d = 1.0 * b / a ; // 1.0f is float
ll e = (1LL << 60) ;
```
### EOF
```c=
int n ;
while(cin >> n) {
// do something
}
```
```c=
int n ;
while(scanf("%d", &n) != EOF) {
// do something
}
```
### 重複 T 次
```c=
void solve() {
// solution
}
int main() {
int T = 1 ;
cin >> T ;
while(T--) {
solve() ;
}
}
```
### 行尾空白
```c=
for(int i=0; i<n; ++i) {
cout << a[i] << " \n"[i == n-1] ;
}
```
### 更好的選擇
| Good | Bad |
| ------------ | ----------- |
| double | float |
| emplace_back | push_back |
| n >>= 1 | n /= 2 |
| global array | local array |
| ++i | i++ |
## 指令編譯
`g++ -o a.out -fsanitize=address -g -Wall -Wextra -O2 file.cpp`
- `-o a.out` 輸出檔名
- `-fsanitize=address -g` 告訴你哪裡戳到陣列外面
- `-Wall -Wextra` 更多警告
- `-O2` 優化
## 出題
[關於出題 I](https://oi-wiki.org/contest/problemsetting/)
[關於出題 II](http://dreamoon4.blogspot.com/2015/04/blog-post.html)
- testlib.h
- https://github.com/MikeMirzayanov/testlib
- https://oi-wiki.org/tools/testlib/
- https://codeforces.com/testlib
- TPS
- https://github.com/ioi-2017/tps
- CMS
- https://cms-dev.github.io/
- https://github.com/melongist/CSL/tree/main/CMS
- polygon
- https://polygon.codeforces.com/
- https://oi-wiki.org/tools/polygon/
## 其他可以學的東西
- 終端機指令
- Unix 系統
- python
- 數學 / 英文
- 計算機概論
- Vim
- markdown
- LaTeX
Sign in with Wallet
Connect another wallet