第十四屆藍橋杯省賽真題解析（含C++詳細源碼）

第十四屆藍橋杯省賽

整數刪除
- 滿分思路及代碼
- - solution1 （40% 雙指針暴力枚舉）
  - solution 2（優先隊列+模擬鏈表 AC）
冶煉金屬
- 滿分代碼及思路
子串簡寫
- 滿分思路及代碼
- - solution 1（60% 雙指針）
  - solution 2（二分 AC）
島嶼個數
- 滿分代碼及思路
飛機降落
- 滿分思路及代碼
接龍數列
- 滿分思路及代碼

整數刪除

在這里插入圖片描述
題目鏈接

滿分思路及代碼

solution1 （40% 雙指針暴力枚舉）

#include <iostream>
using namespace std;
const int N=5e5+10;
int n,k;
int a[N];
int main()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}//實際上我們并不能通過簡單的排序來找到數列中最小的整數//因為這樣會失去原來的相對位置 而導致刪去后的增加操作出錯//所以我們可以用雙指針的思路來寫while(k--){int l=1;int r=n;while(l!=r){if(a[l]<=a[r]){r--;}else{l++;}}//遍歷整個數組尋找最小值if(l==1){a[l+1]+=a[l];}else if(l==n){a[l-1]+=a[l];}else{a[l+1]+=a[l];a[l-1]+=a[l];}//刪除 覆蓋掉for(int i=l;i<=n;i++){a[i]=a[i+1];}n--;
}for(int i=1;i<=n;i++){cout<<a[i]<<' ';}return 0;
}

solution 2（優先隊列+模擬鏈表 AC）

思路參考：
在這里插入圖片描述

#include <bits/stdc++.h>
using namespace std;
// 記錄每個位置的數是否被刪除過
bool removed[500005];
// 數據過大，爆int
#define ll long long
int main()
{int n, k;cin >> n >> k;// 數列，數和左右相鄰的數的距離vector<pair<ll, pair<int, int>>> a(n);// 優先隊列，數和下標priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> p;int t;for (int i = 0; i < n; i++){cin >> t;// 相鄰的數初始距離為1a[i] = {t, {1, 1}};// 數和下標壓入堆p.push({t, i});}//查找k次while (k){// 彈出第一個數pair<ll, int> tp = p.top();p.pop();ll value = tp.first;int index = tp.second;// 如果已經被刪除過，或者被修改過，則跳過，否則刪除if (removed[index] || a[index].first != value)continue;// 標記為已刪除removed[index] = true;// 左右最近未被刪除節點到自己的距離int l = index - a[index].second.first;int r = index + a[index].second.second;// 如果左邊相鄰的數存在則更新if (l >= 0 && !removed[l]){// 更新左邊的數并壓入堆a[l].first += value;p.push({a[l].first, l});// 如果右邊的數存在，則更新左邊的數到右邊的距離if (r < n && !removed[r]){a[l].second.second += a[index].second.second;}}// 如果右邊相鄰的數存在則更新if (r < n && !removed[r]){// 更新右邊的數并壓入堆a[r].first += value;p.push({a[r].first, r});// 如果左邊的數存在，則更新右邊的數到左邊的距離if (l >= 0 && !removed[l]){a[r].second.first += a[index].second.first;}}k--;}// 輸出還未被刪除的數for (int i = 0; i < n; i++){if (!removed[i])cout << a[i].first << " ";}return 0;
}

冶煉金屬

在這里插入圖片描述

滿分代碼及思路

//對于這個v的范圍我們怎么來確定呢
//我覺得是這樣的例如投入75個O產出3個X
//如果最好的情況即浪費的最少得時候即V=25 當然也有小數的情況但也就是直接相除之后向下取整就好最后對于每一次冶煉的V取max
//最壞的情況需要考慮還是拿上面的舉例我們可以從產出4個X所需要的V枚舉到3 最后取min 但是注意此時就需要向上取整即加1；
//因為我們是在找不符合75個出3個X的臨界點即多少O出4個X

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int a[N],b[N];
int n;
int maxval=1e9;
int minval=0;
int main()
{cin>> n;for(int i=0;i<n;i++){cin>>a[i]>>b[i];}for(int i=0;i<n;i++){maxval=min(a[i]/b[i],maxval);minval=max(a[i]/(b[i]+1)+1,minval);}cout<<minval<<' '<<maxval;return 0;
}

