第十四届蓝桥杯大赛软件赛省赛C/C++ 大学 B 组（部分题解）

前言

一年一度的🏀杯马上就要开始了，为了取得更好的成绩，好名字写了下前年2023年蓝桥杯的省赛真题，感觉题目还不错（好难）为此来写篇博客重温一下这几个题。也可以帮助一下第一次参加蓝桥杯的新手小白更好冲击省一。
2023年的题目感觉比我们2024年的题目难（还好我不是去年参加的），不过🏀杯声名远扬，打打暴力可能就能获奖省一，从此成为同学眼中的“大神”。
只写了5个题，剩下的再看看。。。

日期统计

题意：

直接上图片吧，节省时间。
这题一看就非常简单了，毕竟作为第一题肯定不会太难。写出来第一题估计就能省三到省二区间了，大家也可以移步去看看。24年的第一题（更简单）
我们直接暴力打表，六七层循环跑出来，但是要注意其中的细节，这题就是考细节了。
代码就不展示了，好名字的代码找不到了，反正就是这样，然后再那样，相信你们都懂。
最后得到的答案是235。
这题so easy ，必须确保拿下。

冶炼金属

题意：

这是一个数学+二分的题目。我们可以知道
$75➗20=3$
$75➗21=3$
$75➗22=3$
。。。看下来我们可以知道75除以一个区间的数字都是可以等于3，所以对于每一组数据，我们都有一个区间的值符合要求，那么我们可以求出来每一个数据的区间，最后对他们取∩，我们就可以得到最小值，再进行一次取∩我们可以得到最大值。这是二分答案的写法。不会二分答案的同学，可以移步这里。
我看有人用数学的方法也可以写，这里就不做演示了。
这个题在我去年打蓝桥杯的时候就写过博客，大家可以进我主页看看。给朱波点点关注

int n;
vector<int>a,b;

void Solve () {
	cin>>n;
	a.resize(n+1);
	b.resize(n+1);//vector容器的重构大小
	for (int i=1;i<=n;i++) {
		cin>>a[i]>>b[i];
	}
	int left =-1e9,right=1e9;
	for (int i=1;i<=n;i++) {
		int l = 1,r = 1e9;
		while (l<r) {
			int mid = l+r>>1;
			if (a[i]/mid<=b[i]) r = mid;
			else l = mid+1;
		}
		left = max(left,l);
	}
	for (int i=1;i<=n;i++) {
		int l = 1,r = 1e9;
		while (l<r) {
			int mid = l+r+1>>1;
			if (a[i]/mid>=b[i]) l = mid;
			else r = mid-1;
		}
		right = min(right,l);
	}//两次二分
	cout<<left<<' '<<right;
 	return ;
}

这题可以搞，easy。

岛屿个数

题意：

大眼一看主播就知道这是一个搜索题，不过子岛屿的存在让主播有些许的头疼，不过利用瞪眼法我们可以知道，如果一个岛屿外面的海洋是公共的海洋，那么这个岛屿就没有被包围，这个岛屿就不是子岛屿。
所以，我们可以先DFS一遍外海洋，全部标记一遍，再利用这类题的传统解法。⚠️我们题目给出的边界之外全部都是海洋，所以我们可以自己处理一下，像这样

然后附上代码

char a[100][100];
int n,m;
int dx[]={0,0,1,-1,-1,1,-1,1},dy[]={1,-1,0,0,1,1,-1,-1};
int vis1[100][100],vis2[100][100];
int f = 0;
void dfs1 (int x,int y) {
	for (int i=0;i<8;i++) {
		int nx = x+dx[i],ny = y+dy[i];
		if (nx<0||nx>n+1||ny<0||ny>m+1||vis1[nx][ny]||a[nx][ny]=='1') continue;
		vis1[nx][ny] = 1;
		dfs1(nx,ny);
	}
}

void dfs2 (int x,int y) {
	for (int i=0;i<4;i++) {
		int nx = x+dx[i],ny = y+dy[i];
		if (nx<0||nx>n+1||ny<0||ny>m+1||vis2[nx][ny]) continue;		
		if (vis1[nx][ny]==1) f =1;	
		if (a[nx][ny]=='1'){
			vis2[nx][ny] = 1;
			dfs2(nx,ny);
		}	
	}
}

void Solve () {
	cin>>n>>m;
	memset(vis1,0,sizeof vis1);
	memset(vis2,0,sizeof vis2);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			cin>>a[i][j];
		}
	}
	for (int i=0;i<=n+1;i++) {
		for (int j=0;j<=m+1;j++) {
			if (i==0||i==n+1||j==0||j==m+1) a[i][j] = '0';
		}
	}
	vis1[0][0]=1;
	dfs1(0,0);
	int ans = 0;
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=m;j++) {
			if (a[i][j]=='1' && vis2[i][j]==0) {
				vis2[i][j]=1;
				f = 0;
				dfs2 (i,j);
				if (f) {
					ans++;
				}
			}
		}
	}
	
	cout<<ans<<'\n';
 	return ;
}

