預備

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

你會學到三件事

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

開始之前

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

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

一、溢位：安靜的錯

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

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

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

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

⚠️ 那個 LL 不能省。

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

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

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

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

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

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

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

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

if (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())      // 🔴 反了，會越界

完成的樣子

int main() {
    long long big = 1000000LL * 1000000LL;
    cout << big << endl;
    int n = 5;
    if (n > 0 && 10 / n > 1) cout << "safe" << endl;
    return 0;
}

換你了

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

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

這一課你做了什麼

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

如果卡住了