前言

无 $I$ $J$。

思想及代码来源：2023年第十四届蓝桥杯软件类C/C++B组省赛真题全程手写代码完全讲解

---

A：日期统计

思路

DFS：

爆搜，$dfs(0, 0, 0)$ 表示枚举数组的第 $0$ 个位置，日期的第 $0$ 个位置，当前日期为 $0$。

搜完时 (即 $pos == 8$) 检验下日期是否合法且不重复，满足则 $++ans$。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
int a[110], ans;//ans记录有多少个不同日期
bool st[20240000];

bool check(int date)
{
	if(st[date])	return false;
	st[date] = 1;

	int m = date / 100 % 100;//取月份
	int d = date % 100;//取日期

	if(m < 1 || m > 12)	return false;//月份非法
	if(m == 1 || m == 3 || m == 5 || m == 7 || m == 8 || m == 10 || m == 12){
		if(d >= 1 && d <= 31)	return true;
	}
	else if(m == 2){
		if(d >= 1 && d <= 28)	return true;
	}
	else{
		if(d >= 1 && d <= 30)	return true;
	}
	return false;
}
void dfs(int x, int pos, int date)
{
	if(x == 100)	return;
	if(pos == 8){
		if(check(date))//日期合法
			++ans;
		return;
	}

	if(	(pos == 0 && a[x] == 2) ||
		(pos == 1 && a[x] == 0) ||
		(pos == 2 && a[x] == 2) ||
		(pos == 3 && a[x] == 3) ||
		(pos == 4 && a[x] >= 0 && a[x] <= 1) ||
		(pos == 5 && a[x] >= 0 && a[x] <= 9) ||
		(pos == 6 && a[x] >= 0 && a[x] <= 3) ||
		(pos == 7 && a[x] >= 0 && a[x] <= 9) 
		)
		dfs(x + 1, pos + 1, date * 10 + a[x]);
	dfs(x + 1, pos, date);
}
int main()
{
	for(int i = 0; i < 100; ++i)
		cin >> a[i];

	dfs(0, 0, 0);//第几个下标,子序列的第几位,日期
	cout << ans << "\n";
	return 0;
}

---

B：01串的熵

思路

观察可发现：

假设字符串 $S$，$|s| = n$，假设有 $v$ 个 $0$，$u$ 个 $1$，则可得出如下式子：

$H(S) = -u * \dfrac{u}{n} * \log_2(\dfrac{u}{n}) - v * \dfrac{v}{n} *log_2(\dfrac{v}{n})$

有了上述式子，我们可以枚举字符串 $S$ 中 $0$ 的个数，且由于 $0$ 出现的次数比 $1$ 少，所以只需要枚举长度 $23333333$ 的一半即可，枚举时根据式子算出对应的熵 $num$，如果算出的熵 $num$ 和题目所给出的信息熵 $11625907.5798$ 差别 < $1e^{-4}$，即是我们所找的答案。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
using db = long double;
const int N = 23333333;
const db eps = 1e-4;
const db ans = 11625907.5798;

int main()
{
	for(int v = 0; v <= N / 2; ++v){
		int u = N - v;
		db num = (-1.0 * u * u / N * log2(1.0 * u / N)) - 1.0 * v * v / N * log2(1.0 * v / N);

		if(fabs(num - ans) < eps){
			cout << v << "\n";
			break;
		}
	}
	return 0;
}

---

C：冶炼金属

思路

方法1（暴力枚举）：

设转化率为 $v$，只能练出 $b$ 个金属，所以有

$b \times v \leq a$，$a \lt (b + 1) \times v$

上式整理得：

$\dfrac{a}{b + 1} \lt v \ \leq \dfrac{a}{b}$

最后多组数据取一个交集即可

方法2（二分答案）：

做两次二分，每次 $l = 1, r = 1e^9$

二分出 $v \ge b_i$的最大值即是 $V_{max}$，二分出的 $v \le b_i$ 的最小值即是$V_{min}$

---

参考代码

方法1（暴力枚举）：

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int n, mn = -1, mx = 2e9 + 10;//最小值和最大值
	cin >> n;

	while(n--){
		int a, b, l, r;
		cin >> a >> b;

		l = a / (b + 1) + 1, r = a / b;
		mn = max(mn, l), mx = min(mx, r);//取交集，缩区间
	}

	cout << mn << " " << mx << "\n";
	return 0;
}

方法2（二分答案）：

#include<bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, a[N], b[N];

