第十五屆藍橋杯C/C++B組省賽真題講解（分享去年比賽的一些真實感受）

試題A——握手問題

一、解題思路

直接用高中學的排列組合思路

二、代碼示例

#include<bits/stdc++.h>
using namespace std;
int fun(int n)
{int sum=0;for(int i=0;i<n;i++){for(int j=i+1;j<n;j++)sum++;	}	return sum;
} 
int main()
{cout<<fun(50)-fun(7);
}

三、感悟：

這是一個簽到題，都不需要編程都可以做出來

試題B——小球反彈

一、解題思路

大家可以先思考一下，因為題目要求是從左上角射出到第二次到達左上角，在x方向上，是不是一定走了偶數個343720長度，在y方向上，是不是一定也走了偶數個233333長度，設走了i個343720長度，j個233333長度，那x方向上是不是一共走了343720*i長度，y方向上一共走了233333*j長度，斜率又已知，那x方向走的長度比上y方向走的長度是不是就是dx/dy，遍歷i,j,就可以求出來了

如果還是不太理解可以看一下下圖：

假設小球經過四次撞擊就可以回到原點（因為我是對稱畫的，實際上沒有右邊這一部分，但是撞擊后走的路程是相同的，因為斜率是一定的，路程一樣，那在x和y上面走的路程其實也是相同的）所以它最后在x上面走的路程和y上面走的路程是成一定比例的。

二、代碼示例

#include<bits/stdc++.h> 
using namespace std;
typedef long long int ll;
int main()
{//因為i,j一定是偶數，每次加2就行了 for(ll i=2;i<=10000;i+=2){for(ll j=2;j<=10000;j+=2){if(i*343720*17==j*233333*15){cout<<i<<" "<<j<<endl; printf("%.2lf",sqrt((i*343720)*(i*343720)+(j*233333)*(j*233333)));return 0;}}}
}

三、感悟

這題我當時思考了10來分鐘一點沒思路，后來全部都寫完后，又來思考了半個小時，還是想不出來，就直接放棄了，后來看了大家的題解思路才知道是自己的物理學太菜了，大家在賽場上一定要有所取舍，填空題都是5分，如果不會就不要浪費太多時間。

C——好數

題目鏈接：https://www.lanqiao.cn/problems/19709/learning/

我在第十五屆藍橋杯C/C++B組國賽真題講解（分享去年比賽的一些真實感受）-CSDN博客也講過

一、解題思路

本題的目標是計算從 1 到給定正整數 N 范圍內 “好數” 的數量。“好數” 的定義為：按從低位到高位的順序，奇數位（個位、百位、萬位……）上的數字是奇數，偶數位（十位、千位、十萬位……）上的數字是偶數。

暴力思路的核心在于遍歷從 1 到 N 的每一個整數，針對每個整數，逐一檢查其每一位數字是否符合 “好數” 的定義。若符合，則將 “好數” 的計數加 1；若不符合，則繼續檢查下一個整數。最后，計數的結果即為從 1 到 N 中 “好數” 的總數。

二、代碼展示

#include<bits/stdc++.h>//庫函數，萬能頭，記住就好 
using namespace std;//模板記 
//fun(int i)函數用來判斷傳進來的參數i是否是好數，是返回true,否則返回false 
bool fun(int i)
{//count用來記錄當前要判斷的是位數 int count=1;//若i等于0則循環結束 while(i){//若count為奇數位，則count%2=1 if(count%2){//a%10取當前最后一位數字，再對2求余//奇數位需要是奇數，若是偶數，則當前位不符合 if(i%10%2==0)return false;}//如果為偶數位 else{//偶數位需要是偶數，若是奇數，則當前位不符合if(i%10%2==1)return false;}//每次位數+1 count++;//i每次要舍掉最后一位 i/=10;}//若每一位都判斷完成后都沒有return false，說明此數是好數 return true;
}
int main()
{int n;cin>>n;int sum=0;for(int i=1;i<=n;i++)if(fun(i))sum++;cout<<sum;return 0;
}

三、感悟

純暴力，簽到題

D——R格式

題目鏈接：https://www.lanqiao.cn/problems/19710/learning/

一、解題思路

本題要求根據給定的轉換參數?n?，將浮點數?d?按照特定規則轉換為?R?格式整數。規則是先將浮點數乘以?2^n?，再四舍五入到最接近的整數。解題的主要步驟就是實現這個乘法和四舍五入操作，但是這個乘法要用高精度，用普通的long long int會超。

