歐幾裡得算法 gcd(a,b)=gcd(b,r) 已知 a\b=q...r a=bq+r d=a,b 的公因數 → d 為 a-bq的因數 → d 為 r 的因數 → a,b 的公因數為r的因數

Rika 的冒險 (hinamizawa) 第k近點對(k_close_pair) ㄌㄌ矩陣 (loli_matrix) 幫幫夏哥 (matsuri) 遜砲音音 (momosuzu) 愛上火車 (station)

政見 社長參選人 : 11213杜靖智 副社參選人 : 11334羅文謙 我們期待藉由擔任幹部以執行以下政見 壹、課程方面 1. 提前公開課表、簡報並提供旁聽機制 實行原因 : 有時社員對本周課程已經有些研究，但礙於分組必須要留在自己的組內上課, 而無法到其他組別擴展多方向的技能。而現行教學簡報公布時間較晚, 如果直接開放旁聽, 社員不能提前得知詳細課程內容, 無法對下周社課的選擇做出準確判斷。

請說明分治法及其應用，字數不限，如能搭配例題/圖更佳。 https://hackmd.io/@arutoria/toj55 現在是高一上學期，T23剛學會使用迴圈、陣列(也就是說，不需要教基礎語法)，請撰寫一份TOJ55的解析，教導T23們排序演算法以及lower / upper bound的使用。 https://hackmd.io/@arutoria/rkxHoO_FL 請盡量找出這份code中(這題是TOJ 120)，可改進的地方(包含bug , coding style)，並以條列式說明。 https://hackmd.io/@arutoria/B1HEuu_K8

[TOC] :::warning 本章會用到排序演算法 顧名思義可以把一堆數字從小排到大或從大排到小 本章會用 STL sort 來排序 如果想知道排序實作細節請點這裡 ::: 二分搜 二分搜基本概念

分治法:分而治之 分: 切分問題 治: 解決、合併問題 很多時候大的問題很難解決，但是當規模較小的時候我們能直接知道答案。 那我們何不嘗先解決小的問題，在解決大的呢? :::info 分治步驟: 我有一個問題 -> 如果小到我們知道答案直接回答 否則繼續問更小的問題 -> 想辦法用兩個小問題的答案湊出原本問題的答案。 :::

有一個序列 1...n 有兩種操作 1.swap(a,b) 把兩個東西互換 2.recorver(l,r) l<=i<=r 如果這個位置 i 上不是 i 那就把位置 i 上的東西跟 i swap, 並且記有效次數1 請輸出每一次操作 2 的有效次數 N=5e5, Q=5e5

Floyd Warshall === ###### tags: `Algorithm` floyd warshall 是 dp 的思考方式 `dp(i,k,j) = min( dp(i,k-1,j), dp(i,k-1,k)+dp(k,k-1,j))` 可以用 `O(n^3)` bottom-up, 並且壓掉空間複雜度可以壓掉一維變 `O(n^2)` ```cpp //儲存一張圖 for (int i=0,u,v,w; i<m; i++) cin >> u >> v >> w, dis[u][v] = w; for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]); ```

# TIOJ 1014. 打地鼠 ###### tags: `Ans` ### 轉移式 * `dp[s][i]` * s 代表地鼠的狀態, 如果第 x 位是 1 代表第x支還活着 * i 代表最後是敲下哪一個位置的地鼠(結尾) * `dp[s][i] = min{ 0<=k<n | dp[在敲i之前][k結尾]+行走時間+一段時間到t[i]的倍數 }` * 因爲地鼠是有週期性的, 所以值還要在加上一段時間變成週期的倍數 * $dp(s,i) = min\{r\ |\ 0\leq k<n,\ r=([(dp(s\&~(1<<i),k)+abs(i-k)]-1)/t[i]+1)*t[i]\}$ * $[(dp(s\&~(1<<i),k)+abs(i-k)]$ * 在敲 i 之前, 最後一個敲 k 的時間 + 從 k 跑到 i 的時間 * $((x-1)/t[i]+1)*t[i]$ * 把 x 變成 t[i] 的倍數 m, m>=x * (x/t[i]+1)*t[i] 後小數點會被去掉加 1 再把

