第十二屆藍橋杯省賽軟件類（cc++組）

第一題（空間）

解題思路

答案

#include <stdio.h>int main() {// 計算256MB對應的字節數，1MB = 1024KB，1KB = 1024Blong long total_bytes = 256 * 1024 * 1024; // 每個32位二進制整數占4個字節（32 / 8 = 4）int bytes_per_int = 4; // 計算可存儲的整數個數long long num = total_bytes / bytes_per_int; printf("%lld\n", num);return 0;
}

第二題（卡片）

?解題思路

思路
采用模擬的方式，從1開始不斷嘗試拼出整數，每拼出一個整數，就減少該整數中各個數字對應的卡片數量。當某個數字的卡片數量不足時，就停止模擬，此時上一個成功拼出的整數就是答案。

具體過程
用一個長度為10的數組card_count來記錄\(0 - 9\)每個數字卡片的數量，初始時每個元素的值都為2021。
從1開始循環，對于每個整數i，將其轉換為字符串（方便獲取每一位數字），然后遍歷該字符串，每遇到一個數字j，就將card_count[j]減1。如果在遍歷過程中發現card_count[j]小于0，說明該數字的卡片數量不足，此時循環結束，輸出上一個成功拼出的整數。

答案

card_count = [2021] * 10
num = 1
while True:num_str = str(num)for digit in num_str:digit = int(digit)card_count[digit] -= 1if card_count[digit] < 0:print(num - 1)exit()num += 1

#include <stdio.h>int main() {int card_count[10];for (int i = 0; i < 10; i++) {card_count[i] = 2021;}int num = 1;while (1) {int temp = num;while (temp > 0) {int digit = temp % 10;card_count[digit]--;if (card_count[digit] < 0) {printf("%d\n", num - 1);return 0;}temp /= 10;}num++;}return 0;
}

第三題（直線）

?解題思路

答案?

from math import gcddef simplify_fraction(a, b):d = gcd(a, b)return a // d, b // dpoints = [(x, y) for x in range(20) for y in range(21)]
lines = set()
n = len(points)
for i in range(n):for j in range(i + 1, n):x1, y1 = points[i]x2, y2 = points[j]if x1 == x2:lines.add((x1,))else:kx = y2 - y1ky = x2 - x1kx, ky = simplify_fraction(kx, ky)b = y1 * ky - kx * x1b, ky = simplify_fraction(b, ky)lines.add((kx, ky, b))print(len(lines))

#include <stdio.h>
#include <stdlib.h>// 求最大公約數
int gcd(int a, int b) {return b == 0? a : gcd(b, a % b);
}// 簡化分數形式的斜率和截距
void simplify(int *a, int *b) {int d = gcd(*a, *b);*a /= d;*b /= d;
}typedef struct {int type; // 0表示非垂直直線，1表示垂直直線union {struct {int kx;int ky;int b;} non_vertical;int x;} data;
} Line;// 比較直線是否相同
int compare_lines(const void *a, const void *b) {const Line *l1 = (const Line *)a;const Line *l2 = (const Line *)b;if (l1->type != l2->type) {return l1->type - l2->type;}if (l1->type == 0) {if (l1->data.non_vertical.kx != l2->data.non_vertical.kx) {return l1->data.non_vertical.kx - l2->data.non_vertical.kx;}if (l1->data.non_vertical.ky != l2->data.non_vertical.ky) {return l1->data.non_vertical.ky - l2->data.non_vertical.ky;}return l1->data.non_vertical.b - l2->data.non_vertical.b;}return l1->data.x - l2->data.x;
}int main() {Line *lines = (Line *)malloc(20 * 21 * (20 * 21 - 1) / 2 * sizeof(Line));int line_count = 0;for (int x1 = 0; x1 < 20; x1++) {for (int y1 = 0; y1 < 21; y1++) {for (int x2 = x1; x2 < 20; x2++) {for (int y2 = 0; y2 < 21; y2++) {if (x1 != x2 || y1 != y2) {if (x1 == x2) {lines[line_count].type = 1;lines[line_count].data.x = x1;} else {lines[line_count].type = 0;lines[line_count].data.non_vertical.kx = y2 - y1;lines[line_count].data.non_vertical.ky = x2 - x1;simplify(&lines[line_count].data.non_vertical.kx, &lines[line_count].data.non_vertical.ky);lines[line_count].data.non_vertical.b = y1 * lines[line_count].data.non_vertical.ky - lines[line_count].data.non_vertical.kx * x1;simplify(&lines[line_count].data.non_vertical.b, &lines[line_count].data.non_vertical.ky);}line_count++;}}}}}qsort(lines, line_count, sizeof(Line), compare_lines);int distinct_count = 0;for (int i = 0; i < line_count; i++) {if (i == 0 || compare_lines(&lines[i - 1], &lines[i]) != 0) {distinct_count++;}}printf("%d\n", distinct_count);free(lines);return 0;
}

