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

现在他想要从这个数组中寻找一些满足以下条件的子序列：

1. 子序列的长度为 8；
2. 这个子序列可以按照下标顺序组成一个 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); 

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及之后适用）