二、代碼展示

#include<bits/stdc++.h>
using namespace std;// 函數fun用于將字符串表示的數乘以2
string fun(string s)
{int n = s.size();int jinwei = 0;  // 用于記錄進位for (int i = 0; i < n; i++){if (s[i] == '.') continue;  // 遇到小數點跳過int temp = int(s[i] - '0');  // 將字符形式的數字轉換為整型int neww = temp * 2 + jinwei;  // 當前位乘以2并加上進位jinwei = neww / 10;  // 計算新的進位neww %= 10;  // 取個位作為當前位新的值s[i] = char(neww + '0');  // 將新值轉換回字符形式存回原字符串}if (jinwei > 0) s += char(jinwei + '0');  // 如果最后還有進位，添加到字符串末尾return s;
}// 函數fun2用于對字符串表示的數進行四舍五入
string fun2(string s)
{reverse(s.begin(), s.end());  // 反轉字符串，方便從低位開始處理int i = 0;while (s[i] != '.') i++;  // 找到小數點位置i++;  // 移動到小數點后一位int jinwei = 1;  // 初始進位為1，模擬進位操作while (jinwei){int temp = s[i] - '0' + 1;  // 當前位數字加1（準備進位）jinwei = temp / 10;  // 計算新的進位temp %= 10;  // 取個位作為當前位新的值s[i] = temp + '0';  // 將新值轉換回字符形式存回原字符串i++;  // 處理下一位}reverse(s.begin(), s.end());  // 再反轉回原順序return s;
}int main()
{int n;string s;cin >> n >> s;  // 輸入轉換參數n和浮點數s（以字符串形式存儲）reverse(s.begin(), s.end());  // 反轉字符串，方便后續處理while (n--){s = fun(s);  // 循環n次，每次將字符串表示的數乘以2}int count = 0;while (s[count] == '0' || s[count] == '.'){count++;  // 跳過前導0和小數點}reverse(s.begin(), s.end());  // 再次反轉回原順序int nLen = s.size() - count;  // 得到有效數字部分的長度int sign = 0;for (int i = 0; i < nLen; i++){if (s[i] == '.') sign = int(s[i + 1] - '0');  // 找到小數點，記錄小數點后一位數字}if (sign == 0){for (int i = 0; i < nLen; i++) cout << s[i];  // 小數點后一位是0，直接輸出有效數字部分}else{if (sign >= 5){s = fun2(s);  // 小數點后一位大于等于5，進行四舍五入for (int i = 0; i < nLen; i++){if (s[i] == '.') break;  // 遇到小數點停止輸出else cout << s[i];  // 輸出四舍五入后的整數部分}}else{for (int i = 0; i < nLen; i++){if (s[i] == '.') break;  // 小數點后一位小于5，直接輸出整數部分else cout << s[i];}}}return 0;
}

注意：我的代碼不知道為什么只能過90%的樣例，可能還有10％的情況我沒有考慮到，求大神告知

三、感悟

這一題的話如果學了高精度的話并不難，如果沒有學的話，可以直接用暴力,最好先用快速冪求出2^n，然后乘以d，四舍五入判斷進行強制類型轉換，判斷是否加1就行

E——寶石組合

題目鏈接：https://www.lanqiao.cn/problems/19711/learning/

一、解題思路

（由于其他同學講的特別好，所以我借鑒過來了）

二、代碼示例

#include<stdio.h>
const int h=1e5;
int main(){int n;scanf("%d",&n);int mp[h+1]={0};//初始化寶石閃亮度統計表for(int i=0;i<n;i++){int t;scanf("%d",&t);mp[t]++;//統計亮度為t的寶石數量}//這里我們另辟蹊徑，直接枚舉精美程度for(int i=h;i>=1;i--){//枚舉精美程度iint ans=0,now=0;//ans表示尋找到了幾個寶石，now表示現在數組有幾個寶石int num[3];//初始化枚舉到的寶石for(int j=i;j<=h;j+=i){//對于每個精美度i，我們都需要尋找閃亮度為i，2i，3i...的寶石并統計數量ans+=mp[j];//把尋找到的寶石數量統計起來for(int k=0;k<mp[j]&&now<3;k++){//把統計到的寶石放到數組num[now]=j;now++;}if(ans>=3){//如果找到了三個以上的寶石，說明存在三個寶石使其精美度為ifor(int k=0;k<3;k++){printf("%d ",num[k]);}//輸出找到的三個寶石printf("\n");return 0;}}}
}

