0.2.1 基本C++模板與輸入輸出

1
2
3
4
5
6
7
8
#include <bits/stdc++.h> // 萬用標頭檔
using namespace std;
int main(){
    ios::sync_with_stdio(0);    // 優化cin的東西
    cin.tie(0);
    // code here
    return 0;
}

有優化cin的那兩行就不能再把cin/cout與scanf/printf混用，不然會發生無法預測的錯誤

使用scanf/printf
使用cin/cout並優化

0.2.2 程式測試與測試資料

stdin: 標準輸入裝置，預設鍵盤
stdout: 標準輸出裝置，預設螢幕
stderr: 標準錯誤紀錄裝置，預設螢幕

unix環境下的IO重導:

1
./a.out <test.in >test.out

程式裡面I/O重導:

1
2
freopen("test.in","r",stdin);
freopen("test.out","w",stdout);

unix環境下計時:

1
time a.out <test.in

程式裡面計時:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
#include <bits/stdc++.h>
using namespace std;

int main(){
    clock_t start,end;
    start=clock();
    // code here
    end=clock();
    fprint(stderr,"time from start to end = %f sec.\n",(float)(end-start)/CLOCKS_PER_SEC);
    return 0;
}

0.2.3 複雜度估算

複雜度估算方式

時間複雜度通常以$O(f(n))$來表示，念作big-O，以n來表示資料量，常數倍通常忽略不計常見的有:$O(n)$、$O(nlog(n))$、$(n^2)$

由資料量大小推估所需複雜度

題目會說明資料量的大小跟時間限制(time limit)，可以用這兩點去推估時間複雜度可以一秒$10^6$~$10^7$的指令數量來估計

n	超過1萬	數千	數百	20~25	10
複雜度	$O(n)$ or $O(nlog(n))$	$O(n^2)$	$O(n^3)$	$O(2^n)$	$O(n!)$

複雜度需要留意的幾件事

sort/qsort可以視為$O(nlog(n))$
Big-O通常指的是上限，而未必是緊實的上限(tight bound)
$O(n^x)$ 在x是常數時成立

0.教材說明與預備知識