ZOJ B397. 最長共同子序列 === ###### tags: `Ans` ```cpp= #include<bits/stdc++.h> using namespace std; const int maxL = 40; unordered_set<string> sol[maxL][maxL]; string a, b; int n, m; inline bool cmp ( const string *a, const string *b) { return *a < *b; } int dp[maxL][maxL], used[maxL][maxL], u; int lcs (int i, int j) { if (used[i][j]<u) { used[i][j] = u; if (i==n || j==m) { dp[i][j] = 0; sol[i][j].insert(""); } else if (a[i] == b[j]) { dp[i][j] = lcs(i+1,j+1)+1; for (aut

TOJ 126. Irritation === ###### tags: `Ans` #### 先備知識 * 二分搜 [by sa072686](https://hackmd.io/@sa072686/APCS_HARD/https%3A%2F%2Fhackmd.io%2Fs%2Frk_5Ee0K7) * DFS [by sa072686](https://hackmd.io/@sa072686/APCS_HARD/https%3A%2F%2Fhackmd.io%2Fs%2Fr18hJX1TX) ## 想法 題目要求: **所有可能分數中的, 第一個大於等於詢問的分數** 例如: 可能有: `10, 20, 38, 56, 76` 詢問 20, 輸出 20 詢問 35, 輸出 38 詢問 50, 輪出 56 我們把所有可能性算出來, 再利用 `lower_bound` 搜出答案 ## 暴力 打算生成所有解的話, 可能打算這樣做 ```cpp int sco[maxN]; // 所有配分 int pos[maxS], r=0; void gen (int m, int s) /

LCA === ###### tags: `Algorithm` ## 提示 * DFS : 建表 $2^n$ 輩祖先, 紀錄時間戳(用來判祖先) ```cpp void DFS( int u, int p, int d) { tin[u] = t++; anc[u][0] = p; used[u][0] = time; for( int i=1; 1<<i < d; i++) { anc[u][i] = anc[ anc[u][i-1] ][i-1]; //used[u][i] = time; } for( vector<int>::iterator v=adj[u].begin(); v!=adj[u].end(); v++) { DFS( *v, u, d+1); } tout[u] = t++; } ``` * 判

# Iterative-SegmentTree [by OmeletWithouEgg](https://omeletwithoutegg.github.io/2019/12/07/Iterative-SegmentTree/) ###### tags: `Algorithm` --- ## 例題 RMQ 給出序列, 支援幾個操作 * 查詢區間最大值 query(l,r) * 區間加值 modify(l,r,x) ----  --- ## construct  ---- ```cpp const int N = 1<<18; int tr[N<<1], n; ``` * root := *1* * left node:= *i<<1* * right node:= *i<<1|1* * parent:= *i>>1* * brother:= *i^1* * leaf:= n~2n-1

Binary Indexed Tree(BIT) === ###### tags: `Algorithm` ## 詳解 我們知道我們可以利用前綴和來處理區間和, 而 BIT 是一種高效處理前綴和的資料結構 如何儲存前綴和呢? 對於 1~n 的整段合起來的資料,不斷的往下儲存左半邊. 可以發現剛好有空位放下全部的區段  如此 `a1+...+a7` 我們可以表示成 `BIT[111] + BIT[110] +　BIT[100]`  可以觀察到, 當我們減去位置 n 的 lowbit, 就能得到上一層 重複動作, 能找出所有組成位置 n 的區塊 ```cpp int sum( int n) { int s=0; while(n>0) { s += BIT[n]; n-=lowbit(x); } return s; } ``` 得到前綴和後, 就可以查詢區間資料了 ```cpp int query( int a, i

