# 競賽用小技巧

## 複雜度

複雜度的記法稱為O-notation。大多數情況都用大O表示法作為分析標準即可。大O表示法會著重於n趨近時無窮大時函數的增長狀況。
一般演算法分析為使其簡單易懂，有三個步驟省略紀錄，分別為：

1. 用緊實的上限(tight bound)，簡單來說就是用盡可能小的複雜度
2. 忽略常數
3. 忽略成長較慢的項

以f(n)=4n^3^+n^2^+3為例，可將其表示為O(n^3)。

複雜度分為時間與空間，一般來說空間是較為寬裕的，而時間限制較為緊湊。
在多數狀況下時間限制多為1秒，以下是在這樣的時間限制下可以完成的資料規模參考。越後面是越不常見的。

| O(1) |O(log⁡(n))|O(n)|O(nlog⁡(n))|O(n^2^)|O(n^3^)|O(2^n^)|
|------|---------|----|----------|------|------|------|
|2^63^-1| 2^63^-1 |10^6^| 10^5^ | 10^3^ | 500 | 20 |

|O(n!)|O(n^4^)|O(n^5^)|O(n^2^ log⁡(n))|O((nlog(n))^2^)|O(3^n^)|O(4^n^)|
|-----|------|------|-------------|--------------|--|-|
| 10 | 30 | 15 | 500 | 300 | 12|10|

後續再介紹演算法時將會有更進一步的介紹。

## io加速

由於`scanf/printf`並不是特別好用，而且經過加速後的`cin/cout`會比較快(在輸入測資較大時)。於是附上cin/cout的加速方法。

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    //code here
}

 
## 萬用標頭檔

你是否有為引入標頭檔而感到困擾呢？下方是一個較為極端的例子。

#include<iostream>
#include<fstream>
#include<conio.h>
#include<sstream>

#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<map>

#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<ctime>

但其實這些都可以用以下一行取代，對於考試而言可以說方便許多。

#include<bits/stdc++.h>

## 巨集和程式碼簡化技巧

我個人其實並沒有大量地使用巨集，因此我先列出一些較常用的以供參考。

using namespace std;

#define F first
#define S second
#define lowbit(x) (x&-x)
#define ALL(x) x.begin(),x.end()

using ll=long long;
const ll INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;

template<typename T> using prior=priority_queue<T>;
template<typename T> using prior=priority_queue<T>;

## 預建構函數

有時候會出現的~~常用~~函數，

void amax(ll &a,ll b){ if(a<b) a=b;}
void amin(ll &a,ll b){ if(a>b) a=b;}

void pmod(ll &a,ll b){ a=(a+b)%MOD;}
void mmod(ll &a,ll b){ a=(a-b)%MOD;}
void tmod(ll &a,ll b){ a=(a*b)%MOD;}

ll POW(ll x,ll a){
    ll ret=1;
    while(a>0){
        if(a&1) tmod(ret,x);
        tmod(x,x);
        a>>=1;
    }
    return ret;
}

## 重載運算子

用在set/map/priority_queue。

struct info{
    int a,b;
};
//以下自由發揮
bool operator<(info x,info y){
    if(x.a!=y.a) return x.a<y.a;
    return x.b<y.b;
}

priority_queue<info> pq;