# 數論
## 計算外積
* 加絕對值前，若計算結果為負數，代表從A走到B需要「順時鐘」
* 加絕對值後的計算結果代表包含OA、OB兩邊的平行四邊形面積
例題:
* 題目連結: https://cses.fi/problemset/task/2189/
* 解題思路: 利用外積的特性判斷方向解題
## 計算內積
* 判斷平行: 內積=兩個向量的長度相乘
* 判斷垂直: 內積=0
## 判斷點是否在線段上
* 若外積=0且內積<=0
* 以下圖A、B、C點為例，CA X CB=0 且 CA dot CB <0 ，故點C在AB線段上
例題:
* 題目連結: https://cses.fi/problemset/task/2190/
* 解題思路:
1. 判斷L1是否在線段P1P2上、L2是否在線段P1P2上、P1是否在線段L1L2上、P2是否在線段L1L2上
## 使用外積計算任意多邊形面積
兩個相鄰的向量一直外積，最後再加絕對值就好
題目連結: https://cses.fi/problemset/task/2191/
## 判斷某點是否在多邊形內
* 題目連結: https://cses.fi/problemset/task/2190/
* 解題思路: 利用外積的特性判斷方向解題
1. 假設某點a座標為(x,y)，則設定一個遙遠的假想點 r(x+1,y+1e15)
2. 分別拿多邊形的每條邊跟ar線段判斷相交情形
* 若發現點a在某條多邊形的邊上，則為BOUNDARY這種case；
* 若兩條線段相交於一點，則counter++
3. 判斷counter，如果是偶數，代表從遙遠的假想點走到點a的過程中，遵循「進去」 -> 「出來」 -> ...，最終點a停留在「出來」的狀態(代表在多邊形外)；反之則在多邊形內
## 凸包
## 盧卡斯定理
用於處理(Cn取m)%p的問題，其中n,m 是很大的數，p是沒很大的質數
## 擴展盧卡斯定理
用於處理(Cn取m)%p的問題，其中n,m 是很大的數，p是沒很大的數
* 利用中國餘數定理將p拆分成數個互質的數計算
# 圖論
## 求整張圖是否為SCC
1. 從點1開始DFS，檢查1是否可以走到所有點
2. 反轉所有邊，再從1開始DFS一次，檢查1是否可以走到所有點 (對於原圖來說，就是檢查是否所有點都可以走到1)
3. 若1是否可以走到所有點，且所有點都可以走到1，代表整張圖的點都可以到任意點，即為SCC
題目連結: https://cses.fi/problemset/task/1682/
## SCC分群
將互為SCC的這些點標記成相同的數字
先 DFS，以 DFS 結束順序將點放入 stack。
從"最晚"結束的點開始在逆圖上 DFS，將 DFS 所能走到的點標記為同一個 SCC。
處理完所有點就結束。
# Range Queries
## 最基本的線段樹---區間查詢、單點修改
```cpp
vector<llt> a;
vector<llt> tree(1000000,-1);
//0-index，左閉右開
//api:
//build(0,0,n); (當前節點，左界，右界)
//update(0,0,n,k-1,k,u); (當前節點，左界，右界，欲更新的左界，欲更新的右界，更新的值)
//query(0,0,n,a-1,b); (當前節點，左界，右界，欲查詢的左界，欲查詢的右界)
// ex 當前條件定義:
//now=0, left=0, right=7
void build(llt now,llt left,llt right)
{
if(right-left==1)
{
tree[now]=a[left];
return;
}
build(now*2+1,left,(left+right)/2); //遞迴左子樹
build(now*2+2,(left+right)/2,right); //遞迴右子樹
tree[now]=min(tree[2*now+1],tree[2*now+2]); //merge
}
void update(llt now,llt left,llt right,llt goal_left,llt goal_right,llt val)
{
if(left==goal_left && right==goal_right)
{
tree[now]=val;
return;
}
llt mid=(left+right)/2;
if(goal_right<=mid) update(now*2+1,left,mid,goal_left,goal_right,val);
else if(mid<=goal_left) update(now*2+2,mid,right,goal_left,goal_right,val);
else
{
update(now*2+1,left,mid,goal_left,mid,val);
update(now*2+2,mid,right,mid,goal_right,val);
}
tree[now]=min(tree[2*now+1],tree[2*now+2]);
}
llt query(llt now,llt left,llt right,llt goal_left,llt goal_right)
{
if(left==goal_left && right==goal_right)
{
return tree[now]; //ex: query [0,8]
}
llt mid=(left+right)/2;
if(goal_right<=mid) return query(now*2+1,left,mid,goal_left,goal_right); //向左遞迴求解 ex: query [0,4]
else if(mid<=goal_left) return query(now*2+2,mid,right,goal_left,goal_right); //向右遞迴求解 query [4,8]
else
{
//向左右遞迴求解
//ex: query [2,6]，分成 query [2,4] 跟 query [4,6]再取min
return min(query(now*2+1,left,mid,goal_left,mid),
query(now*2+2,mid,right,mid,goal_right));
}
}
```
## 線段樹+二分搜
```
輸入:
8 5 //8間旅館按順序從左到右，五組客人
3 2 4 1 5 5 2 6 //各旅館還能容納的人數
4 4 7 1 1 //每一組客人的人數
輸出:
3 5 0 1 1
//針對每組客人，輸出從左邊數來第一間符合條件的旅館位置，若找不到符合條件的旅館，則輸出0
```
解法:
* 建一棵求區間最小值的線段樹
* 欲求某組客人人數為8的query，一開始now=root，並查看其左右子節點
* 若左右子節點皆>=8，往左子節點走 (因為要找左邊數來第一間符合條件的旅館，故若兩邊皆符合條件時，左邊的優先)
* 若左子節點<8，右子節點>=8，往右子節點走
* 若左子節點>=8，右子節點<8，往左子節點走
* 若左右子節點皆<8，輸出0
## 懶標線段樹---區間查詢、區間修改
懶標的存在目的: 當進行區間修改時，不要整棵樹都更新，而是將欲修改的資訊暫時存入某個區間的tag中，等query到的時候再下放
實作上，開一個跟線段樹一樣的一維陣列，並透過相同的index對應來代表線段樹上每個節點的tag值
ex: 在一棵左閉右閉0-base 區間最小值線段樹中，欲將[0,4]的值都修改成20
* 原做法: 每個節點都要更新，時間複雜度O(2n)
* 懶標作法
* update [0,4]=20
* 當前節點[0,7]，欲update [0,4]，拆分子問題: update [0,4] -> update [0,3] + update [4,4]，並分別遞迴左右更新
* 先遞迴左邊，當前節點[0,3]，欲update [0,3]，**更新當前節點，將子節點打上tag後便直接返回**
* query [0,2]
* 當前節點[0,7]，欲query [0,2]，往左子節點查詢
* 當前節點[0,3]，欲query [0,2]，拆分子問題: query [0,2] -> query [0,1] + query [2,2]，並分別遞迴左右取得答案
* 先遞迴左邊，當前節點[0,1]，欲query [0,1]。**先使用tag更新當前節點，並將其子節點打上tag**，接著返回答案
## 樹壓平
* 概念: 將一棵樹使用DFS 歐拉序編號後，轉化成線段樹的問題
ex: 需要一次性修改某節點與其所有子節點的值，且需要及時查詢某節點與其所有子節點的最大值等
* 這棵樹會被轉成 [1,2,4,5,3,6,7]
# tree algorithm
## 輕重練剖分
### 應用場景
* 假設節點上的數字表示該節點的值
* 給定range=[4,10]，求node_4到node_10間如圖所示的區域，其區間和為多少?
名詞定義:
(本例的nodeID 不等於 DFS歐拉序，輕重鍊剖分的DFS歐拉序需先走重鍊)
### 程式實作
```cpp
//這個函式用以欲處理輕重鍊剖分所需相關資訊
//i是當前節點編號，fa是父節點編號
void dfs1(int i, int fa){
parent[i] = fa; //節點i的父節點
depth[i] = depth[fa] + 1; //節點i的深度
child[i] = 1; //節點i子樹大小 (包含節點i本身)
maxson[i] = 0; //節點i「其子節點中子樹大小最大」的點，其節點編號 (即節點i的重子節點)
for(int ele: graph[i]){
if(ele == fa) continue;
dfs1(ele, i);
child[i] += child[ele];
if(child[ele] > child[maxson[i]]) maxson[i] = ele;
}
}
```
```cpp
//這個函式用以找出每個節點的鍊頭
//i是當前節點編號，top是節點i的鍊頭
void dfs2(int i, int top){
top_id[i] = top; //節點i的鍊頭
rematch[ord] = i; //儲存id的逆向關係
id[i] = ord++; //id 存的是dfs 歐拉序，ord是全域變數，每次使用後會+1
if(maxson[i]) dfs2(maxson[i], top); //如果節點i有重子節點，便會dfs重子節點
for(int ele: graph[i]){ //dfs除了重子節點外的其他節點
if(ele == parent[i] || ele == maxson[i]) continue;
dfs2(ele, ele);
}
}
```
```cpp
//這個函式用以處理query
//a,b是query的左界跟右界 (nodeID)
void decom(int a, int b){
//node a跟node b在不同鍊上的情況
while(top_id[a] != top_id[b]){
//先做比較深的鍊，故需確保node a所在的鍊比較深
if(depth[top_id[a]] < depth[top_id[b]]){
swap(a, b);
}
ans += query(id[top_id[a]], id[a] + 1, 0, n);
//讓node a跳到比較淺的鍊繼續query
a = parent[top_id[a]];
}
//node a跟node b在同一條鍊上的情況
if(id[a] > id[b]){
swap(a, b); //讓a的歐拉序永遠小於b的歐拉序
}
ans += query(id[a], id[b] + 1, 0, n); //線段樹的query
cout << ans << "\n";
}
```
* node a跟node b在不同鍊上時的拆分例子
## 動態樹問題
* 使用 LCT 解題
# 字串演算法
## Trie (字典樹)
## KMP
若想確認字串 m 是否出現在字串 n 中
1. 首先，需建表紀錄 m 的最長共同前後綴
## AC 自動機
若想確認字串 m 是否出現在字串 n 中，但這樣的字串 m 可能會有很多個，此時便會用到 AC 自動機的技巧
時間複雜度: O(n+sum(m$_{1-k}$))
# LCA
問題定義: 給定一棵樹，試求任兩個節點的最低的共同祖先是誰?
先使用倍增表，建表求出樹中的每個節點往上跳 $2^i, i=1, 2, ...$ 格後會到哪個節點
接著兩個節點 i, j 先跳到 min(i 深度, j 深度):
若此時在同一個點便是答案
若此時不在同一個點，則可以利用倍增表 + 二分搜來找出答案
# 經驗談
1. 浮點數有關的題目記得
1. 將浮點數強制轉型成整數前，加上 1e-9
2. 比較浮點數 a , b 是否相等時，應該寫成 if(abs(a-b)<=1e-6)
3. 使用 setprecition() 印出更精確的數字
```cpp
cout<<fix<<setprecition(10)<<a<<endl;
```
2. 從一個字串中，每次拔掉一個字母，並希望新字串字典序最小
ex: abcba -> abba -> aba -> aa -> a
維護一個單調非嚴格遞增的Stack，從該Stack中pop掉的字母便是要拔的
3. 有時候可以善用倒扣的技巧，例如
```cpp
void f(string s,llt num,llt pos)
{
stack<char> Stack;
llt counter=1; //這個變數是多的
for(llt i=0;i<s.size();i++)
{
while(counter<num && !Stack.empty() && Stack.top()>s[i])
{
Stack.pop();
counter++;
}
Stack.push(s[i]);
}
...
```
可以改寫成
```cpp
void f(string s,llt num,llt pos)
{
stack<char> Stack;
for(llt i=0;i<s.size();i++)
{
while(num>1 && !Stack.empty() && Stack.top()>s[i])
{
Stack.pop();
num--;
}
Stack.push(s[i]);
}
...
```
4. 建表在面對很多 query 的題目時可以加速
5. 針對那些找最短路徑的題目，有幾個思路
* dijkstra: 每次都挑出距離最短的點，拿來鬆弛 (更新與該點連接的其他點的最短路徑)
* SPFA: 每次都按順序挑出被鬆弛的那些點 (也就是把 dijkstra 的 priority queue 改成 queue)，拿來鬆弛
* Bellman-Ford: 每輪都拿每個點來鬆弛，直到 n-1 輪
* floyd warshall: 使用動態規劃的思路，建出 dp[i][j] 的二維表；k 在最外層
6. permutation 類型的題目，可以逆向存取 "值 -> 輸入順序" 的關係陣列
7. 找不到規律時，可以暴力解出小測資的答案觀察
8. 用 Set 記住欲操作陣列的 Index，再透過 lower_bound 快速搜尋
9. x & (x-1) =0，if x=1, 2, 4, 8, 16, ...
10. a 的所有因數與 b 的所有因數取交集即為 GCD(a, b)
11. 可以用 set 存 Index, unorder_map 存資料以快速搜尋
12.
Sign in with Wallet
Connect another wallet