第四題（貨物擺放）

解析：這題的理解并不難，就是用三重循環暴力找出方案的總類，但是如果直接暴力，因為n十分大，所以直接暴力空間復雜度和時間復雜度是不太能行的，所以換種方法，先找出n的所有因數，再枚舉因數的組合：

找出??的所有因數：我們使用一個循環從??到??遍歷，對于每個能整除??的數?，將??和??都添加到因數列表?factors?中。這樣可以避免重復計算因數。
枚舉因數組合：使用三重循環遍歷因數列表，對于每一組因數?，檢查它們的乘積是否等于?。如果等于?，則說明找到了一種有效的堆放方案，計數器?count?加?。

題解

#include <stdio.h>#define N 2021041820210418LL// 計算 n 的因數，并存儲在 factors 數組中，返回因數的數量
int find_factors(long long n, long long factors[]) {int count = 0;for (long long i = 1; i * i <= n; i++) {if (n % i == 0) {factors[count++] = i;if (i != n / i) {factors[count++] = n / i;}}}return count;
}int main() {long long factors[100000];  // 假設因數數量不超過 100000int factor_count = find_factors(N, factors);int count = 0;// 枚舉因數組合for (int i = 0; i < factor_count; i++) {for (int j = 0; j < factor_count; j++) {for (int k = 0; k < factor_count; k++) {if (factors[i] * factors[j] * factors[k] == N) {count++;}}}}printf("%d\n", count);return 0;
}

?結果

第五題（路徑）?

題目：

解析：要求1到2021之間的最短路徑，這是典型的最短路徑問題，可以以采用Dijkstra算法來計算兩點之間的最短路徑問題。

Dijkstra算法是一種用于計算帶權有向圖或無向圖中單個源節點到所有節點的最短路徑的貪心算法。

構建圖：根據題目條件，對于兩個不同的結點?a?和?b，如果?|a - b| <= 21，則在它們之間添加一條長度為?a?和?b?的最小公倍數的無向邊。
實現最小公倍數計算：編寫一個函數來計算兩個數的最小公倍數。
使用 Dijkstra 算法：計算從結點 1 到結點 2021 的最短路徑長度。

題解：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>#define MAXN 2022
#define INF 0x3f3f3f3f// 計算兩個數的最大公約數
int gcd(int a, int b) {return b == 0 ? a : gcd(b, a % b);
}// 計算兩個數的最小公倍數
int lcm(int a, int b) {return a / gcd(a, b) * b;
}// Dijkstra 算法
int dijkstra(int** graph, int start, int end) {int dist[MAXN];  // 存儲起點到各點的最短距離int visited[MAXN];  // 標記節點是否已訪問memset(dist, INF, sizeof(dist));memset(visited, 0, sizeof(visited));dist[start] = 0;for (int i = 1; i < MAXN; i++) {int min_dist = INF, u = -1;// 找到未訪問節點中距離最小的節點for (int j = 1; j < MAXN; j++) {if (!visited[j] && dist[j] < min_dist) {min_dist = dist[j];u = j;}}if (u == -1) break;visited[u] = 1;// 更新與 u 相鄰節點的距離for (int v = 1; v < MAXN; v++) {if (!visited[v] && graph[u][v] != INF && dist[u] + graph[u][v] < dist[v]) {dist[v] = dist[u] + graph[u][v];}}}return dist[end];
}int main() {int** graph = (int**)malloc(MAXN * sizeof(int*));for (int i = 0; i < MAXN; i++) {graph[i] = (int*)malloc(MAXN * sizeof(int));}//如果程序需要處理大量的數據，可能會導致棧溢出。因為 graph 數組是在棧上分配的，棧空間是有限的。當數組過大時，可能會超出棧的容量。解決辦法：//可以將 graph 數組改為在堆上分配內存，使用 malloc 函數// 初始化圖for (int i = 1; i < MAXN; i++) {for (int j = 1; j < MAXN; j++) {if (i == j) {graph[i][j] = 0;}else if (abs(i - j) <= 21) {graph[i][j] = lcm(i, j);}else {graph[i][j] = INF;}}}// 計算最短路徑int shortest_path = dijkstra(graph, 1, 2021);printf("%d\n", shortest_path);// 釋放內存for (int i = 0; i < MAXN; i++) {free(graph[i]);}free(graph);return 0;
}