bool check_min(int v)
{
	for(int i = 0; i < n; ++i)
		if(a[i] / v > b[i])
			return false;
	return true;
}
bool check_max(int v)
{
	for(int i = 0; i < n; ++i)
		if(a[i] / v < b[i])
			return false;
	return true;
}
int main()
{
	cin >> n;
	for(int i = 0; i < n; ++i)
		cin >> a[i] >> b[i];

	int l = 1, r = 1e9;
	int mn, mx;

	while(l <= r){
		int mid = l + r >> 1;
		if(check_min(mid)){
			mn = mid;
			r = mid - 1;
		}	
		else l = mid + 1;
	}

	l = 1, r = 1e9;
	while(l <= r){
		int mid = l + r >> 1;
		if(check_max(mid)){
			mx = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}

	cout << mn << " " << mx << "\n";
	return 0;
}

---

D：飞机降落

思路

DFS：

类似于全排列的思想，用一个 $flag$ 变量记录当前是否有解，$st$ 数组表示当前飞机是否起飞了。

枚举每一架飞机，如果没起飞过，且当前时间 $time \le t[i] + d[i]$，即不晚于第 $i$ 架飞机的最晚起飞时间，则起飞第 $i$ 架飞机，起飞后记得恢复现场。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
const int N = 20;
int n, t[N], d[N], l[N];
bool st[N], flag;//飞机i是否起飞过，当前是否有解

void dfs(int x, int time)
{
    if(flag)    return;//有解直接剪枝
    if(x == n){
        flag = true;
        return;
    }
    
    for(int i = 1; i <= n; ++i)
        if(!st[i] && time <= t[i] + d[i]){//没起飞过，且当前时间没有晚于第i架飞机的最晚起飞时间
            st[i] = true;
            dfs(x + 1, max(t[i], time) + l[i]);//枚举下一架飞机
            
            if(flag)    return;//搜完后都有解的话直接return掉
            st[i] = false;//恢复现场
        }
}
void solve()
{
    cin >> n;
    flag = false;//多组测试数据复原
    
    for(int i = 1; i <= n; ++i){
        cin >> t[i] >> d[i] >> l[i];
        st[i] = false;//多组测试数据复原
    }
    
    dfs(0, 0);//0时第0架飞机
    if(flag)    puts("YES");
    else    puts("NO");
}
int main()
{
    int t;
    cin >> t;
    
    while(t--)
        solve();
    return 0;
}

---

E：接龙数列

思路

DP：

先求出最大接龙数列的长度 $len$，最后用总长度 $n$ 减去 $len$ 即是我们所求的最少删除个数。

状态表示：

二维：$dp[i][j]$，表示前 $i$ 个数中，以数字 $j$ 结尾的最长接龙数列的长度。

一维：$dp[j]$，表示以数字 $j$ 结尾的最长接龙数列的长度。

状态转移方程：

$a$ 为数字的最高位，$b$ 为数字的最低位。

例：$x = 234, \ a = 2, \ b = 4$。

二维：$dp[i][b] = max(dp[i - 1][b], \ dp[i - 1][a] + 1)$

一维：$dp[b] = max(dp[b],\ dp[a] + 1)$

方程解释：

$dp[b] = max(dp[b],\ dp[a] + 1)$表示要么没接上，要么是接上了以数字 $a$ 结尾的最长接龙数列，且现在接龙数列的结尾更新为 $b$，最长接龙数列长度 + 1。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
int n, dp[10];
int main()
{
	int n, mx = -1;
	cin >> n;

	string s;
	for(int i = 0; i < n; ++i){
		cin >> s;
		int x = s[0] - '0', y = s.back() - '0';//最高位，最低位

		dp[y] = max(dp[y], dp[x] + 1);
		mx = max(mx, dp[y]);//不断更新最长接龙数列的最大长度
	}
    
	cout << n - mx << "\n";
	return 0;
}

---

F：岛屿个数

思路

BFS：

本题难点在于如何判断一个岛屿是否为子岛屿。

判断是否为子岛屿：

即通过走水（八连通，即八个方向），判断能否走到边界，能则不为子岛屿，否则为子岛屿。

遍历整个地图，如果当前点没走过且是陆地（字符 '1'），则走这个岛屿，并标记走的所有点，然后再判断这个点是否为子岛屿，如果不为子岛屿则 ++ans，ans记录岛屿总个数。

---

参考代码

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;
using PII = pair<int, int>;
const int N = 60;

char mp[N][N];
bool st[N][N], used[N][N];
int dx[] = {0, -1, 0, 1, -1, -1, 1, 1};
int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
int n, m;

void bfs_col(int x, int y)
{
	queue<PII> q;
	q.push({x, y});
	st[x][y] = true;

	while(!q.empty()){
		auto t = q.front();
		q.pop();

		for(int i = 0; i < 4; ++i){
			int tx = t.x + dx[i], ty = t.y + dy[i];
			if(tx < 0 || tx >= m || ty < 0 || ty >= n || st[tx][ty] || mp[tx][ty] == '0')
				continue;

			st[tx][ty] = true;
			q.push({tx, ty});
		}
	}
}
bool bfs_out(int x, int y)//判断是否能逃出去，即往水路走，八连通
{
	for(int i = 0; i < m; ++i)//清空used数组
		for(int j = 0; j < n; ++j)
			used[i][j] = false;

	queue<PII> q;
	q.push({x, y});
	used[x][y] = true;

	while(!q.empty()){
		auto t = q.front();
		q.pop();

		if(t.x == 0 || t.x == m - 1 || t.y == 0 || t.y == n - 1)
				return true;
		for(int i = 0; i < 8; ++i){
			int tx = t.x + dx[i], ty = t.y + dy[i];
			if(tx < 0 || tx >= m || ty < 0 || ty >= n || used[tx][ty] || mp[tx][ty] == '1')
				continue;

			used[tx][ty] = true;
			q.push({tx, ty});
		}
	}
	return false;
}
void solve()
{
	scanf("%d%d", &m, &n);//m行n列
	for(int i = 0; i < m; ++i){//每组测试数据清空st数组
		scanf("%s", mp[i]);
		for(int j = 0; j < n; ++j)
			st[i][j] = false;
	}

	int ans = 0;
	for(int i = 0; i < m; ++i)
		for(int j = 0; j < n; ++j)
			if(!st[i][j] && mp[i][j] == '1'){
				bfs_col(i, j);
				if(bfs_out(i, j))//判断当前点是否能逃跑
					++ans;
			}
	printf("%d\n", ans);
}
int main()
{
	int t;
	scanf("%d", &t);

	while(t--)
		solve();
	return 0;
}

---

G：子串简写

思路

前缀和、双指针：

指针 $i$ 从 $k - 1$ 开始扫，指针 $j$ 从 0 开始，每次 $i$ 与 $j$ 的距离都为 $k$，扫的时候统计有多少个 $c1$ 并用 $cnt$ 存储，如果 $s[i] == c2$， 则 $ans += cnt$，最终 $ans$即为所求答案，记得开 $long \ long$，可能会爆 $int$。

---

参考代码

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{
	int k, cnt = 0;
	string s;
	char c1, c2;

	cin >> k >> s >> c1 >> c2;
	int n = s.size();
	LL ans = 0;

	for(int i = k - 1, j = 0; i < n; ++i, ++j){
		if(s[j] == c1) ++cnt;//借助前缀和思想, cnt统计前j个数中总共有多少个c1
		if(s[i] == c2)	ans += cnt;
	}

	cout << ans << "\n";
	return 0;
}

---

H：整数删除

思路

链表、优先队列：

链表维护每个结点的相邻结点的下标，优先队列存取数值和它对应的下标，这里先开了个大根堆，但为了找最小值，此处存数值和下标时存的都是负数，这样可以转化为小根堆，此时优先队列的队首即是最小值。

模拟删数过程，每次取优先队列队首，取的时候都要乘个 -1 才能转化为原来的数值。

---

参考代码

#include<bits/stdc++.h>//链表+优先队列
#define val first//数值
#define pos second//下标
using namespace std;
using LL = long long;
using PLI = pair<LL, int>;//数值-下标
const int N = 500010;

LL a[N];
int n, k, pre[N], nxt[N];;
priority_queue<PLI> q;//默认大根堆，存对应负数即可转换为小根堆

int main()
{
	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; ++i){
		scanf("%lld", &a[i]);
		pre[i] = i - 1;//存前驱结点的编号
		nxt[i] = i + 1;//存后继节点的编号
		q.push({-a[i], -i});
	}

	pre[1] = -1;
    nxt[n] = -1;
	while(k--){
		PLI now;
		do{
			now = q.top();//取队首
			q.pop();//删除队首
			now.val = -now.val, now.pos = -now.pos;//还原数据
		}while(a[now.pos] != now.val);//如果满足while条件则表明当前数据已经被删除，则继续循环
		
		int PRE = pre[now.pos], NXT = nxt[now.pos];
		if(PRE != -1){//当前点不是左端点，即左边还有点
			a[PRE] += now.val;//更新点
			q.push({-a[PRE], -PRE});//放入优先队列
			nxt[PRE] = NXT;
		}

		if(NXT != -1){
			a[NXT] += now.val;
			q.push({-a[NXT], -NXT});
			pre[NXT] = PRE;//当前结点now的后继结点，更新它的前驱为pre[now.pos]
		}
		a[now.pos] = -1;//取了当前点后，将它的值置为-1，表示改点被删除了
	}

	for(int i = 1; i <= n; ++i)
		if(a[i] != -1)
			printf("%lld ", a[i]);
	return 0;
}

---