三、感悟

這題的做法也非常巧妙，我當時正賽的時候是暴力枚舉，取三個寶石算s的，但是這題這樣去枚舉精美程度可能會更簡單一些，時間復雜度少了很多，從O（N^3）降到了O（N^2），有點像國賽的立定跳遠，去枚舉遍歷你所要求的那一個值。

F——數字接龍

題目鏈接：https://www.lanqiao.cn/problems/19712/learning/

我在https://blog.csdn.net/SUN19326410095/article/details/147070595也講過

一、解題思路

本題可通過深度優先搜索（DFS）來求解。由于要在 N×N的棋盤上，從左上角(0, 0)出發找到滿足特定規則到達右下角(N - 1, N - 1)的路徑，DFS 適合這種在多種可能路徑中進行探索的場景。游戲規則要求路徑數字按0到(K - 1)循環，且每個格子僅經過一次、路徑不交叉，所以在 DFS 過程中，從起始點開始，每到一個格子，需按 8 個方向（水平、垂直、對角線）去探索新格子。對于每個新格子，要判斷是否在棋盤內，防止越界；檢查是否已訪問，保證每個格子只走一次；確認數字是否符合循環序列，確保路徑數字規則正確；還要查看路徑是否交叉，滿足所有這些條件才能繼續遞歸探索。持續此過程，要么找到符合規則的路徑，若有多條則按字典序選取最小的輸出，要么確定不存在路徑時輸出-1 。

二、代碼展示

#include<bits/stdc++.h>
using namespace std;const int N = 11; // 定義棋盤的最大大小
int n, k; // n 為棋盤大小，k 為數字循環的范圍
int board[N][N]; // 存儲棋盤上的數字
int dx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; // 定義 8 個方向的 x 坐標偏移
int dy[8] = {0, 1, 1, 1, 0, -1, -1, -1}; // 定義 8 個方向的 y 坐標偏移
string path; // 存儲路徑的方向編號
bool visited[N][N]; // 標記棋盤上的格子是否被訪問過
bool edge[N][N][N][N]; // 檢查路徑是否交叉// 深度優先搜索函數，用于尋找路徑
bool dfs(int x, int y) {// 如果到達右下角格子，檢查路徑長度是否為 n*n - 1（因為起點不計入路徑）if (x == n - 1 && y == n - 1) {return path.size() == n * n - 1;}visited[x][y] = true; // 標記當前格子已訪問for (int i = 0; i < 8; i++) { // 遍歷 8 個方向int newX = x + dx[i];int newY = y + dy[i];// 檢查目標格子是否越界、是否訪問過、數字是否滿足循環序列要求if (newX < 0 || newX >= n || newY < 0 || newY >= n) continue;if (visited[newX][newY]) continue;if (board[newX][newY] != (board[x][y] + 1) % k) continue;// 檢查路徑是否交叉（對于斜向移動，檢查是否有反向的路徑）if (edge[x][newY][newX][y] || edge[newX][y][x][newY]) continue;edge[x][y][newX][newY] = true; // 標記路徑path += i + '0'; // 將方向編號加入路徑if (dfs(newX, newY)) return true; // 遞歸搜索下一個格子path.pop_back(); // 回溯，移除路徑中的最后一個方向edge[x][y][newX][newY] = false; // 回溯，取消路徑標記}visited[x][y] = false; // 回溯，取消當前格子的訪問標記return false; // 如果所有方向都無法到達終點，返回 false
}int main() {cin >> n >> k; // 輸入棋盤大小和數字循環范圍for (int i = 0; i < n; i++) { // 讀取棋盤上的數字for (int j = 0; j < n; j++) {cin >> board[i][j];}}// 從起點 (0, 0) 開始搜索路徑if (!dfs(0, 0)) {cout << -1 << endl; // 如果沒有找到路徑，輸出 -1} else {cout << path << endl; // 輸出路徑的方向編號序列}return 0;
}

三、感悟

dfs和bfs年年必考，最近幾年dfs考的最多，像這種題目思路都很類似，很容易掌握