gcd?函數：用于計算兩個數的最大公約數，采用遞歸的方式實現。
lcm?函數：用于計算兩個數的最小公倍數，通過公式?lcm(a, b) = a / gcd(a, b) * b?計算。
dijkstra?函數：實現了 Dijkstra 算法，計算從起點?start?到終點?end?的最短路徑長度。
- dist?數組用于存儲起點到各點的最短距離，初始值為無窮大。
- visited?數組用于標記節點是否已訪問，初始值為 0。
- 每次選擇未訪問節點中距離最小的節點?u，標記為已訪問，并更新與?u?相鄰節點的距離。

結果

第六題（時間顯示）

解題思路

輸入處理：借助scanf函數讀取輸入的毫秒數。
單位轉換：把毫秒數轉換為秒數，因為不需要處理毫秒，所以直接除以 1000。
時間計算：
用秒數除以 3600（一小時的秒數），再對 24 取模，得到小時數。
秒數對 3600 取模后再除以 60，得到分鐘數。
秒數對 60 取模，得到秒數。

輸出格式：利用%02d格式化輸出，保證時、分、秒不足兩位時會補前導 0。

答案

#include <stdio.h>int main() {long long milliseconds;scanf("%lld", &milliseconds);// 將毫秒數轉換為秒數long long seconds = milliseconds / 1000;// 計算小時、分鐘和秒int hours = seconds / 3600 % 24;int minutes = seconds % 3600 / 60;int secs = seconds % 60;// 輸出結果，不足兩位時補前導0printf("%02d:%02d:%02d", hours, minutes, secs);return 0;
}

第七題（砝碼稱重）

解題思路

問題分析：

已知有?N?個砝碼，重量分別為?\(W_1, W_2, \cdots, W_N\)，砝碼可以放在天平兩邊，目標是計算能稱出多少種不同的正整數重量。
對于每個砝碼，都有三種處理方式：不使用、放在天平左邊、放在天平右邊。

動態規劃狀態定義：

定義一個布爾型數組?dp，dp[i]?表示是否能夠稱出重量為?i?的物品。這里使用一維數組就可以，因為我們只關心最終能否稱出某個重量，而不需要記錄是用哪些砝碼稱出的（如果需要記錄具體砝碼組合，可能需要更復雜的數據結構）。
初始狀態：dp[0] = true，表示不使用任何砝碼時，可以稱出重量為?0?的物品（這是一個特殊情況，為后續計算做準備）。

動態規劃狀態轉移：

對于每個砝碼?\(W_i\)，遍歷當前已經能稱出的所有重量?j（即?dp[j] == true?的?j）。
當考慮加入砝碼?\(W_i\)?時：
情況一：保持當前重量?j?不變（即不使用該砝碼），這種情況不需要額外操作，因為?dp[j]?已經為?true。
情況二：將砝碼?\(W_i\)?放在天平左邊，此時能稱出的新重量為?\(j + W_i\)，更新?dp[j + W_i] = true（前提是?\(j + W_i < MAX_WEIGHT\)，避免數組越界）。
情況三：將砝碼?\(W_i\)?放在天平右邊，此時能稱出的重量為?\(|j - W_i|\)（取絕對值）。具體計算時，若?\(j \geq W_i\)，則新重量為?\(j - W_i\)；若?\(j < W_i\)，則新重量為?\(W_i - j\)，更新?dp[|j - W_i|] = true。

