# NCTU PCCA winter

## 快速索引

- [活動網頁] | [水題大賽] | [課程網頁]
- [演算法筆記]

[課程網頁]:https://sites.google.com/g2.nctu.edu.tw/pcca-winter-2018/%E8%AA%B2%E7%A8%8B%E8%B3%87%E8%A8%8A?authuser=0
[水題大賽]:https://vjudge.net/contest/204504
[活動網頁]:https://sites.google.com/g2.nctu.edu.tw/pcca-winter-2018/%E9%A6%96%E9%A0%81?authuser=0
[演算法筆記]:http://www.csie.ntnu.edu.tw/~u91029/index.html

### 一般組
- Day 1: 二分搜尋法 ([pdf](https://drive.google.com/file/d/12n-7wQRKTvFtCwddk9UVrgCieCYyOlwr/view?usp=sharing)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F210524&sa=D&sntz=1&usg=AFQjCNEEMkvxGitZbfdAk_9QXjFiwSxxgQ)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fs%2FrknuUZkLz%23&sa=D&sntz=1&usg=AFQjCNEPTGwIPntZ-uN-fEYm6OZaRlju7g))
- Day 2: 資料結構&STL ([slide](http://www.google.com/url?q=http%3A%2F%2Fslides.com%2Fderor1869107%2Fdeck-4%23%2F&sa=D&sntz=1&usg=AFQjCNGzB4v6IF6vGn8dfUV5fhlG0WhysQ)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F210601&sa=D&sntz=1&usg=AFQjCNE8u4HXr9kMqD8wYfZ9vhgu7IRm0g)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FCzCmFYGYDYBNQLQHYmgJwOAQ2lhAONWABk0mHFmGIEZIaksg&sa=D&sntz=1&usg=AFQjCNEbSnUPMmxj6iZzdXqKSG-nsCDhbw))
- Day 3: 暴力法 ([slide](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fp%2FryGTJ8nrM%23%2F&sa=D&sntz=1&usg=AFQjCNGH7PXHP8TjC0eFRMMxV0q7F9gF7Q)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F210927&sa=D&sntz=1&usg=AFQjCNFPcimaKWfU3EYDOweIv05m6mT8ug)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FMwBgHARpCmCMC0AWAxgM0UgrAJgIbwkRGHgBNoxZZdYB2ZaUxIA%3D%3Fview&sa=D&sntz=1&usg=AFQjCNGG1qArKi1-im7recUWCkrO-8GkRg)) (影片)
- Day 4: 貪心法 & 分治法 ([slide](https://docs.google.com/presentation/d/1D-HH4ijGoFix-BREc8xcR-1nFesMEgMyFdIVdnFf6tY/edit?usp=sharing)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F211059&sa=D&sntz=1&usg=AFQjCNHnpObaP6iVBFoa-tvg6wVdDfu1Cw)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fs%2FSy3m-9jBz&sa=D&sntz=1&usg=AFQjCNGoGvLhYkgp7OcYsQu5deBN3F8C5A)) (影片)
- Day 5: 動態規劃 ([slide](https://docs.google.com/presentation/d/1lD8JDTCXKS-lh0gPTqcYJ-xHZJo6R982DfkXBO8cicc/edit)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F211396&sa=D&sntz=1&usg=AFQjCNGnC--Bm8_sAHmOJ1V3jFdIEWb2Ow)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FOwJgnAzAhgjArAEwLQA4pQAxICwDM4xIBGEKApktGHFESnGMDAkA%23&sa=D&sntz=1&usg=AFQjCNGcX0UWBdB-NBGeyX40kiDFg8yJeQ)) (影片)
---
### 進階組
- Day 6: 貪心法 ([pdf](https://drive.google.com/file/d/1YjhMW4tI5aq3e0hK4z4Vk4Z4e2yEOWzi/view?usp=sharing)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F211436&sa=D&sntz=1&usg=AFQjCNG8Lp9bp9OEswVnvQTdFp3Jd3RKew)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fs%2FBJSg9cHUM&sa=D&sntz=1&usg=AFQjCNFr4XW2UTb-djQVf9_EIZNTSRpaSg)) (影片)
- [練習套題 \[日常的日常 \]](https://www.google.com/url?q=https%3A%2F%2Fl.facebook.com%2Fl.php%3Fu%3Dhttp%253A%252F%252Fcodeforces.com%252FgymRegistration%252F101666%252Fvirtual%252Ftrue%26h%3DATNwQtim_J1fr0ODvwu_5fMdeuqw-UeL5iL0_kwjcJDyNVsPur1Nh1BE6wNEQvXdY2dapazEoTENQ3-x6YGnmWuhkC6KElJlkcZb68h5rLuvlasNb6Nl2oqwK5NKA32Tl4UxZj3fYpLFWrB6vNdw1SAdZigQVglmLojGDVhFde0_Wt8_osf0WnMhT4f90udA9xD31YXQr7xFwgZYxrZ-4shpdSWnV-rQXc3YKs8aCbFE8aBbj32Bmw&sa=D&sntz=1&usg=AFQjCNF6keuZpChStesCP41QVJOWbMK1Dg)
- Day 7: 數學工具 ([slide](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fp%2FS1zxxteIG%23%2F&sa=D&sntz=1&usg=AFQjCNELO9MidubbWg_c3bnjTaufDnmerA)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F211705%23overview&sa=D&sntz=1&usg=AFQjCNEWBjT4IWXHKbHxgEvMA07XAgrt4Q)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FMYIwnCDskGwCwFoYBMCGAOBcZmAsAjMogGYAMwqBqqJcApiAUA%3D%3D%23&sa=D&sntz=1&usg=AFQjCNErX5XBGxzHUNa_KU49psP8Z37Yxg))
- Day 8: 自動機與字串們 ([slide](https://docs.google.com/presentation/d/1gOoIElQz9NhlvRNzjGSxJTdclNj5Po5xSkRzNn5ndvo/edit#slide=id.p)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F211940&sa=D&sntz=1&usg=AFQjCNF3GGKm9qAK5Y9mamxK7tY9PuE1eg)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FEYdgbMAmAcDGAMBaaAzAhgRkQFmPJw2GATIpCNAKzCVjayEDMQA%3D&sa=D&sntz=1&usg=AFQjCNFhoudHMuGg4CHJZtRomaCy8v43KA))
- [練習套題 \[無盡的日常\]](https://www.google.com/url?q=https%3A%2F%2Fl.facebook.com%2Fl.php%3Fu%3Dhttp%253A%252F%252Fcodeforces.com%252FgymRegistration%252F101620%252Fvirtual%252Ftrue%26h%3DATMUW16U1SbtK6CLFYVo40X3NiwaVRCyVgze43TC2ENKKKO5W2pD-f77XVVgxdC9GV15wLCbSlBVSiXD_YuG8UZDQO7NRGyHVVE6HiLWdE-L33bHX9YpypfArwq3bTNUGI35bz0F9EypshxZKQZOnvbf_MkvLjEMe9ue_3LnbmduAf1EPpoKQMXuY22rNiOkF1rdwftD2JIte0q0CmmdjPV6B6iEarRs7k6qmK4&sa=D&sntz=1&usg=AFQjCNFykK4SbQU8jeXTwJrznZGG-Sh40A)
- Day 9: 高級的DP ([slide](http://www.google.com/url?q=http%3A%2F%2Fslides.com%2Fhank55663%2Fdeck%23%2F&sa=D&sntz=1&usg=AFQjCNEK4dFoIES4A5NgCuMKXHWpgR_Hcg)) ([上機練習](https://www.google.com/url?q=https%3A%2F%2Fvjudge.net%2Fcontest%2F212091&sa=D&sntz=1&usg=AFQjCNEYKwIYNA5MS0TMFgfk7b_3W0O7og)) ([題解](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2FMYRgTAJgZgLAHHAtAQwKwAYaJhZBTROAdnREQhgCMA2ATjwfWWTiA%3D%3D%3D%3Fview&sa=D&sntz=1&usg=AFQjCNEnvDvbsQtpL1h8O3xI1HED7Tk-JQ))
- Day 10: 高級的圖論 ([slide](https://goo.gl/idbPuV))
---

## 二分搜 Day1
- [PDF]
- [上機練習]
- [題解]

### 整理筆記

演算法
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同時用
加上面兩行可以加快速度

[PDF]:https://drive.google.com/file/d/12n-7wQRKTvFtCwddk9UVrgCieCYyOlwr/view
[上機練習]:https://vjudge.net/contest/210524
[題解]:https://hackmd.io/s/rknuUZkLz#

## 資料結構&stl Day2
[slide] [上機練習]

[slide]:http://slides.com/deror1869107/deck-4#/
[上機練習]:https://vjudge.net/contest/210601

## 窮舉法Day3
[slide](https://www.google.com/url?q=https%3A%2F%2Fhackmd.io%2Fp%2FryGTJ8nrM%23%2F&sa=D&sntz=1&usg=AFQjCNGH7PXHP8TjC0eFRMMxV0q7F9gF7Q)

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

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

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

八后問題
雙向BFS

## 分智法Day4

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

最近點對
- 分解 分成n/2的左右半邊
- 解決 答案是只剩兩點的距離
- 合併 答案有三種，左半、右半、跨邊點對 把三種可能的答案取min
題目
- 10245
- 10750
- 11378
- Codeforce 429D

## DP Day 5
1<n<10^5