注意记得初始化，主播因为没有初始化一开始，看了半天不知道哪里出错了，这是个多实例！！！
这个题也不难，不过OI赛制下可能写搜索题可能不太友好。说不定就差一个字母，这个题都没分。

子串简写

题意：

这一题找有多少符合条件的子串，并且要求这个子串的长度不能小于k，这个子串的首尾两个字母要和样例给出的一样，我们发现当我们在某处符合条件再往后找的时候，但凡出现字符b都是符合条件的。
举个例子：

首字母为a，尾字母为b，长度为4）
adcb这个答案显然为1
adcbb这个就是2
adcbbbbb这个就是5
aadcbbbbb这个就是10

我们可以看出，这显然和前缀和有关，所以我们思考一下，就可以知道，这个和前缀和其实没啥关系，但是和后缀和关系就大了，我们对串预处理一下，出现b的位置标为1，否则就是0。
然后用后缀和相加起来，我们可以输出一下这个后缀和看下，以样例为例

4 4 3 3 2 2 1 1

而后我们遍历这个串，从出现a的位置往后找k位，用后缀和快速找到后面有多少b，就是这个位置往后有多少符合条件的解，最后全部加起来就是答案。

void Solve () {
	int k;cin>>k;
	string s;cin>>s;
	s = " "+s;
	int t = s.size();
	vector<int>x(t+2);
	char a,b;cin>>a>>b;
	for (int i=1;s[i];i++) {
		if (s[i]==b) x[i] = 1;
		else x[i] = 0;
	}
	for (int i=t-1;i>=1;i--) {x[i] = x[i+1]+x[i];}
	int ans = 0;
	for (int i=1;i<s.size()-k+1;i++) {
		if (s[i]==a) {
			ans+=x[i+k-1];
		}
	}
	cout<<ans<<'\n';
 	return ;
}

这个题赛时可以全写完，不难。

整数删除

题意：

这一题真的是挺不容易的，难度我觉得在CF1400+，主要就是对于小根堆的处理。不知道大小根堆的人有难了。还是去看下大小根堆的介绍理解一下吧。
每次删除一个最小数，我们很容易就能想到是小根堆的利用，但是本题会让其他数字也发生变化，我们又不能对于小根堆里面的数字进行更改，怎么办呢？
不能改我们就不改了嘛，我们用一个数组存一下每个位置改变的值，当要删除这个数字的时候，看看你会不会被前面删除的数字影响，就比如1,2,3我们先删除1，那么下一个2就会受影响变成3。同时如果是2 1 3的话，我们删除1，这时2的右领居和3的左领居就会发生变化，我们下次变化的时候就要进行调整。
所以我们要对于每一个数字的左右领居进行维护，然后用一个cnt数组记录每个位置的变化情况。
最后对于小根堆不停的删除最小的数字，当这个即将删除的数字会被之前的删除的数字影响，我们就push这个数字加上cnt的值放进小根堆里面。（小根堆还会自动排序，太好用了！）再进行判断。
最后输出就行了，看下代码。

priority_queue<PII,vector<PII>,greater<PII>>q;//用pair开小根堆记录这个值，和位置
void Solve () {
    int n,k;cin>>n>>k;
    vector<int>l(n+10),r(n+10);
    for (int i=1;i<=n;i++) {
        int x;cin>>x;
        q.push({x,i});
        l[i] = i-1;
        r[i] = i+1;
    }
    vector<int>cnt(n+10,0);   
    while (k--) {
        int x = q.top().fi;
        int id = q.top().se;
        q.pop();    
        if (cnt[id]) {
            q.push({x+cnt[id],id});
            k++;//重新放进去再进行判断，所以k++
            cnt[id] = 0;
        }
        else {
            int le = l[id],ri = r[id];
            cnt[le] += x;cnt[ri] += x;
            r[le] = ri; l[ri] = le;//变化id这个位置的左右邻居
        }
    }
    map<int,int>mp;
    while (q.size()) {
        int x = q.top().fi;
        int y = q.top().se;
        q.pop();
        mp[y] += (x+cnt[y]);
    }
    for (auto t : mp) cout<<t.se<<' ';    
     return ;
}

注意数组要开大一点，不然就会像我一样WA好几发（蓝桥杯赛场就炸缸了）
感觉这一题挺好的，可以细细斟酌一下。

总结

蓝桥杯不用想着把正解搞出来，其实暴力跑跑已经可以超过绝大部分人了（在弱省），好好备战，补药让300块打水漂。