2023第十四屆藍橋杯大賽軟件賽省賽C/C++ 大學 B 組(真題題解)（C++/Java題解）

記錄刷題的過程、感悟、題解。
希望能幫到，那些與我一同前行的，來自遠方的朋友😉

大綱：

?1、日期統計-（解析）-暴力dfs（😉藍橋專屬

?2、01串的熵-（解析）-不要chu，認真讀題，并且知道log()怎么用就OK

?3、冶煉金屬-（解析）-其實推理極限，用數學知識就能OK😊

?4、飛機降落-（解析）-暴力搜索dfs（😉藍橋專屬

?5、接龍數列-（解析）-字典dp（😎就是名字高大上點，只是一道dp

?6、島嶼個數-（解析）-bfs+dfs，重點在于會染色+會讀題（廣搜深搜一起整

?7、子串簡寫-（解析）-一道簡單的前綴和

?8、整數刪除-（解析）-優先隊列+雙向鏈表（😎模擬）

9、10 是lca類型的題目，這類題型，攢著。到時候出個專題，一塊搞。😎

知識點：

1、二分查找

2、emplace

3、log() ::cmath::

1、日期統計

問題描述

小藍現在有一個長度為 100?的數組，數組中的每個元素的值都在?0?到?9?的范圍之內。數組中的元素從左至右如下所示：
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
現在他想要從這個數組中尋找一些滿足以下條件的子序列：

子序列的長度為?8；
這個子序列可以按照下標順序組成一個?yyyymmdd 格式的日期，并且要求這個日期是?2023 年中的某一天的日期，例如?20230902，20231223。yyyy 表示年份，mm 表示月份，dd?表示天數，當月份或者天數的長度只有一位時需要一個前導零補充。

請你幫小藍計算下按上述條件一共能找到多少個不同的?2023 年的日期。對于相同的日期你只需要統計一次即可。

答案提交

這是一道結果填空的題，你只需要算出結果后提交即可。本題的結果為一個整數，在提交答案時只填寫這個整數，填寫多余的內容將無法得分。

/*
? 其實本題非常簡單，因為它體現了藍橋杯可以暴力（dfs）的點：
? 首先，以2023開頭是固定的，你可以在前方，先把這個給枝剪掉
? 然后再剩下mmdd這四位中爆搜（dfs，當然多層for循環也行）就行，把所有可能給列舉出來
? 切記，一定要防止日期重復，這點很細節。
*/

C++題解