為了避免重復更新，我們可以使用一個臨時數組?temp?來記錄當前砝碼加入后能稱出的重量，最后再將?temp?數組的值復制回?dp?數組。

統計結果：

遍歷?dp?數組，從?1?到?MAX_WEIGHT - 1，統計?dp[j] == true?的個數，這個個數就是能稱出的不同正整數重量的數量。

內存管理：

由于使用了動態分配的數組（如?dp?數組），在程序結束前需要使用?free?函數釋放這些數組占用的內存，以防止內存泄漏。

答案

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define MAX_WEIGHT 100001int main() {int n;int weights[101];bool *dp = (bool *)calloc(MAX_WEIGHT, sizeof(bool));// 讀取砝碼數量scanf("%d", &n);// 讀取每個砝碼的重量for (int i = 0; i < n; i++) {scanf("%d", &weights[i]);}// 初始化 dp 數組dp[0] = true;// 動態規劃過程for (int i = 0; i < n; i++) {// 臨時數組用于記錄當前砝碼加入后能稱出的重量bool *temp = (bool *)calloc(MAX_WEIGHT, sizeof(bool));for (int j = 0; j < MAX_WEIGHT; j++) {if (dp[j]) {temp[j] = true;// 加上當前砝碼if (j + weights[i] < MAX_WEIGHT) {temp[j + weights[i]] = true;}// 減去當前砝碼（取絕對值）int diff = j > weights[i] ? j - weights[i] : weights[i] - j;temp[diff] = true;}}// 將臨時數組的值復制回 dp 數組for (int j = 0; j < MAX_WEIGHT; j++) {dp[j] = temp[j];}// 釋放臨時數組內存free(temp);}// 統計可以稱出的不同正整數重量的數量int count = 0;for (int j = 1; j < MAX_WEIGHT; j++) {if (dp[j]) {count++;}}// 輸出結果printf("%d\n", count);// 釋放動態分配的內存free(dp);return 0;
}

?第八題（楊輝三角）

解題思路

理解楊輝三角與目標數列

楊輝三角具有如下特點：

第?n?行（從?0?開始計數）有?\(n + 1\)?個元素。

第?n?行第?k?個元素（k?從?0?開始計數）的值等于組合數?\(C_{n}^{k}=\frac{n!}{k!(n - k)!}\)?。將楊輝三角按從上到下、從左到右順序排成數列，我們要在這個數列中找?N?首次出現的位置。

遍歷查找策略

逐行遍歷：從楊輝三角的第?0?行開始，依次處理每一行。因為楊輝三角前面的行元素個數少，先處理前面行可以更快定位到較小的數，符合找首次出現位置的要求。

計算每行元素：對于當前處理的第?n?行，通過組合數公式計算該行第?k?個元素的值。比如計算第?n?行第?k?個元素時，就用?\(C_{n}^{k}\)?的公式，在代碼中通過循環來實現這個公式的計算邏輯。

記錄位置：使用一個變量（如代碼中的?index?）來記錄遍歷過的元素個數。每處理一個元素，index?就加?1?。當找到等于?N?的元素時，此時?index?的值就是?N?在數列中首次出現的位置，輸出該值并結束查找過程。

終止條件

當找到與?N?相等的元素時，就找到了?N?在數列中首次出現的位置，程序可以終止。如果遍歷完很多行（實際做題時要合理設定一個較大的行數范圍）都沒找到?N?，也可按題目要求處理（本題默認能找到）

答案

