## 處理四捨五入
一般題目都會特別規範四捨五入的位置與自行定義"新的四捨五入"，這裡使用常見的四捨五入，在小數點後一位
簡單來說就是四捨五入到整數，最後的結果不要出現小數
最基本的方式就是將結果先 $\times 10$ 假設結果是 $43.1$，那在計算的過程中先 $\times 10$
之後只要做 `if (n % 10 < 5)` 就可以當作四捨五入，不過記得判斷完要 $\div 10$
## 大數處理 (Python 也可以用)
在面對某些題目時會遇到位數非常大的數字，比如 $1000$ 位就遠超 long long 能儲存的範圍
這時候我們就需要使用大數處理的技巧，大數處理通常會依照以下的順序
1. 用 string 輸入數字
2. 將 string 每一個字元一一儲存進 array
```cpp=
string s ;
cin >> s ;
int n = s.size() ;
for (int i=0;i<n;i++)
A[i] = s[n-i-1] - '0' ; // 順序要顛倒
```
之所以順序要顛倒是因為如果遇到加減乘除運算，可能會讓數字位數變大
所以讓位數越大的放越右邊有助於空間利用
不過在大部分情況，只要確定數字在 long long 內，直接用 long long 取代 int
除非在一些考慮速度的競賽，因為 long long 相較 int 會更慢一點
## 二維矩陣的邊界
對於部分題目，二維矩陣的邊界判斷不可避免的，一般會用以下方式執行
```cpp=
// 假設 (x,y) 為當前位置，0 <= x <= n-1, 0 <= y <= m-1
if (x >= 0 && x < n && y >= 0 && y < m) {
// 程式片段
}
```
不過其實也可以用"不存在的元素"當作邊界，比如常見的有 $-1$
不過要記得開多一點空間，實際的作法會像是這樣
```cpp=
// 注意從 1~n, 1~m
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
cin >> A[i][j] ;
}
}
for (int j=0;j<=m+1;j++) { // 上下作邊界
A[0][j] = A[n+1][j] = -1 ;
}
for (int i=0;i<=n+1;i++) { // 左右作邊界
A[i][0] = A[i][m+1] = -1 ;
}
```
不過這個要不要使用就因人而異，也有人認為前面的作法就很好用了
## 簡易方向表達
一般在考慮上下左右的時候，都會需要用 $(x\pm1, y)$ 或 $(x,y\pm1)$
如果一個方向需要寫一段程式碼，那四個方向就需要做四次，這時可以用 for+array 取代
```cpp=
int mm[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} ;
for (int i=0;i<4;i++) {
int nx = x + mm[i][0], ny = y + mm[i][1] ; // 上下左右的座標
// 程式碼片段
}
```
通常會在有二維陣列的題目裡使用，不過方向還有另一種可能，就是順/逆時針移動
這時候如果用 $0$ 表示上、$1$ 表示右、$2$ 表示下、$3$ 表示左
```cpp=
int to = 0 ;
for (int i=0;i<n;i++) {
// 程式碼片段
to = (to+1) % 4 ;
}
```
只要重複取餘 $4$ 就可以讓左 $\rightarrow$ 上順利轉向
## 簡易演算法函式庫
C++ 當中有提供一些滿不錯的函式庫，由於我們都用 `#include<bits/stdc++.h>`
所以不需要特別去記下方的函式從哪些函式庫出來的，只要記住用法即可
第一個就是最大值或最小值，通常會用 `max(), min()`，不過這只能一次判斷兩個值
如果我們想一次判斷多個值或一個陣列等等，那就要用到這些方法
```cpp=
// 一次判斷多個值
min({a,b,c,d,...}) ;
max({a,b,c,d,...}) ;
// 一次判斷陣列 a 的所有元素
int min_v = *min_element(a, a+n) ;
int max_v = *max_element(a, a+n) ;
// 最大值的"位置"
int min_p = min_element(a, a+n) ;
int max_p = max_element(a, a+n) ;
```
比較特殊的就是找第 $k$ 大的值，如果用排序的那就是 $a[k-1]$
但如果沒有排序的話，那用 `nth_element()` 通常會快很多
```cpp=
int kth_v = *nth_element(a, a+n) ;
int kth_p = nth_element(a, a+n) ;
```
---
第二個就是排序 `sort()` 跟交換 `swap()`
`sort()` 可以處理陣列或 vector 非常方便
```cpp=
int a[101] ;
vector<int> b(101) ;
// 程式碼片段
sort(a, a+n, cmp) ; // cmp 是比較函數，預設是由小到大
sort(b.begin(), b.end(), cmp)
```
```cpp=
int a = 3, b = 5 ;
swap(a, b) ;
// a == 5, b == 3
```
---
第三個 `unique()` 是在做資料離散(相同的資料去除留下剩一個)的時候很方便
一般我們的操作會像是下面這樣
```cpp=
sort(a, a+n) ;
vector<int> v = {a[0]} ;
for (int i=1;i<n;i++)
if (a[i] != a[i-1])
v.push_back(a[i]) ;
```
排序過後，同樣的值會被排在一起，所以相鄰不相同的值就是新的值，自然要加到 v 當中
那 `unique()` 就是直接幫你省去了這個過程，並且還能不用開新的容器
```cpp=
sort(v.being(), v.end()) ;
int pos = unique(v.begin(), v.end()) ;
// 假設 1 1 2 2 2 4 5
// unique 後會變成 1 2 4 5 x ...
// pos 就是 x 位置的 iterator
// x 的值不重要，因為前面的數字已經去除重複了
```
當然用 set 也可以做到同樣的事情，這個就看用途去做選擇
`unique()` 本身的功能是將相鄰的同值元素消到只剩一個，不過通常用在排序後
所以我們就不去探討其他的用途了，萬一會用到也可以用最初的做法去做
---
第四個是 `accumulate()` 和 `iota()`，這兩個的基礎使用場景比較少，自己做也不難
`accumulate()` 可以計算 $a[i]\sim a[j]$ 的總和
```cpp=
cout << accumulate(a+i, a+j) << '\n' ;
```
不過這個可以自己手搓一個出來，並不難，如果多次查詢還是用前綴和會比較快
`iota()` 的用處就是在 $a[x] \sim a[y]$ 的部分放從 $z$ 開始一次加一的值
```cpp=
// 自己手搓
for (int i=x;i<=y;i++)
a[i] = z+(i-x) ;
// 用 iota()
iota(a+x, a+y+1, z) ;
```
這個自己手搓也不難，大部分會用到都是用下面這種方式，自己寫就好
```cpp=
for (int i=0;i<n;i++)
a[i] = i ;
```
## Reference 參考
在競技程式中，Reference 通常拿來簡化許多問題，算是在 C++ 特有的語法糖
首先的功能就是用地址去實現類似 global 變數的情況
一般在不同 function 中，local 變數不可以在另一個 function 被改變
比如如果要交換兩個變數，我們如果這樣寫
```cpp=
void swap(int a, int b) {
int tmp = a ;
a = b ;
b = t ;
}
swap(x, y) ;
```
這樣交換的是 swap 內部的 local 變數 $a,b$，而不是 $x,y$，應該這樣寫
```cpp=
void swap(int &a, int &b) {
int tmp = a ;
a = b ;
b = t ;
}
swap(x, y) ;
```
因為這樣 $x,y$ 的地址也會被傳入 swap，更改的時候會一起更改
不過要注意，因為"地址"也要被傳入，所以這裡的 swap 只能傳整數變數，整數是不行的
---
第二個功能也是在 function，傳入 vector 等資料結構的時候很好用
```cpp=
void sort_and_print(vector<int> &v, int n) {
sort(v.begin(), v.end()) ;
for (int i=0;i<n;i++)
cout << v[i] << ' ' ;
cout << '\n' ;
}
```
如果沒加入 & 的話，傳入 function 一次就需要複製一次 vector
如果像是 DFS 這種需要一邊更改陣列內容，一邊遞迴的情況，多次複製會大幅度降低效率
這種方式只要注意，function 內部跟外部是同時改變的(用指標也可以做到同樣的事情)
---
最後一種功能就是用參考精簡變數，通常用在需要 array、map、string 等多層堆疊的變數
```cpp=
for (int i=0;i<n;i++) {
find_root(s[a[idx[i]]]) ;
if (check(s[a[idx[i]]]))
s[a[idx[i]]] += cul(s[a[idx[i]]]) ;
else if (s[a[idx[i]]]-'a' < 26 && s[a[idx[i]]]-'a' >= 0)
s[a[idx[i]]] = 'a' ;
else
s[a[idx[i]]] = 'A' ;
}
```
這段程式碼用到很多 `s[a[idx[i]]]`，雖然在實作中可以用複製貼上
但是如果這之間的順序錯了，比如 `s[a[idx[i]]]` 應該是`s[idx[a[i]]]`
這時候就需要一次改變所有同樣位置，如果這時候可以用一個簡單的變數取代，改起來就很輕鬆
```cpp=
for (int i=0;i<n;i++) {
int &tmp = s[a[idx[i]]] ;
find_root(tmp) ;
if (check(tmp))
tmp += cul(tmp) ;
else if (tmp-'a' < 26 && tmp-'a' >= 0)
tmp = 'a' ;
else
tmp = 'A' ;
}
```
當然這裡要注意幾個問題，大致上就是要記得別用下面幾種寫法
```cpp=
int &tmp ; // 沒指定 -> 無法做參考
int &tmp = 100 ; // 無法做純整數的參考
int &tmp = a+b ; // 兩整數變數相加後是純整數，無法做參考
```
## 變數的初始化與特性
通常變數的初始化都是我們額外去指定的，但大致上有幾個特性可以幫助我們解題
首先就是整數全域變數會被初始化為 $0$，因為這個特性所以通常在以下情況會用到
比如在定義一個一維矩陣或二維矩陣時，如果要多寫一個 for 初始化有點麻煩
```cpp=
int G[101][101] ; // 預設初始化為 0
int main() {
// 程式碼片段
return 0 ;
}
```
在只需要一次初始化的時候滿好用的，但是如果要多次初始化就要用其他方式了
至於如果需要一個 local 的區域變數初始化，就直接用原本的方式即可 `int G[101][101] = {} ;`
還有一個有關 global 的特性，就是拿來存放超大的陣列
---
第二個就是 struct 的使用，通常在需要一次存兩個以上變數時會用到
比如圖論常會用到 (點, 權重) 之類的做法，這時候用 struct 就會滿方便的
不過 struct 初始化有一個特性，就是 struct 內部初始化後，使用時都會自動初始化
```cpp=
struct node {
int n = 7, w = 1 ;
} ;
node global_node ;
int main() {
node local_node ;
cout << global_node.n << ' ' << global_node.w << '\n' ; // 7 1
cout << local_node.n << ' ' << local_node.w << '\n' ; // 7 1
return 0 ;
}
```
---
第三個就是 auto 的使用，auto 的特性讓我們在一些情況很方便
比如最簡單的就是在處理一些 STL 的資料結構時，for 迴圈跑過需要用到 iterator
```cpp=
map<int, int> mp ;
for (auto it=mp.begin();it!=mp.end();it++) {
// 程式碼片段
}
```
還有在一些情況，需要用到以下作法，解釋起來太麻煩，只要在實作上能用就可以了
```cpp=
auto cmp[](int a, int b) {
return a < b ;
} ;
```
---
第四個是 static，這是一種拿來更好地區隔 global 和 local 的方式
如果多次執行同一個函式，並且輸出是第幾次執行這個函式
這時候你可以傳入與回傳紀錄次數，或是用一個 globla var 紀錄次數
```cpp=
// 傳入與回傳紀錄次數
int f(int times) {
// 程式碼片段
return times+1
}
int global_t = 0 ;
void g() {
// 程式碼片段
global_t++ ;
}
int main() {
int times = 0 ;
times = f(times) ;
// times = times+1
g() ;
cout << '\n' << times << ' ' << global_t << '\n' ;
return 0 ;
}
```
這兩種的缺點也很明顯，第一個方法的問題是如果函式需要回傳其他值，就會很麻煩
第二個方法就是因為 global var 有可能會不小心被其他地方改掉
這時候如果用 static local var 就可以有一個不會被重製的 local var
```cpp=
void f() {
static int times = 0 ;
times++ ;
}
void g() {
static int times = 0 ;
times-- ;
}
int main() {
f(); // times in f: 1
f(); // times in f: 2
g(); // times in g: -1, times in f: 2
f(); // times in g: -1, times in g: 3
g(); // times in g: -2, times in g: 3
return 0 ;
}
```
這兩個函式內的 times 都是 local，兩個變數互不干涉
static 還有一個很方便的功能，就是讓 local var 初始化
比如我需要一個在 function 內寫全 $0$ 的陣列
通常需要一個 for-loop，但用 static array 就可以省下麻煩
不過還是要記得上面說的 static 的功能，不然可能會誤用
---
最後就是 const，主要的功能就是讓變數不能修改，然後執行速度變快
會用在只能來讀取但不修改的變數，比如大量取某數的餘數或四個方向移動陣列
```cpp=
const int MOD = 10000000007 ;
const int mm[4][2] = {{1,0},{-1,0},{0,1},{0,-1}} ;
```
還可以用在函式傳遞某些變數，只要不修改就可以使用
```cpp=
void f(const vector<int> &a) {
// 程式碼片段
}
```
還有一個額外的好處，就是 reference 可以傳入非變數，比如上方可以用 `f({1,2,3})`
### 用數字表示選擇
一般來說，我們在表示某個有規律的資料中，元素是否被選擇的時候，會用 bool 陣列去做
但是如果我們也可以用另外一個方式表示，使用數字去儲存是否選這個元素，或是否存在該元素
這樣的好處就是在處理 $n$ 個由資料內元素組成的集合時，我們不需要用 $n$ 個 bool 陣列
只需要 $n$ 個數字就可以處理，至於實作的方式，是考慮到數字本身由位元組成
二進制的數字剛好和 bool 陣列的概念類似，都是一串 $0$ 和 $1$
```cpp=
#include<bits/stdc++.h>
using namespace std ;
int main() {
int A[10] = {9,8,7,6,5,4,3,2,1,0} ;
int pick_odd = 0, pick_even = 0 ; // 根據 index 選
for (int i=0;i<10;i++) {
if (i % 2) // 奇數
pick_odd += 1 ;
else // 偶數
pick_even += 1 ;
// 進到下一個選擇
pick_odd <<= 1 ;
pick_even <<= 1 ;
}
int len = 10 ;
for (int i=len-1;i>=0;i--) {
pick_odd >>= 1 ;
if (pick_odd % 2) // 輸出選擇的數字
cout << A[i] << ' ' ;
}
cout << '\n' ;
for (int i=len-1;i>=0;i--) {
pick_even >>= 1 ;
if (pick_even % 2) // 輸出選擇的數字
cout << A[i] << ' ' ;
}
cout << '\n' ;
return 0 ;
}
```
Sign in with Wallet
Connect another wallet