【2025藍橋杯】賽前2小時考點梳理

1. 🧩 STL（優先級最高）

核心容器/函數

• vector
push_back() / pop_back() / size()
• string
substr(pos, len) / find(str) / +=
• queue
push() / front() / pop()
• priority_queue
  默認大根堆，小根堆：priority_queue<int, vector<int>, greater<int>>
• sort(v.begin(), v.end())
  自定義排序：bool cmp(int a, int b) { return a > b; }

? 應用場景

• 快速實現數組操作（vector）
• 字符串處理（substr截取子串）
• 堆優化（Dijkstra算法優先隊列）

---

2. 🔢 排序（STL為主）

關鍵模板

// 自定義結構體排序
struct Node { int x, y; };
bool cmp(Node a, Node b) { if (a.x == b.x) return a.y < b.y;return a.x > b.x;
}
sort(v.begin(), v.end(), cmp);

? 應用場景

• 貪心算法前的預處理
• 二分查找前的有序化

---

3. 🔍 二分（必背！）

整數二分模板

int l=1;r=n;
int ans;//ans表示當前答案滿足時的最優解
while(l<=r) 
{int mid=(l+r)>>1;if(check(mid))l=mid+1,ans=mid; else r=mid-1; 
}
cout << ans;

實數二分模板

double l=0, r=1e9;
for (int i=0; i<100; i++) { // 精度控制double mid = (l + r) / 2;if (check(mid)) r = mid;else l = mid;
}

? 應用場景

• 有序數組查找
• 答案單調時的最優解問題（如：分繩子）

---

4. ? 前綴和與差分

一維核心公式

• 前綴和：s[i] = s[i-1] + a[i]
• 差分：diff[l] += c, diff[r+1] -= c

二維差分操作

// 矩陣區域加減
diff[x1][y1] += c;
diff[x2+1][y1] -= c;
diff[x1][y2+1] -= c;
diff[x2+1][y2+1] += c;

? 應用場景

• 區間求和（O(1)查詢）
• 多次區間修改后求最終數組

---

5. 🧮 數學（背公式！）

高頻考點

• 質數判斷：試除法（枚舉到√n）
• 篩質數（線性篩，埃氏篩）
• 快速冪（遞歸分治）：

  long long qpow(long long a, long long b, long long p) {if (b == 0) return 1 % p;long long res = qpow(a, b/2, p);return b % 2 ? res * res % p * a % p : res * res % p;
  }
  

• 最大公約數：__gcd(a, b)（STL自帶）
• 組合數學問題
• 進制問題

---

6. 🤝 并查集 + 貪心

并查集模板

int father[N];
int find(int x) {return father[x] == x ? x : father[x] = find(father[x]);
}
void merge(int a, int b) {father[find(a)] = find(b);
}

貪心策略

• 排序貪心：按權重排序后取最優
• 區間調度：優先選結束早的

---

7. 💻 二進制與位運算

常用操作

• n & 1：判斷奇偶
• n >> 1：等價于 /2
• a ^ b ^ b = a：交換變量 a = a ^ b; b = a ^ b; a = a ^ b;

? 應用場景

• 狀態壓縮（用二進制表示集合）
• 快速計算乘除2的冪

---

8. 🐌 動態規劃（最后沖刺）

經典問題

• 背包問題
  狀態轉移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i])
• 最長遞增子序列
  狀態轉移：dp[i] = max(dp[i], dp[j] + 1) (j < i && a[j] < a[i])

? 突擊技巧

• 背模板！先解決「01背包」「斐波那契」等基礎模型

📌 突擊策略

1. 優先掌握：STL > 排序 > 二分 > 前綴和
2. 代碼默寫：每天手敲一次二分/快速冪模板
3. 動態規劃留到最后，只背經典題！