NCTU PCCA winter

快速索引

一般組

Day 1: 二分搜尋法 (pdf) (上機練習) (題解)
Day 2: 資料結構&STL (slide) (上機練習) (題解)
Day 3: 暴力法 (slide) (上機練習) (題解) (影片)
Day 4: 貪心法 & 分治法 (slide) (上機練習) (題解) (影片)
Day 5: 動態規劃 (slide) (上機練習) (題解) (影片)

進階組

Day 6: 貪心法 (pdf) (上機練習) (題解) (影片)
- 練習套題 [日常的日常 ]
Day 7: 數學工具 (slide) (上機練習) (題解)
Day 8: 自動機與字串們 (slide) (上機練習) (題解)
- 練習套題 [無盡的日常]
Day 9: 高級的 DP (slide) (上機練習) (題解)
Day 10: 高級的圖論 (slide)

二分搜 Day1

整理筆記

演算法 Big O 時間複雜度

二分搜尋快速找東西，全部找過一遍 O=n 單調性輸入：一堆有單調性的資料輸出：符合條件的第一筆或最後一筆作法：每次取中間值，尋找範圍小一半 big O(log n)

int Binary_Search () {
    int L=0, M, R=INF;
    while (R-L >1) {
        M=(L+R)/2;
        if (check(M)) {
            L=M;
        } else {
            R=M;
        }
    }
    return L;
}

競賽會評估時間複雜度，簡單解法比較好輸入輸出 C-style input/output 格式化 scanf fscanf sscanf 格式化輸出 printf fprintf sprintf 非格式化輸出~~gets~~(remove from C++14 fgets 非格式化輸出 puts, fputs 直接輸入輸出 getchar, putchar Formatted i/o

%% 一個%
%c 一個字元或一堆資院
%s 一個沒有空白的字串
%[set] 一個只包含 set 的字元的字串 ，若要寫成不包含 ：%^[set]
Ex %[^0-9] 存一個沒有 0-9 的字串
%[][] 右括弧先
%d %i %u(無符號) %o %x 一個整數
%0d 可以輸出 binary
%a %e(十進位科學記號) %f %lf(倍準) %g 一個符點數
scanf 吃進的東西是 pointer
%-3d 靠左-3 格
%f.1 小數點後一位
ex %010.3f 補 0 補到 10 格

stream-base i/o
std::cin, std::cout
std::getline std::iostream::getline
<iomanip>:std::setw std::setfill std::setprecision

常見題型輸入 t 筆測資，輸出到底幾位輸出直到 eof EOF：檔案結尾 EOF=-1 是一個巨集

二分搜要有單調性

輸入整行字串 fgets(word, 128, stdin); 包含空白 c++

getline(cin, name);

輸入以空白分隔的數列 sscanf string stream (c++)

檔案輸入輸出 freopen fopen

c++ fstream

cplusplus.com

&a 對 a 這個變數取位置

while(t--) {
xxxx
}

scanf return 1 2 -1(EOF) while (~(scanf())) 等同於 while (scanf()!=-1)

EOF ctrl D linux/ ctrl Z windows

using namespace std;
c++ cin cout
cin >> n;
cin >> n >> m;
cout << n
cout << sum << '\n' << flush
cout << sum << endl

~~gets~~ puts fgets(buffer, 128, stdin) getchar putchar stdin stdout stderr c++ string s; getline(cin,s); 會自己分配記憶體 cin.getline() ???好像很類似 scanf ，會跳過 space 換行 getchar windows \r\n linux \n

sscanf(str, "%d", )

c++

#include <iostream>
stringstream ss;
ss << input ;
while (ss>>num) {}
cout << num << endl

Ex stringstream ss(s) while (ss >> a)

c++ auto 型別 ex auto f = fopen("in.txt", "r");

ifstream fin("in.txt") fin.close()

cin cout VS printf scanf cin cout 速度其實差不多，但有時比較慢字串會差不多，時間會有差是差在 endl 因為中間會跑很多層，會累積到一定數量再輸出 c++ 裡，加上 endl 會清掉 cout << n << endl 代表清空，丟到螢幕上

ios_base::sync_with_std(false); 只能用 c 或 c++ cin.tie(NULL); 不要和 endl 同時用加上面兩行可以加快速度

資料結構&stl Day2

slide 上機練習

窮舉法 Day3

slide

遞迴迴圈考慮一個 int x，算 x^n mod m 觀察規律 n&1

inline int f(x) { return x\*x; } inline 會使後面的展開

暴力演算法快速冪(較難) 剪枝

八后問題雙向 BFS

分治法 Day4

快速冪合併排序

分解左子右子
解決數列剩一個元素，甚麼都不用做
合併左右都排序好，甚麼都不用做

DP Day 5

1<n<10^5

ref

https://hackmd.io/X7gz1KqkR-2sFlK9i-Zucw
https://www.facebook.com/groups/363494050740833/permalink/399730377117200/

alanhc-til