#include <iostream>
#include <vector>
using namespace std;vector<int> vec{ // 年份剔除，已經存儲完畢3,8, 5 ,1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
};vector<vector<bool>> ymd(13,vector<bool>(32,false)); // 已經非常確定了void t(int mm, int dd){ // 檢測if(mm==1||mm==3||mm==5||mm==7||mm==8||mm==10||mm==12){ // 31天if(0<dd&&dd<=31) ymd[mm][dd]=true;}else if(mm==2){ // 28天if(0<dd&&dd<=28) ymd[mm][dd]=true;}else if(mm==4||mm==6||mm==9||mm==11){ // 30天if(0<dd&dd<=30) ymd[mm][dd]=true;}
}void dfs(int cur, int pla, string str){if(cur==4){ // 判斷int mm = stoi(str.substr(0,2));int dd = stoi(str.substr(2,2));t(mm,dd);return;}for(int i=pla+1; i<vec.size(); ++i){dfs(cur+1,i,str+ to_string(vec[i]));}
}int main()
{dfs(0,0,"");int sum = 0;for(int i=0; i<ymd.size(); ++i){for(int j=0; j<32; ++j){if(ymd[i][j]) sum++;}}cout<<sum<<endl;return 0;
}

Java題解

import java.util.ArrayList;
import java.util.List;public class Main {// 年份剔除，已經存儲完畢static List<Integer> vec = List.of(3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6, 1, 4, 0, 1,0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3);// 已經非常確定了static boolean[][] ymd = new boolean[13][32];// 檢查日期是否合法并標記static void t(int mm, int dd) {if (mm == 1 || mm == 3 || mm == 5 || mm == 7 || mm == 8 || mm == 10 || mm == 12) {// 31 天的月份if (0 < dd && dd <= 31) {ymd[mm][dd] = true;}} else if (mm == 2) {// 28 天的月份if (0 < dd && dd <= 28) {ymd[mm][dd] = true;}} else if (mm == 4 || mm == 6 || mm == 9 || mm == 11) {// 30 天的月份if (0 < dd && dd <= 30) {ymd[mm][dd] = true;}}}// 深度優先搜索static void dfs(int cur, int pla, String str) {if (cur == 4) {// 判斷int mm = Integer.parseInt(str.substring(0, 2));int dd = Integer.parseInt(str.substring(2, 4));t(mm, dd);return;}for (int i = pla + 1; i < vec.size(); ++i) {dfs(cur + 1, i, str + vec.get(i));}}public static void main(String[] args) {dfs(0, 0, "");int sum = 0;for (int i = 0; i < ymd.length; ++i) {for (int j = 0; j < 32; ++j) {if (ymd[i][j]) {sum++;}}}System.out.println(sum);}
}

2、01串的熵

// 只要你不chu，認真讀題，仔細觀察，還是能做本題的

/*
? 但是前提條件之一是，你要知道log的用法 =底數;<cmath>
? C++中，log默認是 ln(..) ，要做到log(真數，指數的底數)，這一步，
需要用換底公式：=ln(真數)/ln(指數的底數)
? 這涉及到，數學中的指數式與對數的轉換
? 細節：log(float/double) 內部只能傳遞這兩種類型，傳出也是，否則也會被隱式轉換
*/
/*
? 本題的式子，都給的這么明顯了，怎么可能還搞不出來？
? H(S)= 首先是負號、然后觀察 100，一個1，兩個0。看出什么沒？
? 當然是后面的對應順序呀。共3個（1個1 1/3) (2個0 2/3）還有個數。
?“ 0 出現次數比 1 少 ”
?根據題意：所以0的個數一定1~23333333/2，之間的某個數字。
*/

C++版

#include <iostream>
#include <cmath>
using namespace std;int main()
{int N = 23333333;for(int i=1; i<=N/2; ++i){int n0 = i; // 0的個數;int n1 = N-i; // 1的個數;double sum = 0;sum-=(double)n0/N*log((double)n0/N)/ log(2)*n0;sum-=(double)n1/N*log((double)n1/N)/ log(2)*n1;if(fabs(sum-11625907.5798)<1e-4){cout<<n0<<endl;break;}}return 0;
}

Java版

import java.lang.Math;public class Main {public static void main(String[] args) {int N = 23333333;for (int i = 1; i <= N / 2; ++i) {int n0 = i; // 0的個數int n1 = N - i; // 1的個數double sum = 0;sum -= (double) n0 / N * Math.log((double) n0 / N) / Math.log(2) * n0;sum -= (double) n1 / N * Math.log((double) n1 / N) / Math.log(2) * n1;if (Math.abs(sum - 11625907.5798) < 1e-4) {System.out.println(n0);break;}}}
}

3、冶煉金屬

問題描述

小藍有一個神奇的爐子用于將普通金屬?O?冶煉成為一種特殊金屬?X。這個爐子有一個稱作轉換率的屬性?V，V?是一個正整數，這意味著消耗?V?個普通金屬?O?恰好可以冶煉出一個特殊金屬?X，當普通金屬?O?的數目不足?V?時，無法繼續冶煉。

現在給出了?N?條冶煉記錄，每條記錄中包含兩個整數?A?和?B，這表示本次投入了?A?個普通金屬?O，最終冶煉出了?B?個特殊金屬?X。每條記錄都是獨立的，這意味著上一次沒消耗完的普通金屬?O?不會累加到下一次的冶煉當中。

根據這?N?條冶煉記錄，請你推測出轉換率?V 的最小值和最大值分別可能是多少，題目保證評測數據不存在無解的情況。

輸入格式

第一行一個整數?N，表示冶煉記錄的數目。

接下來輸入?N?行，每行兩個整數?A、B，含義如題目所述。

輸出格式

輸出兩個整數，分別表示?V?可能的最小值和最大值，中間用空格分開。

樣例輸入
3
75 3
53 2
59 2
樣例輸出
20 25
樣例說明

當?V=20 時，有：?75/20?=3，?53/20?=2，?59/20?=2，可以看到符合所有冶煉記錄。

當?V=25時，有：?75/25?=3，?53/25?=2，?59/25?=2，可以看到符合所有冶煉記錄。

且再也找不到比?20?更小或者比?25 更大的符合條件的?V?值了。

評測用例規模與約定

對于?30% 的評測用例，1≤N≤10^2。

對于?60% 的評測用例，1≤N≤10^3。

對于?100% 的評測用例，1≤N≤10^4，1≤B≤A≤10^9。

// 本題為貪心算法-從局部推至整體、
// 我看網上，其他人用了很多復雜的方法，什么差分吶...
// 好像用不到耶，只需要，推逼一下極限就行
/*
? 聽好嘍，這幾部很關鍵。
? 什么是轉化率消耗的最小值？極限就是你剛好能轉化 B+1塊，
? ? 但因為是推理出來的極限，實際上是不存在的，也就是差一點點。所以要再結果上在+1塊
（例：75/4=18，18+1=19，19就是此時的極限）
? 同樣什么是轉化率消耗的最大值？你的所有金屬A，剛好轉哈為B塊。A/B
*/
// 希望對你有幫助

C++版

#include <iostream>
#define ll long long
using namespace std;
const ll maxl = 0x3f3f3f3f3f3f3f3f; // 偽最大值int main()
{int t;cin>>t;int maxV=maxl,minV=0; // 涉及一個極端情況。int A,B;while(t--){cin>>A>>B;minV=max((A/(B+1)+1),minV); // 最小值maxV=min((A/B),maxV);   // 最大值}cout<<minV<<" "<<maxV;return 0;
}

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long maxV = Long.MAX_VALUE; // 初始化為最大可能值long minV = 0; // 初始化為最小可能值int t = scanner.nextInt();for (int i = 0; i < t; i++) {long A = scanner.nextLong();long B = scanner.nextLong();// 計算當前測試用例的最小和最大值long currentMin = (A / (B + 1)) + 1;long currentMax = A / B;// 更新全局的最小和最大值if (currentMin > minV) {minV = currentMin;}if (currentMax < maxV) {maxV = currentMax;}}System.out.println(minV + " " + maxV);}
}

4、飛機降落

問題描述

N?架飛機準備降落到某個只有一條跑道的機場。其中第?i?架飛機在?Ti??時刻到達機場上空，到達時它的剩余油料還可以繼續盤旋?Di 個單位時間，即它最早可以于?Ti??時刻開始降落，最晚可以于?Ti+Di??時刻開始降落。降落過程需要?Li??個單位時間。

一架飛機降落完畢時，另一架飛機可以立即在同一時刻開始降落，但是不能在前一架飛機完成降落前開始降落。

請你判斷?N?架飛機是否可以全部安全降落。

輸入格式

輸入包含多組數據。

第一行包含一個整數?T，代表測試數據的組數。

對于每組數據，第一行包含一個整數?N。

以下?N?行，每行包含三個整數：Ti?，Di??和?Li?。

輸出格式

對于每組數據，輸出?YES?或者?NO，代表是否可以全部安全降落。

樣例輸入
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
樣例輸出
YES
NO
樣例說明

對于第一組數據，可以安排第?3?架飛機于?0?時刻開始降落，20?時刻完成降落。安排第?2?架飛機于?20?時刻開始降落，30?時刻完成降落。安排第?1?架飛機于?30?時刻開始降落，40?時刻完成降落。

對于第二組數據，無論如何安排，都會有飛機不能及時降落。

評測用例規模與約定

對于?30% 的數據N≤2。

對于?100% 的數據 1≤T≤10，1≤N≤10，0≤Ti,Di,Li≤10^5。

// 我當時寫的時候，一直輪詢檢測超時。我還以為是太暴力了(┬┬﹏┬┬)，結果...是藍橋杯官網出問題了，提交不了，可惡。
// 人家都給你飛機了，而且最多不會超過10架
// 題都給到這種程度了，還猶豫什么？？？直接爆搜，把所有情況給枚舉出來。（最多10！）
// 所以說好聽點，本題本質上就是一道組合題目
/*
? 你要先創建一個數組used[N]，這臺飛機你遍歷過沒
? 然后在爆搜期間，維持一個cnt(原count、簡寫)，去記錄到底停了幾架飛機
? ---以上，這些只是方便縷清思路的一環，接下來才是關鍵---
? 咱假設cur_start是你的最晚開始落下時間、cur_last 其他飛機能開始落下的時間。
? cur_start=Ti+Di 是你的最晚開始落下時間、
? 而cur_last=Ti+Di+Li 才是你最晚落下后，并且能讓其他飛機降落的時間。
? 也就是 cur_last = cur_start+Li;
? 但是認真讀過題的都知道！
? 開始降落的時間，不一定非要是Ti+Di,
? 他取決于2點：

上一架飛機，是啥時候落下的（other_last）
能不能在Ti（最早）時刻落下（Ti）。

? 此刻if(other_last>Ti) cur_last = other_last;
? ? ? if(other_last<Ti) cur_last = Ti;
（確切的是，畫個圖就知道了）
? OK，知道這些了，你確定你還會做不出來嗎？
? 爆搜開始
*/

C++版

#include <iostream>
#include <vector>
using namespace std;const int N = 1e1+5;
int t,n;
vector<bool> used(N,false); // 是否已經降落
vector<vector<int>> res(N,vector<int>(3,0));int flag = false;void dfs(int cur ,int tim){ // nif(cur==n){ // 成功的條件flag=true;return;}for(int i=0; i<n; ++i){// 標準回溯if(!used[i] && tim<=(res[i][0]+res[i][1])){ // tim>vec[i][1] 超過了最晚截止時間used[i]=true;// cout<<i<<" "<<used[i]<<" "<<tim<<" "<<res[i][0]<<" "<<res[i][1]<<endl;int cur_start = max(res[i][0],tim);dfs(cur+1,cur_start+res[i][2]);used[i]=false;}}}int main()
{cin>>t;while(t--){for(int i=0; i<n; ++i) used[i]=false;cin>>n;for(int i=0; i<n; ++i){cin>>res[i][0]>>res[i][1]>>res[i][2]; // 存}dfs(0,0);if(flag) cout<<"YES"<<endl;else cout<<"NO"<<endl;flag = false;}return 0;
}

Java版

import java.util.Scanner;
import java.util.ArrayList;public class Main {static final int N = 105;static int t, n;static boolean[] used = new boolean[N];static int[][] res = new int[N][3];static boolean flag = false;public static void main(String[] args) {Scanner scanner = new Scanner(System.in);t = scanner.nextInt();while (t-- > 0) {for (int i = 0; i < N; i++) {used[i] = false;}n = scanner.nextInt();for (int i = 0; i < n; i++) {res[i][0] = scanner.nextInt();res[i][1] = scanner.nextInt();res[i][2] = scanner.nextInt();}flag = false;dfs(0, 0);if (flag) {System.out.println("YES");} else {System.out.println("NO");}}scanner.close();}static void dfs(int cur, int tim) {if (cur == n) {flag = true;return;}for (int i = 0; i < n; i++) {if (!used[i] && tim <= (res[i][0] + res[i][1])) {used[i] = true;int cur_start = Math.max(res[i][0], tim);dfs(cur + 1, cur_start + res[i][2]);used[i] = false;}}}
}

5、接龍數列

問題描述

對于一個長度為?K?的整數數列：A1,A2,…,AK，我們稱之為接龍數列當且僅當?Ai??的首位數字恰好等于?Ai?1??的末位數字?(2≤i≤K)。例如?12,23,35,56,61,11是接龍數列；12,23,34,56 不是接龍數列，因為?56?的首位數字不等于?34?的末位數字。所有長度為?1?的整數數列都是接龍數列。

現在給定一個長度為?N?的數列?A1,A2,…,AN，請你計算最少從中刪除多少個數，可以使剩下的序列是接龍序列？

輸入格式

第一行包含一個整數?N。

第二行包含?N?個整數?A1,A2,…,AN?。

輸出格式

一個整數代表答案。

樣例輸入
5
11 121 22 12 2023
樣例輸出
1
樣例說明

刪除?22，剩余?11,121,12,2023 是接龍數列。

評測用例規模與約定

對于?20% 的數據，1≤N≤20。

對于?50% 的數據，1≤N≤10000。

對于?100% 的數據，1≤N≤105，1≤Ai≤109。所有?Ai?保證不包含前導?0。

// 有很多，特殊的案例的，11 12 13 35
// 額，字典dp這玩意... 我真的還是第一次聽說耶，
// 挺值得思考的，為什么我在第一次做本題的時候，咋就沒有往動態規劃上想
// 他們都是這樣解釋字典dp的：利用（哈希表）來儲存和管理狀態的優化方式
// 簡而言之，就是通過，鍵值對儲存最優解，適用于不連續的場景，或范圍較大的場景
/*
? 好啦、知道啥是字典序了，就來解決一下本題 -->
? 肯定很多人，在一開始，直接想到貪心、局部最優推導全局最優。
? 于是就嚇唬亂刪一通。
? 舉個例子： 11 12 13 35；
? 你能亂刪嗎？
? 刪 13、35 -> 你就會得到 11 12
? 刪 12 ? ? -> 你就會得到 11 13 15
? 那？該怎么做？難道是將所有的可能，都給枚舉出來刪一遍？
? 額、包超時的。
? 這個時候，你仔細觀察就會發現一個很有趣的現象。
? 畢竟題目就叫做接龍了。
? 不論你刪誰，都跟你的上一個以本首字母，為結尾的字母的狀態有關。
? 這不就是動態規劃，能推導的前提嗎？
? 原順序 13 35 34 45 56
? ? ? ? ? ? ? ? ? ? ? ? ? ?__34-45
? 舉個列子：13-? ? ? ? ? ? ? ?-56 （56你接在誰后面？
? ? ? ? ? ? ? ? ? ? ? ? ? ?--35
? 這個時候，35經過判斷，會接在56后邊
? 所以，這個時候維護一個dp[0~9]之后，dp[i]的含義就是，以i為起始位置的串的長度
? 遞歸公式 dp[last]=max(dp[start]+1,dp[last]);
*/

C++版

#include <iostream>
using namespace std;int main()
{int dp[10]={0};int n; cin>>n;for(int i=0; i<n; ++i){string str;cin>>str;int i1 = str[0]-'0';int i2 = str[str.size()-1]-'0';dp[i2] = max(dp[i1]+1,dp[i2]);}int maxn=0;for(int i=0; i<10; ++i) maxn=max(maxn,dp[i]);cout<<n-maxn<<endl;return 0;
}

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int[] dp = new int[10]; // 初始化動態規劃數組int n = scanner.nextInt();for (int i = 0; i < n; i++) {String str = scanner.next();int i1 = str.charAt(0) - '0'; // 首字符轉數字int i2 = str.charAt(str.length() - 1) - '0'; // 尾字符轉數字// 更新動態規劃狀態if (dp[i1] + 1 > dp[i2]) {dp[i2] = dp[i1] + 1;}}int maxn = 0;for (int num : dp) {if (num > maxn) {maxn = num;}}System.out.println(n - maxn);}
}

6、島嶼個數

問題描述

小藍得到了一副大小為?M×N?的格子地圖，可以將其視作一個只包含字符 '0'（代表海水）和 '1'（代表陸地）的二維數組，地圖之外可以視作全部是海水，每個島嶼由在上/下/左/右四個方向上相鄰的 '1' 相連接而形成。

在島嶼?A?所占據的格子中，如果可以從中選出?kk?個不同的格子，使得他們的坐標能夠組成一個這樣的排列：(x0,y0),(x1,y1),…,(xk?1,yk?1)，其中?(xi+1modk,yi+1modk)是由?(xi,yi)( 通過上/下/左/右移動一次得來的?(0≤i≤k?1)，此時這?k?個格子就構成了一個“環”。如果另一個島嶼?B?所占據的格子全部位于這個“環”內部，此時我們將島嶼?B?視作是島嶼?A?的子島嶼。若?B?是?A?的子島嶼，C?又是?B?的子島嶼，那?C?也是?A?的子島嶼。

請問這個地圖上共有多少個島嶼？在進行統計時不需要統計子島嶼的數目。

輸入格式

第一行一個整數?T，表示有?T?組測試數據。

接下來輸入?T?組數據。對于每組數據，第一行包含兩個用空格分隔的整數?M、N?表示地圖大小；接下來輸入?M?行，每行包含?N?個字符，字符只可能是 '0' 或 '1'。

輸出格式

對于每組數據，輸出一行，包含一個整數表示答案。

樣例輸入
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
樣例輸出
1
3
樣例說明

對于第一組數據，包含兩個島嶼，下面用不同的數字進行了區分：
01111
11001
10201
10001
11111
島嶼?2?在島嶼?1?的“環”內部，所以島嶼?2?是島嶼?1?的子島嶼，答案為?1。

對于第二組數據，包含三個島嶼，下面用不同的數字進行了區分：
111111
100001
020301
100001
111111
注意島嶼?3?并不是島嶼?1?或者島嶼?2?的子島嶼，因為島嶼?1?和島嶼?2?中均沒有“環”。

評測用例規模與約定

對于?30?的評測用例，1≤M,N≤10。

對于?100?的評測用例，1≤T≤10，1≤M,N≤50。
// 注：在上網了解一下，emplace的作用。
// 搜索一下，fill的作用

// 可惡啊，預處理數組大小開小了。(┬┬﹏┬┬)
// 本題是一道典型的搜索類型題目，不論你是用dfs、還是用bfs，還是倆個結合著用，不論如何這都是非常酷的。
// 我非常確定，肯定有些人，一上來就直接被(x0,y0) (x1,y1)...(xi+1modk,yi+1modk) 給整成小迷糊
// 這樣會導致失去很多細節
// 仔細審題，最好在紙上，畫出來
// 就像本題、通過上/下/左/右移動得來的，才算圍成環，畫圖時，就會發現左上呢？右下呢？...等等等
/*
? 作為一道經典的板子題（套路題）
? 做這類型的題目，一般就是現在外層圍一圈海
? 簡而言之，就是在最外圍，多鋪墊一層'0';
? 本題最大的左右就是，在左上角，（0，0）的位置，首先將所有外海染色，
? 為啥(⊙_⊙)？要染色呢，因為沒有染色的，必然有兩種情況
? 1、是島嶼
? 2、是內海
? 這時，思路就清晰了，只要島嶼在內海中，他就是子島嶼，不用計數，但是也要染色，方便繼續搜索。
*/
// 拓展一下，就是emplace家族的用法。（emplace_back、emplace）
// 優點是能直接在容器內，構建元素，避免不必要的拷貝，提高性能
// vector用emplace_back(); list、map等，可用emplace
// 使用方法與insert、push類似。不過是傳入構造元素所需參數。所需參數。

C++版

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e2+5;
int T,m,n; // 組 行 列
vector<vector<int>> arr(N,vector<int>(N,0));
struct node{int x; // 行int y; // 列node(int cx,int cy):x(cx),y(cy){}
};
// 一共8個方向
int fa1[]={0,0,1,-1,1,1,-1,-1};
int fa2[]={1,-1,0,0,-1,1,-1,1};
queue<node> q;
void bfs(){ // 廣搜，用于起始時將外海染色，這個用深搜不太行，因為沒法地毯式染色while(!q.empty()){int x = q.front().x, y = q.front().y;q.pop();if(arr[x][y]!=0) continue; // 不是外海水if(x<0||x>m+1||y<0||y>n+1) continue; // 越界arr[x][y]=2;for(int i=0; i<8; ++i){ // 標準格式，應該不是這樣的if(x+fa1[i]<0||x+fa1[i]>m+1||y+fa2[i]<0||y+fa2[i]>n+1) continue; // 越界q.emplace(x+fa1[i], y+fa2[i]);}}
}
void dfs(int x, int y){ // 深搜，用來將島嶼染色if(arr[x][y]!=1) return; // 不是島嶼if(x<0||x>m+1||y<0||y>n+1) return; // 越界arr[x][y]=3;for(int i=0; i<4; ++i){dfs( x+fa1[i], y+fa2[i] );}
}
int main()
{cin>>T;while(T--){for(int i=0; i<N; i++)for(int j=0; j<N; ++j) arr[i][j]=0;cin>>m>>n;for(int i=1; i<=m; ++i){string str;cin>>str;for(int j=1; j<=n; ++j) arr[i][j] = str[j-1]-'0';}q.emplace(0,0); // 廣搜bfs();int sum=0;for(int i=1; i<=m; ++i){for(int j=1; j<=n; ++j){if(arr[i][j]!=1||arr[i+1][j]!=2) continue; // 跳過sum++;dfs(i,j); // 將這個島嶼統一染色。染成2}}cout<<sum<<endl;}return 0;
}

Java版

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class Main {static final int N = 102;static int T, m, n;static int[][] arr = new int[N][N];static int[] fa1 = {0, 0, 1, -1, 1, 1, -1, -1};static int[] fa2 = {1, -1, 0, 0, -1, 1, -1, 1};static Queue<node> q = new LinkedList<>();static class node {int x;int y;node(int cx, int cy) {x = cx;y = cy;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);T = scanner.nextInt();while (T-- > 0) {for (int i = 0; i < N; i++) {for (int j = 0; j < N; j++) {arr[i][j] = 0;}}m = scanner.nextInt();n = scanner.nextInt();for (int i = 1; i <= m; i++) {String str = scanner.next();for (int j = 1; j <= n; j++) {arr[i][j] = str.charAt(j - 1) - '0';}}q.add(new node(0, 0));bfs();int sum = 0;for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (arr[i][j] != 1 || arr[i + 1][j] != 2) {continue;}sum++;dfs(i, j);}}System.out.println(sum);}scanner.close();}static void bfs() {while (!q.isEmpty()) {int x = q.peek().x;int y = q.peek().y;q.remove();if (arr[x][y] != 0) {continue;}if (x < 0 || x > m + 1 || y < 0 || y > n + 1) {continue;}arr[x][y] = 2;for (int i = 0; i < 8; i++) {if (x + fa1[i] < 0 || x + fa1[i] > m + 1 || y + fa2[i] < 0 || y + fa2[i] > n + 1) {continue;}q.add(new node(x + fa1[i], y + fa2[i]));}}}static void dfs(int x, int y) {if (arr[x][y] != 1) {return;}if (x < 0 || x > m + 1 || y < 0 || y > n + 1) {return;}arr[x][y] = 3;for (int i = 0; i < 4; i++) {dfs(x + fa1[i], y + fa2[i]);}}
}

7、子串簡寫

問題描述

程序猿圈子里正在流行一種很新的簡寫方法：對于一個字符串，只保留首尾字符，將首尾字符之間的所有字符用這部分的長度代替。例如 internation-alization 簡寫成 i18n，Kubernetes （注意連字符不是字符串的一部分）簡寫成 K8s, Lanqiao 簡寫成 L5o 等。

在本題中，我們規定長度大于等于?K?的字符串都可以采用這種簡寫方法（長度小于?K?的字符串不配使用這種簡寫）。

給定一個字符串?SS?和兩個字符?c1??和?c2??，請你計算?S?有多少個以?c1??開頭?c2??結尾的子串可以采用這種簡寫？

輸入格式

第一行包含一個整數?K。

第二行包含一個字符串?S?和兩個字符?c1??和?c2?。

輸出格式

一個整數代表答案。

樣例輸入
4
abababdb a b
樣例輸出
6
樣例說明

符合條件的子串如下所示，中括號內是該子串：

[abab][abab]abdb

[ababab][ababab]db

[abababdb][abababdb]

ab[abab][abab]db

ab[ababdb][ababdb]

abab[abdb][abdb]

評測用例規模與約定

對于?20?的數據，2≤K≤∣S∣≤10000。

對于?100?的數據，2≤K≤∣S∣≤5×10^5。S?只包含小寫字母。c1??和 c2??都是小寫字母。

∣S∣?代表字符串?S?的長度。

// 注：查看二分解法lower_bound()..
// 我看網上很多人都用的是二分解法，這讓我迷惑不已，二分？？？
// 這道題目，用前綴和解決他不香嗎？？
/*
? 其實，本題只需要維護一個數組vec[N]
? N表示，截止到這個位置，包括這個位置，到底有幾個字符c1，
? ----------
? abababdb
? 11223333 - 數字代表該下標之前有幾個C1，包括自己
? ----------
? 在遍歷第二遍，從k-1開始，當遇到b時，直接arr(下標-k+1)，求這個位置，有幾個能匹配成a--b;然后累加。
? 沒嘍
*/

C++版

#include <iostream>
#include <vector>#define ll long long
using namespace std;
const ll N = 5e5+5;
int main()
{int k;cin>>k;string str;char c1,c2;cin>>str;cin>>c1>>c2;vector<ll> vec(N,0);if(str[0]==c1) vec[0]++;ll sum=0;for(int i=1; i<str.size(); ++i){if(str[i]==c1) vec[i]=vec[i-1]+1;else vec[i]=vec[i-1];}for(int i=k-1; i<str.size(); ++i){if(str[i]==c2) sum+=vec[i-(k-1)];}cout<<sum<<endl;return 0;
}

Java版

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取間隔長度 kint k = scanner.nextInt();// 讀取字符串String str = scanner.next();// 讀取兩個字符 c1 和 c2char c1 = scanner.next().charAt(0);char c2 = scanner.next().charAt(0);scanner.close();long[] vec = new long[str.length()];// 初始化前綴和數組的第一個元素if (str.charAt(0) == c1) {vec[0] = 1;}// 計算前綴和數組for (int i = 1; i < str.length(); i++) {if (str.charAt(i) == c1) {vec[i] = vec[i - 1] + 1;} else {vec[i] = vec[i - 1];}}long sum = 0;// 遍歷字符串，統計滿足條件的組合數量for (int i = k - 1; i < str.length(); i++) {if (str.charAt(i) == c2) {sum += vec[i - (k - 1)];}}System.out.println(sum);}
}

8、整數刪除

問題描述

給定一個長度為?NN?的整數數列：A1,A2,…,AN。你要重復以下操作?K?次：

每次選擇數列中最小的整數（如果最小值不止一個，選擇最靠前的），將其刪除。并把與它相鄰的整數加上被刪除的數值。

輸出?K?次操作后的序列。

輸入格式

第一行包含兩個整數?N?和?K。

第二行包含?N?個整數，A1,A2,A3,…,AN?。

輸出格式

輸出?N?K 個整數，中間用一個空格隔開，代表?K?次操作后的序列。

樣例輸入
5 3
1 4 2 8 7
樣例輸出
17 7
樣例說明

數列變化如下，中括號里的數是當次操作中被選擇的數：

[1]?4?2?8?7

5?[2]?8?7

[7]?10?7

17?7

評測用例規模與約定

對于?20?的數據，1≤K<N≤10000。

對于?100?的數據，1≤K<N≤5×10^5，0≤Ai≤10^8。

// 悠悠的嘆息聲？為何？先敬羅衣，后敬魂
// 說實話，本題一看，我就知道，本題跟優先隊列有關，但是有一件挺無奈的事情是他要不停的刪除東西...
// 眾多周知，priority_queue內部就是一個黑盒(會用就行-其實內部是堆heap)
// 所以本題的難度就是，如何將priority_queue內部的東西，邊用邊刪除
// 當然，這里面，也有一個非常重要的細節！！！priority_queue重載的時候，要分情況重載，因為這是一個有序數組。
/*
? 其實也不難的，有人說用并查集，其實鏈表就能解決
? 只能說，這道題，你知道大概解法，你就能做，不知道，你肯定不會
? 本題需要維護一個雙向鏈表（可不是標準鏈表）是用兩個數組模擬一個鏈表pre[N],ne[N];
? 然后在維護一個數組(sum[i])，去記錄那些值改變了
? 切記，設置鏈表的時候，最開始位置，從1開始。方便減1 or 加1
? 假設，刪掉下標為cur的值(num)的時候
? pre[ne[y]]=pre[y]; ne[pre[y]]=ne[y]; 切記（不是！不是！sum[cur-1]+=num,sum[cur+1]+=num;，導致鏈接錯誤
? 既然刪掉該值了，吶本坐標，也就不再存在了，所以接下來要改變坐標。
? 這時，你要將cur儲存的下一位的坐標--傳給左邊
? 將cur儲存的上一個位置---傳遞給右邊
? ------------
? pre 0 1 2 3
? val 1 2 3 4
? ne ?2 3 4 5
? ------------
? 刪掉val值2之后,1和3的pri與ne都回改變
? ------------
? pre 0 1 1 3
? val 1 2 3 4
? ne ?3 3 4 5
? ------------
? OK了，其他的，想必大家就清楚了
? 切接，priority_queue默認大堆頂
*/

C++版

#include <iostream>
#include <vector>
#include <queue>
#define ll long long
const ll N = 1e6+5;
ll n,k;
using namespace std;
vector<ll> pre(N, 0);
vector<ll> ne(N, 0);
vector<ll> sum(N,0);
vector<ll> a(N,0);
// 重載
struct cmp{ // ！！！bool operator() (const pair<ll,ll>& p1, const pair<ll,ll>& p2){if(p1.first == p2.first) return p1.second > p2.second; // 值相同選下標小的return p1.first > p2.first; }
};int main() // 天吶，這些都是什么東西   ·
{cin>>n>>k;priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,cmp> p;ne[0]=1;for(int i=1; i<=n; ++i){ll val;cin>>val;p.emplace(val,i);//pre[i]=i-1;ne[i] =i+1;}while(k--){ // 進行k次操作ll val = p.top().first;ll y = p.top().second;while(sum[y]){val += sum[y];p.pop();p.emplace(val,y);sum[y]=0;// 更新val = p.top().first;y = p.top().second;}// 鏈表更新錯誤sum[pre[y]]+=val;sum[ne[y]]+=val;// 更新pre[ne[y]]=pre[y];ne[pre[y]]=ne[y];p.pop();}// 提取出來while(!p.empty()){a[p.top().second]=p.top().first;p.pop();}for(int i=1; i<=n; i++)if(a[i]+sum[i]) cout<<a[i]+sum[i]<<" ";return 0;
}

Java版

import java.util.PriorityQueue;
import java.util.Scanner;// 自定義比較器，用于優先隊列
class PairComparator implements java.util.Comparator<Pair> {@Overridepublic int compare(Pair p1, Pair p2) {if (p1.val == p2.val) {return Long.compare(p1.index, p2.index);}return Long.compare(p1.val, p2.val);}
}// 定義 Pair 類，用于存儲值和索引
class Pair {long val;long index;Pair(long val, long index) {this.val = val;this.index = index;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);long n = scanner.nextLong();long k = scanner.nextLong();long[] pre = new long[(int) (n + 2)];long[] ne = new long[(int) (n + 2)];long[] sum = new long[(int) (n + 2)];long[] a = new long[(int) (n + 2)];// 優先隊列，使用自定義比較器PriorityQueue<Pair> p = new PriorityQueue<>(new PairComparator());ne[0] = 1;for (int i = 1; i <= n; i++) {long val = scanner.nextLong();p.offer(new Pair(val, i));pre[i] = i - 1;ne[i] = i + 1;}// 進行 k 次操作for (long i = 0; i < k; i++) {Pair top = p.poll();long val = top.val;long y = top.index;while (sum[(int) y] != 0) {val += sum[(int) y];sum[(int) y] = 0;p.offer(new Pair(val, y));top = p.poll();val = top.val;y = top.index;}sum[(int) pre[(int) y]] += val;sum[(int) ne[(int) y]] += val;pre[(int) ne[(int) y]] = pre[(int) y];ne[(int) pre[(int) y]] = ne[(int) y];}// 提取優先隊列中的元素while (!p.isEmpty()) {Pair pair = p.poll();a[(int) pair.index] = pair.val;}// 輸出結果boolean first = true;for (int i = 1; i <= n; i++) {if (a[i] + sum[i] != 0) {if (!first) {System.out.print(" ");}System.out.print(a[i] + sum[i]);first = false;}}System.out.println();scanner.close();}
}

后面的兩道題，咱時間有限，就先跳過啦(～￣▽￣)～

要學會做減法。

當然大家有好的代碼、解析，也可以發給我，讓我瞅瞅。( ?? ω ?? )?，我貼上去。

知識點

1、二分查找

二分查找主要位于<algorithmn>頭文件中。常用的有lower_bound、upper_bound、binary_bound

lower_bound

查找第一個大于等于lower_bound的元素

auto it = lower_bound(vec.begin(),vec.end(),num); 
int place = it-vec.begin();

upper_bound

查找最后一個大于lower_bound的元素

auto it = upper_bound(vec.begin(),vec.end(),num); 
int place = it-vec.begin();
cout<<*it<<(it-vec.begin())<<endl; // 兩者皆可

binary_bound

判斷目標值，是否存在

bool t = binary_bound(vec.begin(),vec.end(),num);

set中也設置了lower_bound();

set<int> s;
...
auto it = s.lower_bound(11);

2、emplace

C++中，emplace是 C++11引入的，用于在容器中構建元素，避免復制/移動操作，提高效率。

基本用法

container.emplace(args...);

與push的區別

push: 先構造對象，可能會傳遞。
emplace：傳參、直接構造。
（具體用法的話，就是原本push怎么用，emplace就代替成push。
如：push_back--emplace_back）
（push--emplace）

std::vector<std::pair<int, int>> vec;
// 傳統 push_back
vec.push_back(std::make_pair(1, 2));
vec.push_back({3, 4});  // C++11后可簡化// 使用 emplace_back
vec.emplace_back(5, 6);  // 直接構造 pair，更高效

適用容器

支持?emplace?的容器：
- 序列容器：vector、deque、list
- 關聯容器：map、set、unordered_map、unordered_set
- 適配器：priority_queue（底層容器支持即可）
不支持?emplace?的容器：
- queue、stack?等適配器（接口限制）。

3、log() ::cmath::

在 C++ 里，log()?函數一般是指?<cmath>?頭文件里用于進行對數運算的函數。下面會詳細介紹?log()?函數的具體用法。

`log()`?函數原型

<cmath>?頭文件里定義了幾個不同版本的?log()?函數，常用的有：

// 計算自然對數（以 e 為底）
double log(double x);
float log(float x);
long double log(long double x);

這些函數接收一個浮點數參數?x，并返回?x?的自然對數（以自然常數?e?為底）。

以其他底數計算

其他對數函數

除了?log()?函數，<cmath>?頭文件還提供了其他對數相關的函數：（C++11及之后適用）