子串簡寫

在這里插入圖片描述

題目鏈接

滿分思路及代碼

solution 1（60% 雙指針）

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>using namespace std;// 雙指針方法
int TwoPointers(int K, const string& S, char c1, char c2) {int n = S.length();int count = 0;for (int left = 0; left < n; ++left) {if (S[left] == c1) {for (int right = left + K - 1; right < n; ++right) {if (S[right] == c2) {++count;}}}}return count;
}
//首先暴力的思路類似于雙指針 
//三種情況
//我們用p指針找到C1 保持c1不動移動指針q 讓q不斷去找c2 直到滿足我們的長度我們的res++
//然后q走到最后一個c2了之后移動p 規則一樣
//p q一起動
//
int main() {int K;string S;char c1, c2;// 讀取輸入cin >> K;cin >> S >> c1 >> c2;// 計算結果int result=TwoPointers(K, S, c1, c2);cout << result << endl;return 0;
}

solution 2（二分 AC）

#include<iostream>
#include<algorithm>
using namespace std;
int nec1[500100];
int c1dx = 0;
int c2dx = 0;
int nec2[500100];
int main()
{int k;cin >> k;string str;cin >> str;str = "1" + str;char c1, c2;cin >> c1 >> c2;for (int i = 1; i < str.length(); i++) {//記錄c1字符所有出現的位置if (str[i] == c1) {nec1[c1dx] = i;c1dx++;}//記錄c2字符所有出現位置if (str[i] == c2) {nec2[c2dx] = i;c2dx++;}}long long ans = 0;//枚舉c1字符出現的位置for (int i = 0; i < c1dx; i++) {//二分查找c2字符出現的位置的合法位置auto dx = lower_bound(nec2, nec2 + c2dx, nec1[i] + k-1);//沒有找到情況if (dx == nec2 + c2dx)continue;//找到了int t = dx - nec2;//加上總合法個數ans += c2dx - t;}cout << ans << endl;return 0;
}

島嶼個數

在這里插入圖片描述

題目鏈接

滿分代碼及思路

在我之前的文章搜索系列里面可以找到詳細分析

#include <bits/stdc++.h> 
using namespace std;
const int X = 50 + 10;
typedef pair<int, int> PII;
int grid[X][X];  // 使用 int 類型數組
int n, m, T;
int ans;
int s[X];
// 海的移動偏移量數組
int dx[8] = {-1,-1,-1,0,1,1,1,0};
int dy[8] = {-1,0,1,1,1,0,-1,-1};
// 陸地的移動偏移量
int DX[4] = {-1, 0, 1, 0};
int DY[4] = {0, 1, 0, -1};
bool st_land[X][X];
bool st_sea[X][X];bool check(int x, int y) {if (x < n && x >= 0 && y < m && y >= 0) {return true;}return false;
}// 找到了（x,y）所在的島嶼 并將該島嶼的所有點都標為了 true
void bfs_land(int u, int v) {queue<PII> Q;st_land[u][v] = true;PII tp = {u, v};Q.push(tp);while (!Q.empty()) {PII t = Q.front();Q.pop();for (int i = 0; i < 4; i++) {int nu = t.first + DX[i];int nv = t.second + DY[i];if (check(nu, nv) && grid[nu][nv] == 1 && !st_land[nu][nv]) {st_land[nu][nv] = true;Q.push({nu, nv});}}}
}void bfs_sea(int x, int y) {queue<PII> q;PII tmp = {x, y};q.push(tmp);st_sea[x][y] = true;while (!q.empty()) {PII p = q.front();q.pop();for (int i = 0; i < 8; i++) {  // 枚舉一下海的方向  int nx = p.first + dx[i];int ny = p.second + dy[i];if (!check(nx, ny) || st_sea[nx][ny]) {continue;}if (grid[nx][ny] == 0) {st_sea[nx][ny] = true;q.push({nx, ny});} else if (grid[nx][ny] == 1 && !st_land[nx][ny]) {ans++;bfs_land(nx, ny);  // 如果發現尋找外海的過程中發現了陸地 說明屬于新的外島那么需要找到與他相連的全部陸地}}}
}int main() {cin >> T;while (T--) {cin >> n >> m;ans = 0;  // 每次都需要重置一下for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {st_sea[i][j] = st_land[i][j] = false;}}for (int i = 0; i < n; i++) {string s;cin >> s;for (int j = 0; j < m; j++) {grid[i][j] = s[j] - '0';  // 將字符轉化成數字存進去}}bool has_sea = false;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (i == 0 || i == n - 1 || j == 0 || j == m - 1) {if (!st_sea[i][j] && grid[i][j] == 0) {  // 當前的這個點是海并且是沒有被標記過has_sea = true;bfs_sea(i, j);}}}}// 判斷全是陸地的特例（只有一個大島）if (!has_sea) {ans = 1;}cout << ans << endl;}return 0;
}

飛機降落

在這里插入圖片描述
題目鏈接

滿分思路及代碼

思路直接去看我之前的文章就好：搜索系列
非常詳細具體
視頻講解：非常牛逼

#include <bits/stdc++.h>
using namespace std;
const int N =10+9;//防止越界
int n;//有多少架飛機
//int T,D,L;//分別表示降落時刻，能盤旋的時間，降落的時間
//考慮到這題這三個數據可以代表一架飛機的屬性 可以考慮采用結構體來實現struct plane{
int t;
int d;
int l;
}p[N];
bool s[N];//每架飛機的狀態
//我們需要知道幾架飛機成功降落 和前一架飛機降落的時間
bool dfs(int x,int time)
{if(x>=n){return true;}//遞歸出口//枚舉每種降落順序for(int i=0;i<n;i++){if(!s[i])//這架飛機沒有安排過{s[i]=true;if(p[i].t+p[i].d<time)//燃盡了也沒等到前一架飛機降落完畢{//回溯s[i]=false;return false;}int next=max(p[i].t,time)+p[i].l;//核心 兩種情況的綜合//即一來就可以落 和 需要等前一架降落完畢再落if(dfs(x+1,next)){return true;//后續的飛機都可以順利降落}s[i]=false;}}return false;//所有降落方案都不能成功降落；}
int main()
{int T;//測試的組數cin>>T;while(T--){cin>>n;for(int i=0;i<n;i++){cin>>p[i].t>>p[i].d>>p[i].l;}if(dfs(0,0)){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}for(int i=0;i<n;i++){s[i]=false;}}return 0;}

接龍數列

在這里插入圖片描述

題目鏈接

滿分思路及代碼

其實我們需要轉化題目所問的問題
題目問的是最少需要刪除幾個字符或者說數字等價于求數列最長是多少 ——最長子序列問題
思路參考:視頻講解

#include <iostream>
using namespace std;
const int N = 1e5;
int a[N]; //也可以使用vector,但在效率上會有損失
int dp[10];//全局變量，全部默認初始化為0
int main()
{
int n;
cin >> n;
for (int i = 0;i < n;i++)
{
cin >> a[i];
}
//拆分每一個數，取出首位數字和末位數字
int front, tail;
for (int i = 0;i < n;i++)
{
int cur = a[i];
tail =cur % 10;
front =tail;
while (cur)
{
front = cur%10;
cur= cur / 10;
}
dp[tail] = dp[tail] > dp[front] + 1 ? dp[tail] : dp[front ]+ 1;
}
//找最大的dp數組元素值
int maxLen = 0;
for (int i = 0;i < 10;i++)
{
if (dp[i] > maxLen)
maxLen = dp[i];
}
cout << n - maxLen << endl;
return 0;
}