【筆記】三校聯合暑期培訓營

2022 新化高中 x 嘉義高中 x 薇閣高中 資研社聯合暑期培訓營GithubYouTube
【進度】

競賽入門

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

二分圖:一張圖的節點分為兩個集合,且集合內部沒有邊的圖。

拓撲排序:用來解決圖上點的順序。
拓撲排序的圖必定是一張有向無環圖。

樹壓平

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *