2016年藍橋杯C/C++ B組真題詳解與解題心得

前言：初戰藍橋杯的感悟

這是我第一次參加藍橋杯省賽，整場比賽時間緊湊，最後一道大題甚至來不及動筆。賽後複盤發現，全排列算法（next_permutation）在多道題目中都是關鍵突破口，這讓我深刻體會到基礎演算法熟練度的重要性。以下整理幾道印象深刻的題目與解法，供大家參考。

題目一：煤球數目（三角錐堆疊）

題目描述

煤球堆成立體三角錐：第1層1個，第2層3個（三角形），第3層6個，第4層10個……每層皆為三角形數。若共100層，求煤球總數。

解題思路

第 k 層煤球數為三角形數 T_k = k(k+1)/2。總數即為前100個三角形數之和，亦即四面體數公式：
S = Σ_k=1..100 k(k+1)/2 = 100×101×102/6 = 171,700。

參考代碼（C++）

#include <iostream>
using namespace std;
int main() {
    long long sum = 0, layer = 1, inc = 2;
    for (int i = 1; i <= 100; ++i) {
        sum += layer;
        layer += inc++;
    }
    cout << sum << endl; // 171700
    return 0;
}

題目二：生日蠟燭（等差數列求和）

題目描述

某人從某齡開始每年生日吹熄與年齡同數的蠟燭，至今共吹熄236根。求開始過壽派對的年齡。

解題思路

設起始年齡為 a，結束年齡 b（b ≤ 100），則 Σ_i=a..b i = 236。雙重循環枚舉 a、b 即可，複雜度極低。答案為 26 歲（26+27+...+31 = 236）。

題目三：湊算式（全排列暴力搜索）

題目描述

A + B/C + DEF/GHI = 10，其中 A~I 為 1~9 不重複數字。求解法總數。

解題思路

利用 next_permutation 遍歷 9! = 362,880 種排列，檢查等式是否成立（注意浮點數誤差，用 fabs(... - 10) < 1e-6 判斷）。答案為 29 種。

關鍵代碼片段

int a[9], cnt = 0;
for (int i = 0; i < 9; ++i) a[i] = i + 1;
do {
    double val = a[0] + 1.0*a[1]/a[2] + 
                 (100*a[3]+10*a[4]+a[5]) / (100*a[6]+10*a[7]+a[8]);
    if (fabs(val - 10) < 1e-6) ++cnt;
} while (next_permutation(a, a+9));

題目四：快速排序分區函數填空

題目描述

給出快排 partition 函數框架，需填入缺失語句完成單趟分區邏輯。

解析

經典 Hoare 分區法：以 a[p] 為基準，雙指針 i、j 向中間掃描並交換，最後將基準交換至 j 位置。缺失行為 swap(a, p, j);。

題目五：抽簽組合（DFS 深度優先搜索）

題目描述

6 國派遣 5 人觀察團，各國名額上限 {4,2,2,1,1,3}。求國家組合種數（輸出前幾行如 DEFFF, CEFFF…共 101 行）。

解題思路

遞歸函數 f(k, m) 表示處理第 k 國、剩餘 m 個名額。對第 k 國嘗試派 0~a[k] 人，遞歸處理下一國。葉節點 m=0 時輸出方案。填空處為遞歸調用 f(a, k+1, m-i, b);。

題目六：方格填數（回溯 + 剪枝）

題目描述

10 格填 0~9，相鄰（含對角）格子數字不可連續。求合法方案數。

解題思路

預處理每個格子的相鄰格索引，DFS 填數並即時檢查約束。共 1580 種方案。代碼中用硬編碼相鄰關係，雖顯繁瑣但有效。

題目七：剪郵票（連通塊計數）

題目描述

3×4 郵票表（缺 2 格），剪取 5 張連通郵票（僅角連不算）。求不同剪法數。

解題思路

將 12 格編碼 1~12，枚舉所有 C(12,5)=792 個 5 子集，判斷是否連通（BFS/DFS 檢查邊相連）。答案 116。圖中粉紅區域為合法示例。