【C++】競程筆記（基礎題型）

程式碼範例參考：NTUCPC Guide，此筆記僅為個人學習用途。

萬用標頭檔

#include <bits/stdc++.h>

有些OJ不給用要特別注意，能用就用，其他函式庫名稱還是要背一下。還有因為他抓的函式庫比較多的原因，所以執行會變得有點慢，但基本上不影響。

基本輸出輸入優化（提升速度用）

ios::sync_with_stdio(false)（關閉與C同步的關鍵函式）

cin.tie(nullptr)（關閉 flush 機制，若代碼有用到 endl，這條就沒屁用了，要注意）

endl 建議用 \n 跳脫字元取代。

T 筆測資題型

1
2
3
4
5
int t;
cin >> t;
while (t--) {
    // do something
}

while() 迴圈，括號裡面如果是 0（false），就停止迴圈。以 t 遞減至 0，是比較聰明且簡潔的做法。

此題目會要求輸入 T 個測資，並使用迴圈執行 T 次讀取。

EOF 處理

1
2
3
4
int n;
while (cin >> n) {
    // do something
}

while() 括號裡面放 cin >> n。

EOF：End Of File。

輸入至 0

1
2
3
4
int n;
while (cin >> n && (n != 0)) {
    // do something
}

&& 邏輯運算子 AND，加上 (n != 0)，表示輸入至 0 為止結束迴圈。

sstream 函式庫

1
#include <sstream>
  • istringstream：用於從字串中讀取資料。
  • ostringstream：用於將資料寫入字串。
  • stringstream：是 istringstream 和 ostringstream 的組合，可以同時進行讀取和寫入。

Tip：stringstream 較為常用。

語法：

1
2
3
4
5
6
7
8
9
10
#include <sstream>

// 使用 istringstream
std::istringstream iss("some data");

// 使用 ostringstream
std::ostringstream oss;

// 使用 stringstream
std::stringstream ss;

這個函式庫是拿來處理字串流的，能將字串當成輸出輸入流來使用。

重點是能拿字串進行數學上的運算。

不提供變數數量的題目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <sstream>
#include <string>
using namespace std;
 
int main() {
    int n = 0, arr[100] = {};
    {
        string line;
        getline(cin, line);
        stringstream ss(line);
        int x;
        while (ss >> x)
            arr[++n] = x;
    }
}

有些題目不會提供變數數量，要自己寫程式判斷，因此就需要 stringstream 幫忙。

  • cin：遇到空格就結束。如：AB CD，只會讀到 AB，不會讀到空格+CD。
  • getline(cin, string)：string 代表要輸入進去的字串。然後這東西會讀空格（一整行）。

cin >> x >>ws 換行字元問題

假設輸入：

1
2
1
1 2 3 4 5

輸入完 1 後，cin 不會讀掉換行字元，所以要加上 cin >> x >> ws; 去把換行字元讀掉。

ws 的意思是使 cin 不斷讀掉空白字元直至遇到非空白字元為止。

如果沒加上 ws，後續 getline() 就讀不到了，因為 getline() 會讀到換行字元。

非空格字元的輸入

假設輸入：

1
1,2,3,4,5,6,7

Solution：將逗號去除，改成空格。

1
2
3
for (int i = 0; i < int(str.size()); ++i)
    if (str[i] == ',')
        str[i] = ' ';

Reference 進階應用

1
2
3
4
5
6
for (int i = 0; i < n; ++i) {
cal(arr[pl[idx[i]]]);
if (check(arr[pl[idx[i]]]))
    arr[pl[idx[i]]] = change(arr[pl[idx[i]]]);
} // 假設 cal, check, change 是三個已經寫好在別處的函式

參考（Reference）可說是物件的別名，直接宣告一個變數令 int &cur = arr[pl[idx[i]]];，可省去許多麻煩。

1
2
3
4
5
6
for (int i = 0; i < n; ++i) {
    int &cur = arr[pl[idx[i]]];
    cal(cur);
    if (check(cur))
        cur = change(cur);
} // 假設 cal, check, change 是三個已經寫好在別處的函式

負數取模問題

1
(a % b + b) % b

-5 / 3 的餘數在 C++ 運算中，會變為 -2，要解決此問題，以上式子即可解決。

邊界檢查（越界存取問題）

時常會錯在陣列的索引存取問題，一定要注意陣列索引為 0 ~ n-1（假設陣列長度為 n）。

Tip：若題目範圍上限是 N，則陣列範圍可能取 N + 5，或 N + 10。