#include <stdio.h>// 計算組合數函數
int combination(int n, int k) {int result = 1;for (int i = 1; i <= k; i++) {result = result * (n - (i - 1)) / i;}return result;
}int main() {int n;scanf_s("%d", &n);int index = 1;for (int i = 0; i < 1000; i++) {  // 這里假設足夠多行能找到目標數，可按需調整范圍for (int j = 0; j <= i; j++) {int num = combination(i, j);if (num == n) {printf("%d\n", index);return 0;}index++;}}return 0;
}

第九題（雙向排序）

解題思路

問題理解：

輸入包括數組的長度?n?和操作的次數?m?。

每次操作由兩個整數?x?和?y?表示，x?為操作類型（0?表示一種操作，1?表示另一種操作），y?是與操作相關的參數。

目標是根據這些操作對一個初始為?1?到?n?的數組進行調整，得到最終的數組順序。

數據結構選擇：

使用一個結構體數組?s?來模擬棧，結構體?PII?包含兩個成員?first?和?second?，分別存儲操作類型和對應的參數。

用一個數組?ans?來存儲最終的結果數組。

操作處理邏輯：

0?操作處理：

當遇到?0?操作時，如果棧頂元素也是?0?操作（即連續的?0?操作），則取當前?y?和棧頂?y?的較大值，并彈出棧頂元素。這是因為連續的?0?操作中，只保留范圍較大的那個即可。

然后檢查棧中是否存在可以被當前?0?操作覆蓋的?0?操作（即棧中前一個?0?操作的參數小于等于當前?y?），如果存在則彈出這兩個元素（因為它們被覆蓋了，不需要保留）。

最后將當前?0?操作及其參數壓入棧中。

1?操作處理：

當遇到?1?操作且棧不為空時，如果棧頂元素也是?1?操作，則取當前?y?和棧頂?y?的較小值，并彈出棧頂元素。

接著檢查棧中是否存在可以被當前?1?操作覆蓋的?1?操作（即棧中前一個?1?操作的參數大于等于當前?y?），如果存在則彈出這兩個元素。

最后將當前?1?操作及其參數壓入棧中。

生成結果數組：

操作處理完成后，開始根據棧中的操作記錄來填充結果數組?ans?。

從?1?到?top?遍歷棧，對于每個操作：

如果是?0?操作，從?r（初始為?n?）開始，當?r?大于當前?y?且?l（初始為?1?）小于等于?r?時，將?k（初始為?n?）賦值給?ans[r]?，然后?r--?和?k--?。這是因為?0?操作表示降序處理一部分數組，所以從后往前填充較大的數字。

如果是?1?操作，從?l?開始，當?l?小于當前?y?且?l?小于等于?r?時，將?k?賦值給?ans[l]?，然后?l++?和?k--?。這是因為?1?操作表示升序處理一部分數組，所以從前往后填充較小的數字。

如果遍歷完棧后?l?大于?r?，說明已經填充完所有數字，結束填充過程。

處理剩余數字：

如果棧的元素個數?top?為奇數，說明最后一個操作是?0?操作（降序操作），則從?l?開始將剩余的數字依次填充到?ans?數組中。

如果?top?為偶數，說明最后一個操作是?1?操作（升序操作），則從?r?開始將剩余的數字依次填充到?ans?數組中。

輸出結果：

最后，按順序輸出數組?ans?的所有元素，得到最終的結果。

答案

#include <stdio.h>
#include <string.h>
#include <stdlib.h>// 定義一個結構體來模擬 pair 類型
typedef struct {int first;int second;
} PII;PII s[100005];
int n, m;
int top;
int ans[100005];int main() {scanf_s("%d %d", &n, &m);int x, y;for (int i = 1; i <= m; ++i) {scanf_s("%d%d", &x, &y);if (!x) {  // 0 操作if (top && s[top - 1].first == 0) {  // 對于連續的 0 操作只保留一個y = (y > s[top - 1].second) ? y : s[top - 1].second;top--;}while (top >= 2 && s[top - 2].second <= y) {  // 0 操作覆蓋掉亂序區top -= 2;}s[top].first = 0;s[top].second = y;top++;  // 插入}else if (top) {  // 棧不為空,且為 1 操作。if (top && s[top - 1].first == 1) {y = (y < s[top - 1].second) ? y : s[top - 1].second;top--;}while (top >= 2 && s[top - 2].second >= y) {top -= 2;}s[top].first = 1;s[top].second = y;top++;}}int k = n, l = 1, r = n;for (int i = 0; i < top; ++i) {  // 將固定的數字插入 ans 數組里if (s[i].first == 0) {while (r > s[i].second && l <= r) ans[r--] = k--;}else {while (l < s[i].second && l <= r) ans[l++] = k--;}if (l > r) break;}// 如果有數字沒被固定，就還需要將它們存入 ans 數組里if (top % 2 != 0) {while (k > 0) ans[l++] = k--;}else {while (k > 0) ans[r--] = k--;}for (int i = 1; i <= n; ++i) {printf("%d ", ans[i]);}return 0;
}

第十題（括號序列）

解題思路

整個問題的解決分為兩個主要步驟，分別對原始括號序列和經過反轉并交換左右括號后的序列進行處理，計算各自的方案數，最后將這兩個方案數相乘并對?mod?取模得到最終結果。

具體步驟分析

1. 讀取輸入

在?main?函數中，首先讀取用戶輸入的括號序列字符串?s，并獲取其長度?n。這是整個問題的基礎數據，后續的操作都基于這個括號序列展開。

2. 定義狀態和初始化

狀態定義：使用二維數組?f[i][j]?來表示狀態，其中?i?表示處理到括號序列的第?i?個字符，j?表示當前左括號比右括號多的數量。

初始化：在?get?函數中，將?f[0][0]?初始化為?1。這表示在處理括號序列之前（即第 0 個字符），左括號和右括號數量相等的方案數為 1，是一個合法的起始狀態。

3. 狀態轉移

在?get?函數里，通過兩層循環遍歷括號序列進行狀態轉移：

遇到左括號?(?時：

當處理到第?i?個字符且該字符為左括號時，左括號比右括號多的數量會增加 1。所以對于?j?從 1 到?n?的情況，f[i][j]?的值等于?f[i - 1][j - 1]。這意味著當前狀態下左括號比右括號多?j?個的方案數，是由前一個狀態下左括號比右括號多?j - 1?個的方案數轉移過來的。

遇到右括號?)?時：

對于?f[i][0]，它的值等于?(f[i - 1][1] + f[i - 1][0]) % mod。這是因為當左括號和右括號數量相等時（j = 0），可以從之前左括號比右括號多 1 個的狀態轉移過來，也可以保持原來左括號和右括號數量相等的狀態。

對于?j?從 1 到?n?的情況，f[i][j]?的值等于?(f[i - 1][j + 1] + f[i][j - 1]) % mod。這表示當前狀態下左括號比右括號多?j?個的方案數，既可以從之前左括號比右括號多?j + 1?個的狀態轉移過來（因為添加了一個右括號使得差值減少），也可以從當前狀態下左括號比右括號多?j - 1?個的狀態轉移過來（考慮之前狀態的延續）。

4. 尋找最終方案數

在完成狀態轉移后，在?get?函數中通過遍歷?f[n][i]（i?從 0 到?n），找到第一個不為 0 的值并返回。這個值就是處理完整個括號序列后，滿足某種條件（可能是特定的合法括號組合）的方案數。如果都為 0，則返回 -1。

5. 反轉并交換括號

在?main?函數中，調用?reverse_and_swap?函數對原始括號序列進行處理。該函數會將字符串反轉，同時把左括號和右括號進行交換。這樣做的目的是得到一個新的括號序列，然后對這個新序列再次進行上述的狀態轉移和方案數計算。

6. 計算最終結果

將對原始括號序列計算得到的方案數?x?和對反轉并交換括號后的序列計算得到的方案數?y?相乘，然后對?mod?取模，得到最終的結果并輸出。

答案

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
using LL=long long;
const int N = 5005;
int f[N][N];
int mod=1e9+7;
string s;
int n;
LL get(){memset(f,0,sizeof f);f[0][0]=1;for(int i=1;i<=n;i++){if(s[i-1]=='('){for(int j=1;j<=n;j++)f[i][j]=f[i-1][j-1];}else{f[i][0]=(f[i-1][1]+f[i-1][0])%mod;for(int j=1;j<=n;j++)f[i][j]=(f[i-1][j+1]+f[i][j-1])%mod;}}for(int i=0;i<=n;i++)if(f[n][i])return f[n][i];return -1;
}
int main(){cin>>s;n=s.size();LL x=get();reverse(s.begin(),s.end());for(int i=0;i<n;i++){if(s[i]==')')s[i]='(';elses[i]=')';}LL y=get();cout<<(x*y)%mod;
}