NCTU PCCA winter

快速索引

一般組


進階組


二分搜 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的字元的字串 ,若要寫成不包含 :%[1]
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

快速冪
合併排序

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

最近點對

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

DP Day 5

1<n<10^5

Select a repo