【進度】
競賽入門
- cin.tie(0)：解除自動清除緩衝區。
- ios::sync_with_stdio(0)：解除 cin、scanf 自動同步。
for(auto &it : a) it++;
for(auto it : a) cout << it << ' ';#include <sstream>
string s;
getline(cin, s);
stringstream ss;
ss << s;
while(ss >> i) cout << i << ' ';int a[n+1]; long long b[n+1];
b[0] = 0;
for(int i=1; i<=n; i++){
cin >> a[i];
b[i] = b[i-1] + a[i];
}
cout << b[r]-b[l-1] << '\n';b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + a;
cout << b[x2][y2] - b[x1-1][y2] - b[x2][y1-1] + b[x1-1][y1-1];資料結構 I
vector<int> v = {9,4,8,7};
cout << *v.begin() << ' ' << *v.rbegin(); //9 7
#include <utility>
pair<int, int> p = make_pair(1, 2);
cout << p.first << ' ' << p.second;
//sort: 優先比第一項，相同再比第二項
#include <tuple>
tuple<int, int, int> t = make_tuple(1, 2, 3);
cout << get<0>(t);#include <cstring>
string s = "hello world";
char c[s.size()+1];
strcpy(c, s.c_str());
cout << c;
cout << s.substr(6, 3); //wor(index, length)Deque (雙向佇列)
- 可以 push_front()。
- 缺點：速度比 vector 慢。
Priority Queue (優先佇列)
- 預設由大到小排序。
枚舉
搜尋
int a[1000001];
for(i=1; i<=100; i++)
for(j=1; j<=100; j++)
for(k=1; k<=100; k++)
a[i+j+k]++, a[i*j+k]++, a[i+j*k]++, a[i*j*k]++;
cout << a[n];貪心與基礎證明技巧
分治
分：Divide，把大問題分割成多個小問題。
治：Conquer，把小問題的答案合併起來得到大問題的解。
數學
快速冪：快速計算 a^b。[O(b) → O(logb)]
int fastpow(int a, int b){
int res = 1;
while(b){
if(b&1) res*=a; //is odd
a*=a;
b/=2;
}
return res;
}
質因數分解：2~根號n、LPF(最小質因數)
質數：埃氏篩法、線性篩(不重複刪)
最大公因數：__gcd(x,y)
貝祖定理：若 ax + by = c 存在整數解 ⇐⇒ gcd(a, b) | c
拓展歐幾里得演算法(extgcd)
同餘：模運算、模反元素(費馬小定理、建表法、拓展歐幾里得定理)
歐拉函數
中國剩餘定理
動態規劃(一)
用先前的最佳狀態來得到當前的最佳狀態。
Top-Down：遞迴。
圖論
度數 (degree)：一個點連接的邊數。
入度 (in-degree)：指向節點的邊數，deg+(v)。
出度 (out-degree)：節點往外指的邊數，deg−(v)。
簡單路徑 (simple path)：路徑上每個點只走過一次。
負環 (negative cycle)：權重和為負的環。
連通分量：一個集合內的點互相連通。
樹：n 個節點，n-1 條邊的有向無環圖。
vector<pair<int, int>> G[MAXN];
void build(){
cin >> n >> m;
for (int i=0; i<m; i++){
cin >> a >> b >> c;
G[a].push_back({b, c});
G[b].push_back({a, c});
}
}vector<int> G[MAXN];
bool vis[MAXN];
void dfs(int i){
vis[i] = true;
for(int e : G[i]){
if(!vis[e]) dfs(e);
}
}//每個城市都連通 = 每個城市都跟城市1相通
dfs(1);
for(int i=2; i<=n; i++){
if(!vis[i]){
ans.push_back({1, i});
dfs(i);
}
}//dis(u, i, v) = dep(u) + dep(v) − 2 × dep(i)
//取 i 的子結點中回傳的前兩大 DFS 值
int dfs(int i, int dep){
pair<int, int> mx(dep, dep);
for (int e : G[i]){
int tmp = dfs(e, dep+1);
if (tmp >= mx.first) mx={tmp, mx.first};
else if(tmp > mx.second) mx={mx.first, tmp};
}
ans = max(ans, mx.first+mx.second-2*dep);
return mx.first;
}
void bfs(){
queue<int> q;
q.push(1);
vis[1] = true;
while(q.size()){
int now = q.front();
q.pop();
for(int e : G[now]){
if(!vis[e]){
vis[e] = true;
q.push(e);
}
}
}
}二分圖：一張圖的節點分為兩個集合，且集合內部沒有邊的圖。
拓撲排序：用來解決圖上點的順序。
拓撲排序的圖必定是一張有向無環圖。
樹壓平