G——爬山

我在藍橋杯C/C++5天逆襲省一之第二天——C++STL容器（增強版）-CSDN博客講過

一、解題思路

二、代碼展示

#include <bits/stdc++.h>
using namespace std;int main()
{int n, P, Q;long long ans = 0;// 定義一個大頂堆h，用于存儲山的高度，方便每次取出最高的山priority_queue<int> h;// 讀取山的數量n，第一種魔法的可用次數P，第二種魔法的可用次數Qcin >> n >> P >> Q;for (int i = 0; i < n; i++){int hi;// 讀取每座山的高度hicin >> hi;// 將山的高度hi加入大頂堆h中h.push(hi);}// 當兩種魔法還有可用次數時，循環進行操作while (P || Q){// 取出堆頂元素，即當前最高的山的高度int first = h.top();h.pop();// 如果兩種魔法都有可用次數if (P && Q){// 比較兩種魔法作用后的山的高度，選擇能使山變得更矮的魔法if (sqrt(first) <= first / 2){// 使用第一種魔法，將山的高度變為其平方根向下取整h.push(sqrt(first));// 第一種魔法可用次數減1P--;}else{// 使用第二種魔法，將山的高度變為其一半向下取整h.push(first / 2);// 第二種魔法可用次數減1Q--;}}// 如果只剩下第一種魔法有可用次數else if (P){// 使用第一種魔法，將山的高度變為其平方根向下取整h.push(sqrt(first));// 第一種魔法可用次數減1P--;}// 如果只剩下第二種魔法有可用次數else if (Q){// 使用第二種魔法，將山的高度變為其一半向下取整h.push(first / 2);// 第二種魔法可用次數減1Q--;}}// 遍歷堆，將剩余山的高度累加起來，得到最終花費的體力值while (!h.empty()){ans += h.top();h.pop();}// 輸出最優情況下需要花費的體力值cout << ans;return 0;
}

注意：這一題可能只能通過90%的樣例，并不能通過全部樣例

三、感悟

這一題也會有少量數據通過不了，例如2，1，3，35，36，歡迎大神來指教一下

H——拔河

我在藍橋杯C/C++5天逆襲省一之第二天——C++STL容器（增強版）-CSDN博客講過

一、解題思路

二、代碼展示

#include<bits/stdc++.h>
using namespace std;
// 定義數組的最大長度
const int N = 1e3+10;
// 存儲前綴和數組
long long a[N];
// 同學的數量
int n;
// 用于存儲所有可能的右區間的力量值之和
multiset<long long>s;// 自定義函數，返回兩個數中的較小值
long long minn(long long a,long long b){if(a<b) return a;else return b;
}int main(){// 讀取同學的數量cin>>n;// 讀取每個同學的力量值，并構建前綴和數組for(int i = 1;i<=n;i++) {cin>>a[i];// 計算前綴和a[i]+=a[i-1]; }// 枚舉所有可能的右區間 [i, j]，并將其力量值之和插入到 multiset 中for(int i = 1;i<=n;i++){for(int j = i;j<=n;j++){// 計算右區間 [i, j] 的力量值之和并插入到 multiset 中s.insert(a[j]-a[i-1]); }}// 初始化最小差距為一個較大的值long long res = 1e9;// 枚舉左區間的右端點 ifor(int i = 1;i<n;i++){// 刪除所有以 i 作為右區間起始點的情況，避免左區間和右區間重疊for(int j = i;j<=n;j++){// 計算以 i 為起始點的右區間 [i, j] 的力量值之和auto k = a[j] - a[i-1];// 從 multiset 中刪除該力量值之和s.erase(s.find(k));}// 枚舉左區間的左端點 jfor(int j = 1;j<=i;j++){// 計算左區間 [j, i] 的力量值之和auto k = a[i] - a[j-1];// 在 multiset 中找到第一個大于等于 k 的元素auto p = s.lower_bound(k);// 如果找到了這樣的元素，計算其與 k 的差值的絕對值，并更新最小差距if(p!=s.end()){res = minn(res,abs(*p-k));}// 如果 p 不是 multiset 的第一個元素，考慮其前一個元素與 k 的差值的絕對值，并更新最小差距if(p!=s.begin()){p--;res = minn(res,abs(*p-k));}}}// 輸出最小差距cout<<res<<endl;return 0;
}