changed 5 years ago  
Linked with GitHub

競賽基本知識

Wiwi Ho

tags: CRC

https://hackmd.io/@wiwiho/crc1082algo

複雜度分析

什麼是複雜度？

有一個函數 \(f(n)\)
它的值跟 \(n\) 有什麼關係？

\(f(n)=n^2+2n-1\)

\(n^2\) 對 \(f(n)\) 的值影響最大
\(\Rightarrow\) \(f(n) \in O(n^2)\)

Big-O notation

對於兩個函數 \(f(n)\) 和 \(g(n)\)
若存在正數 \(c\) 和 \(n_0\)
滿足所有的 \(n \geq n_0\) 都符合 \(f(n) \leq cg(n)\)
則 \(f(n) \in O(g(n))\)

複雜度怎麼求

只留最高次項
且把係數拿掉

比大小

複雜度越大
表示函數值成長越快

怎麼比（嚴謹定義）

\(\lim_{n \to \infty} \frac{g(x)}{f(x)}\)

  • 無限大：\(O(g(n))>O(f(n))\)
  • \(0\)：\(O(g(n))<O(f(n))\)
  • 非零常數：\(O(g(n))=O(f(n))\)

如果 \(O(g(n))>O(f(n))\)
\(O(f(n)) \in O(g(n))\)

\(\Rightarrow 2n^2+n-1 \in O(2n^2+n-1) \in O(n^2) \in O(n^3)\)

複雜度非唯一
通常會選最小而且寫出來最簡單的

用詞

常數：\(O(1)\)

線性：\(O(n)\)

其他應該很好懂 (?
e.g. 對數（\(O(\log n)\)）、根號（\(\sqrt{n}\)）……

STL 的複雜度

查表
cppreference.com

時間複雜度

表示程式的執行時間如何隨輸入的數值成長
\(\Rightarrow\) 用來比較演算法好壞的方法

會用多少時間？

不能準確計算

把所有參數的最大值代入後
約 \(10^8\) 到 \(10^9\) 為一秒

範例

int n;
cin >> n;
vector<int> v(n);
for(int i = 0; i < n; i++) cin >> v[i];
for(int i = 0; i < n - 1; i++){ //迴圈 1
    for(int j = 0; j < n - i - 1; j++){ //迴圈 2
        if(v[j] > v[j + 1]) swap(v[j], v[j + 1]);
    }
}
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << "\n";

int n;
cin >> n;

stack<int> st;
for(int i = 0; i < n; i++){
    int t;
    cin >> t;
    while(!st.empty() && st.top() <= t) st.pop();
    if(st.empty()) cout << "-1 ";
    else cout << st.top() << " ", st.pop();
    st.push(t);
}
cout << "\n";

常數

被丟掉的常數

常數重要嗎？

當然重要！

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        for(int k = 0; k < 10; k++) /*...*/;
    }
}

時間複雜度 \(O(n^2)\)
如果 \(n \leq 10000\)
\(n^2=10^8\)

好像勉強還行？

那個 10 呢？
\(10n^2=10^9\)

可能不太行

如果常數會造成時間剛好超過
那就很重要

看不到的常數

加、減、乘、除、模都是 \(O(1)\)
但除和模需要比較多時間

unordered_set、unordered_map
的插入刪除尋找都是 \(O(1)\)
但常數很大

輸入輸出

各種流

輸入流、輸出流？

什麼是流？

輸出流：把東西給它，它會負責輸出到某地方
輸入流：跟它要一個東西，它會負責從某個地方拿給你

標準流

  • 標準輸入流 - cin
  • 標準輸出流 - cout
  • 標準錯誤流 - cerr

預設：在 terminal 輸入輸出
可以重新導向成在檔案輸入輸出

錯誤流

一種輸出流
用來輸出錯誤訊息
不會被 judge 讀到

重新導向

在程式碼

freopen("filename", "w", stdout);
freopen("filename", "w", stderr);
freopen("filename", "r", stdin);

在 terminal

command < in
command > out
command 2> err
command < in > out 2> err
command < in > out

緩衝區

cin

輸入的東西先到緩衝區
程式讀取的時候會從緩衝區拿資料

cout

輸出的東西先到緩衝區
flush 後再真的輸出到它該去的地方

cerr

沒有緩衝區
會馬上輸出到它該去的地方

stringstream

一種 iostream
\(\Rightarrow\) 是輸入流也是輸出流

stringstream ss;
ss << 5;
int t;
ss >> t;
cout << t << "\n";

輸入輸出優化

效率太差？

來看看它為什麼差

輸出到 terminal 或檔案裡的常數很大

cout 自動 flush

  • endl = << '\n' << flush
  • 使用 cin 時會自動 flush cout
  • 使用 cerr 時會自動 flush cout
  • 程式結束時強制 flush
  • 不要用 endl
  • cin.tie(0)
  • cerr.tie(0)
  • 在最後讓程式自己 flush 就好了

歷史因素

要和 scanf/printf 同步

ios_base::sync_with_stdio(false)

運算子重載

ostream& operator<<(ostream& o, pair<int, int> p){
    return o << p.first << " " << p.second;
}

istream& operator>>(istream& i, pair<int, int> p){
    return i >> p.first >> p.second;
}

輸入格式

EOF

EOF = End Of Line

某些題目：
一個檔案有多筆測資
而且不告訴你有幾筆

while(cin >> /*...*/){
    //...
}

terminal 不是 file？

按 ctrl+z 或 ctrl+d 製造 EOF

輸入一整行

string s;
getline(in, s); //in 是輸入流

跟 >> 混用

abc
abcd abcd

string a, b;
cin >> a;
getline(cin, b);

預期：a=abc，b=abcd abcd 實際：a=abc，b=空字串

多 getline 一次

忽略輸入

ZJ c268：
給你一堆數字，找三個數字當三角形邊長

\(O(n \log n)\) 可以嗎？

\(n \leq 10^7\)
太多了吧

\(n \geq 50\) 保證有解
所以超過 50 項就可以不用讀了

可是一個檔案多測資，怎麼辦？

把輸入忽略掉

cin.ignore(1000000000, '\n');

輸出格式

小數位數

cout << fixed << setprecision(10) << ...;

數字寬度

cout << setw(n) << setfill(c) << ...;

前置處理器

什麼是前置處理器？

在編譯之前，會先做前置處理

#include ...
#define ...

都是前置處理器的指令

什麼是前置處理？

根據指令修改程式碼

include

把別的檔案的內容在該處貼上

引號、角括號？

#include <iostream>
#include "test.cpp"

找檔案的地方不同

  • 角括號：找函式庫
  • 引號：找同個目錄

define

macro/ 巨集 / 宏

//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a) / (b) + !!((a) % (b)))

//#define TEST

typedef long long ll;
typedef unsigned long long ull;

using namespace std;
using namespace __gnu_pbds;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}


int main(){
    StarBurstStream

    return 0;
}

#define a b

把所有單字 a 換成 b

也可以用 function

#define f(a) a+4

換行

#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\

一樣嗎？

#define f(a) a + 5

//...

cout << (3 * f(1));

int f(int a){
    return a + 5;
}

//...

cout << (3 * f(1));

條件判斷

#if ...
...
#elif ...
...
#else
...
#endif

符合條件的地方才會留下來

#if defined(a)
#ifdef (a)
#if !defined(a)
#ifndef (a)

判斷 a 有沒有被 define 過

去寫練習題

Select a repo