2021年第十二屆藍橋杯省賽B組C++題解

關鍵詞：藍橋杯、省賽、題解、C++、算法

---

一、個人見解

第十二屆藍橋杯省賽B組共有10道題目，包含5道填空題（T1-T5）和5道編程題（T6-T10），總分150分。比賽時長4小時，填空題需直接提交答案，編程題需通過代碼實現。題目整體難度中等偏上，重點考察暴力枚舉、數論、動態規劃、圖論等算法知識。以下為完整題目解析及優化后的代碼實現。

---

二、題目解析與代碼實現

A. 空間（填空題）

題目描述
小藍用256MB內存開數組，數組元素為32位二進制整數。求最多能存儲多少個這樣的整數？

解題思路

• 單位轉換：1MB=1024KB，1KB=1024B，1B=8bit
• 計算公式：256MB = 256 * 1024 * 1024 B，每個元素占4B（32位）
• 答案：256 * 1024 * 1024 / 4 = 67108864

代碼實現

#include <iostream>
using namespace std;
int main() {cout << 256 * 1024 * 1024 / 4 << endl; // 輸出67108864return 0;
}

---

B. 卡片（填空題）

題目描述
小藍有0-9的卡片各2021張，從1開始連續拼數，直到某數字卡片不足。求最大能拼到的數。

解題思路

• 模擬消耗過程，1的卡片最先耗盡
• 遍歷每個數的每一位，統計卡片使用情況
• 當某卡片數量為負時，返回前一個數

代碼實現

#include <iostream>
using namespace std;
int main() {int cards[10] = {2021}; // 初始化卡片數量for (int i = 1; ; i++) {int num = i;while (num) {int digit = num % 10;if (--cards[digit] < 0) { // 卡片不足cout << i - 1 << endl; // 輸出3181return 0;}num /= 10;}}return 0;
}

---

C. 直線（填空題）

題目描述
給定20×21的網格點，求這些點能確定的不同直線數量。

解題思路

• 枚舉所有兩點組合，計算斜率k和截距b
• 使用set<pair<double, double>>去重
• 注意處理垂直和水平線（共20+21條）

優化代碼

#include <iostream>
#include <set>
using namespace std;int main() {set<pair<double, double>> lines;// 處理非垂直/水平線for (int x1 = 0; x1 < 20; x1++) {for (int y1 = 0; y1 < 21; y1++) {for (int x2 = 0; x2 < 20; x2++) {if (x1 == x2) continue; // 跳過垂直線double k = 1.0 * (y2 - y1) / (x2 - x1);double b = (x2 * y1 - x1 * y2) * 1.0 / (x2 - x1);lines.insert({k, b});}}}cout << lines.size() + 20 + 21 << endl; // 40257return 0;
}

---

D. 貨物擺放（填空題）

題目描述
給定n=2021041820210418，求滿足n=L×W×H的排列方案數。

解題思路

• 找出n的所有因數
• 三重循環枚舉因數組合，統計乘積等于n的方案數
• 優化：先存儲因數，減少重復計算

代碼實現

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;int main() {LL n = 2021041820210418;vector<LL> factors;// 收集所有因數for (LL i = 1; i * i <= n; i++) {if (n % i == 0) {factors.push_back(i);if (i != n / i) factors.push_back(n / i);}}// 枚舉因數組合int ans = 0;for (LL a : factors)for (LL b : factors)for (LL c : factors)if (a * b * c == n) ans++;cout << ans << endl; // 2430return 0;
}

---

E. 路徑（填空題）

題目描述
2021個節點的圖中，節點a與b（|a-b|≤21）有一條邊，邊權為LCM(a,b)。求節點1到2021的最短路徑。

解題思路

• Dijkstra算法求單源最短路徑
• 預處理鄰接表，計算邊權（最小公倍數）

優化代碼

#include <iostream>
#include <cstring>
using namespace std;
const int N = 2025;
int g[N][N], dist[N];
bool vis[N];int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }void dijkstra() {memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < 2021; i++) {int t = -1;for (int j = 1; j <= 2021; j++)if (!vis[j] && (t == -1 || dist[j] < dist[t])) t = j;vis[t] = true;for (int j = max(1, t - 21); j <= min(2021, t + 21); j++)dist[j] = min(dist[j], dist[t] + lcm(t, j));}
}int main() {dijkstra();cout << dist[2021] << endl; // 10266837return 0;
}

---

三、總結

本屆省賽B組題目難度適中，填空題側重數學思維和暴力枚舉，編程題涉及動態規劃和數據結構優化。解題關鍵在于：

1. 單位轉換與公式推導（如A題）
2. 模擬與邊界處理（如B題）
3. 集合去重與精度控制（如C題）
4. 因數分解與組合優化（如D題）
5. 圖論算法應用（如E題）

---

官方資源

• 題目鏈接：藍橋杯題庫
• 報名入口：藍橋杯官網