預備

進競賽之前要先知道的三件事。 · ⏱ 約 30 分鐘

你會學到三件事

1. 溢位：int 裝不下的時候不會報錯，會繞回去
2. 複雜度：從「跑得完嗎」倒推「可以用什麼演算法」
3. 短路：&& 的右邊不一定會算

開始之前

⚠️ 右下角的目標選「C++ 競賽」。

從這裡開始，題目會告訴你「n ≤ 100000」這種話， 而那句話直接決定你可以用什麼做法。

🟢 先把編輯器打開，跟著下面一起做。 讀完再打開的話，下面每一段你都得先記起來，而那不是這個工具要你做的事。

到編輯器打開這一課：跟著做

一、溢位：安靜的錯

試試看這一段，它不會報錯，而答案是錯的：

1int a = 1000000;2cout << a * a << endl;      // 🔴 印出一個負數

int 大約裝到 21 億（2³¹ - 1），一兆放不進去。

而 C++ 不會報錯：它把多出來的位元丟掉，於是數字繞回去變成負的。

1long long big = 1000000LL * 1000000LL;2cout << big << endl;        // 1000000000000  ✅

⚠️ 那個 LL 不能省。

1long long big = 1000000 * 1000000;    // 🔴 還是錯的

因為右邊兩個都是 int，乘法在變成 long long 之前就已經溢位了。 LL 是在說「這個字面值是 long long」。

判準：算出來的中間值會不會超過 21 億？ 會 → 全部用 long long。競賽裡多打幾個字比錯一題便宜。

二、複雜度：從時限倒推做法

比賽機器一秒大約跑 10⁸ 次基本運算。

看到 n ≤ 100000 就知道雙層迴圈不能用。 這不是猜的——10⁵ × 10⁵ = 10¹⁰，是一秒能跑的一百倍。

題目給的範圍，就是它在告訴你要用哪一類演算法。

三、短路：右邊不一定會算

&& 左邊不成立的時候，右邊根本不會算：

1if (n > 0 && 10 / n > 1) cout << "safe" << endl;

n 是 0 的話，左邊 n > 0 不成立，右邊就不會算了。

如果會算，10 / 0 會讓程式當掉。

⚠️ 所以順序有意義：把「檢查」放左邊，「會出事的操作」放右邊。

if (i < v.size() && v[i] == x)      // ✅ 先檢查範圍
if (v[i] == x && i < v.size())      // 🔴 反了，會越界

完成的樣子

1#include <iostream>2using namespace std;3int main() {4    long long big = 1000000LL * 1000000LL;5    cout << big << endl;6    int n = 5;7    if (n > 0 && 10 / n > 1) cout << "safe" << endl;8    return 0;9}

換你了

把 1000000LL 的兩個 LL 都拿掉，執行看看印出什麼。

（會是一個奇怪的數字，而沒有任何警告。）

到編輯器做這一題：練習：把兩個 LL 拿掉，看它印出什麼

做一個

算出 1 加到 1000000 的總和，印出來。

🔴 先用 int 寫一次，記下它印出什麼，再換成 long long。 那個錯的答案是負數，而程式沒有報任何錯。這就是這一課第一件事。 ⚠️ 另外：用迴圈加一百萬次，和用公式一次算完，跑起來差多少？兩種都試。

到編輯器做這一題：做一個：1 加到一百萬

這一課你做了什麼

• 你看到 int 溢位是安靜的，而 long long 的 LL 不能省
• 你學會從 n 的範圍倒推可以用什麼演算法
• 你知道 && 的右邊不一定會算，而那可以用來擋越界

如果卡住了