Spare Table === ###### tags: `Algorithm` Sparse Table 用來解決區間極值問題 ## table  ### query * `q(a,b)` * find level k * `k=log(b-a+1)` * `merge(sp[k][a],sp[k][b-(1<<k)+1])` * `(1<<k)`: kthlevel length * ex: `q(1,7)` * level k = 2 * `merge(sp[2][1],sp[2][3])` ## code ```cpp const int N = 5e5, K = 30; int st[K][N], n; int build () { for (int i=0; i<n; i++) cin >> st[0][i]; for (int j=1; (1<<j)<=n; j++) for (int

Segment Tree === ###### tags: `Algorithm` ## 思路 * root = 1, left node = (n<<1), right node = (n<<1|1) * build * set l, r * if (l==r) get arr value * else gen child, pull(merge) * query * if query cover node complete * return val * else if l or r touched * query l or r (query don't change), merge ## Code ```cpp #define maxN (1000000+10) #define L(x) (x<<1) #define R(x) ((x<<1)|1) //st int l[maxN], r[maxN], val[maxN]; inline void pull( int x) { val[x] = min

# UVa 271 Simply Sintax ###### tags: `Algorithm` `Ans` ```cpp= #include<iostream> using namespace std; #define maxN 10000000 int rear; int stk[maxN]; int main() { ios::sync_with_stdio(0); cin.tie(0); string s; while (getline(cin,s)) { rear=0; int len=s.size(); for( int i=0; i<len; i++) { if (s[i]=='N') { stk[rear++] = -1; } else if (s[i]=='C' || s[i]=='D' || s[i]=='E' || s[i]==

# Mod 取模 ###### tags: `Algorithm` ## 定理 ::: info * 可以比照等號計算(除了除法,必須除數k必須和模數m互質,gcd(k,m)=1) * ==重要卻基本 `a ≡ a%m `== a 在除了除法以外 a%m 做其他運算的結果≡ a ::: #### 例題(1) > **15^8001 X 22^4781 X 11^3 除以7的餘數為多少** ``` 15 ≡ 1 (mod 7) 22 ≡ 1 (mod 7) 11 ≡ 4 (mod 7) ``` 1.根據上面==餘的相乘性質的次方公式== ``` 15^8001 ≡ 1^8001 (mod 7) 22^4781 ≡ 1^4781 (mod 7) 11^3 ≡ 4^3 (mod 7) ``` 2.然後上面三條可以相乘 (根據上面==同餘的相乘性質==) ``` 15^8001 X 22^4781 X 11^11 ≡ 1^8001 X 1^4781 X 4^3 (mod 7) 15^8001 X 22^4781 X 11^11 ≡ 64 (mod 7)

數論 === ###### tags: `Algorithm` `Todo` * a|x a 是因數 ## 費馬小定理(唬爛法) * a^p-1=1 ```cpp #define _for(i,a,b) for(int i=(a);i<(b);i++) #include <iostream> #include <random> using namespace std; long long power(long long a, long long n,long long m)// power(a, n) 表示詢問 a^n { long long tmp = a,ans = 1; while (n) { if (n&1) { ans = tmp*ans%m; } n /= 2; tmp = tmp*tmp%m; } return ans; } mt19937 mt(123); int main() { long long p; while (cin>>p) { bool isPrime = true; _for (i, 0, 5

Binary Seach, 倍增法 === ###### tags: `Algorithm` ## 整數二分搜 ***以搜8為例***  ### upperBound_a, lowerBound_a * 排除右邊 * lw_a 向右排除 >= * up_a 向右排除 > * ` m = (l+r+1)>>1 ` 避免 m 一直留在左邊進入無窮迴圈 ```cpp // seaching up_a int l, r, m; while (l<r) { m = (l+r+1)>>1; if (arr[m] > tar) { r = m-1; } else { l = m; } } retunr l; ``` ### upperBound_b, lowerBound_b * 排除左邊 * lw_b 向左排除 < * up_b 向左排除 <= * ` m = (l+r)>>1 ` 避免 m 一