### 競賽程式導論
程式競賽中時間寶貴，執行時間越短越好。所以要減少所花費的時間，以及估算程式的執行時間

----

### 競賽程式先備知識
* 時間複雜度
* 前綴和&差分
* $overflow-rounding$ $error$
* $I/O$優化

---

## 複雜度估算
為了評估程式的執行效率，我們可以測量時間

----

複雜度通常以$O(f(n))$表示 O通常被稱為大O符號，$n$是資料量，而$f(n)$是$n$的函數

----

* 時間複雜度

| Big O Notation | 別名 | 常見演算法 |
| -------- | -------- | -------- |
| $O(1)$ | 常數 | 陣列讀取 |
| $O(n)$ | 線性 | [Linear search](https://en.wikipedia.org/wiki/Linear_search)|
| $O(logn)$ | 對數(Logarithmic ) | [二分搜尋法](https://en.wikipedia.org/wiki/Binary_search_algorithm)|
| $O(nlogn)$ | 線性 | [堆積排序](https://hackmd.io/@SupportCoding/Heap_sort)，[合併排序](/Merge_sort) |

----

| Big O Notation | 別名 | 常見演算法 |
| -------- | -------- | -------- |
| $O(n^2)$ | 平方 | [氣泡排序](https://en.wikipedia.org/wiki/Bubble_sort)，[插入排序](https://en.wikipedia.org/wiki/Insertion_sort)|
| $O(n^3)$ | 三次方 | 三重迴圈枚舉法，高斯消去法求解線性方程組 |
| $O(2^n)$ | 指數 | 費氏數列 |
| $O(n!)$ | 階層 | 排列組合，八皇后問題 |

----


----

根據上圖
我們要盡可能避免使用$n^2, n^3, 2^n$ 這三個
增長速度飛快的方法來執行

----

通常一秒能執行的量大概是$O(10^9)$
因此我們可以得到下表

----

| $n$大小 | 通常使用甚麼方法 |
| -------- | -------- |
| $n>10000$ | $O(n)$ or $O(nlog(n))$|
| $n>1000$ | $O(n^2)$ |
| $n>100$ | $O(n^3)$ |
| $20<=n<=26$ | $O(2^n)$ |
| $n=<10$ | $O(n!)$ |

---

## 前綴和$prefix-sum$
$ps[i]$=$\sum_{n=0}^{i} val[n]$
$ps[x]-ps[y]$=$\sum_{n=y+1}^{x} val[n]$

//一般的前綴和陣列的建立
int val[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
//前墜和(ps)陣列可以方便找區間和
int ps[10] = {0};
ps[0] = val[0];   //預處理第一項
for(int i = 1;i < 10;i++) { 
    ps[i]=ps[i-1]+val[i];  
}
//前綴和陣列的第n項=前綴和陣列的前項+原陣列的第n項

----

### 差分
$d[i]=val[i]-val[i-1] ; d[1]=val[1]$

int val[3] = {3, 3, 4};
int ps[3] = {3, 6, 10}; //前綴和陣列
//對ps進行差分 
int d[3]= {3, ps[1]-ps[0], ps[2]-ps[1]}  //變成原陣列

----

可得

----

### 前綴和與插分的進階技巧
EX：給定一陣列$A_{1},A_{2}...A_{n}$
進行$i$次, 每次給$l, r, x$
代表$from$ $A_{l}$ $to$ $A_{r}, all+=x$
求最後的陣列
若正常做所需時間=$O((l-r)*x)$ 容易TLE

----

因此我們可以對差分陣列進行改變

int val[5] = {3, 4, 5, 6, 7};
int d[5] = {3, 1, 1, 1, 1};

若要改變的區間是$val[1]～val[3], +=3$
我們可以改成將$d[1]+3, d[3+1]-3$

d[5] = {3, 4, 1, 1, -2} //進行前綴和
val={3, 3+4, 3+4+1, 3+4+1+1, 3+4+1+1-2}

這樣可以把$O(n)$變成$O(1)$

---

#### $overflow$

$overflow$是C++數字的存儲上限

| $int$ | $long-long$ |
| -------- | -------- |
| $2^{32}-1$約$10^9$ | $2^{64}-1$ 約$10^{18}$ |

如果使用該資料類型卻超過,會產生亂數

----

#### $rounding-error$
C++中浮點數可能會產生存儲誤差
例如0.3在二進制就是無限小數,導致無法存儲
出現誤差

---

## $I/O$優化
C++中如果使用`cin和cout`,時間常數比較大
即花費較多時間
可以改用`scanf和printf`或進行$I/O$優化,減少時間

//加上這行即可I/o優化
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

---

# 結束!!!