Alan Tseng

20180210-NCTU-PCCA-winter-notes

#competitive_programming

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 的字元的字串 ，若要寫成不包含 ：%^[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

快速冪 合併排序

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

最近點對

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

DP Day 5

1<n<10^5

ref
👈Go Back

@alanhc