其他题目

第17届蓝桥杯省赛C++研究生组真题个人解析—C题2026的出现次数
第17届蓝桥杯省赛C++研究生组真题个人解析—D题评测漏洞
第17届蓝桥杯省赛C++研究生组真题个人解析—F题基态坍缩
第17届蓝桥杯省赛C++研究生组真题个人解析—G题综合应变指标

一、题目描述

1.1题目大意

给定一个字符串S，其只包含数字0、2、6。
你可以进行任意次以下操作：在字符串中寻找一个连续子串202，将其替换为6。
你的目标是：通过执行若干次操作，使得最终得到的字符串中，连续子串2026出现的次数最多。
现在，请输出这个最多的出现次数。

1.2输入格式

输入一行，包含一个仅有数字0、2、6组成的字符串S。

1.3输出格式

输出一个整数，表示最终字符串中连续子串2026出现的最大次数。

1.4示例

输入：2022026，输出1
输入：2026202202，输出2

1.5输入数据规模

对于40%的评测用例，字符串S的长度∣S∣满足 1≤∣S∣≤500；
对于所有评测用例，字符串S的长度∣S∣满足 1≤∣S∣≤10的5次方，所有输入字符均限定在{0,2,6}集合内。

要求时间限制在1s，内存为256MB。

二、题目分析及解题代码

2.1题目分析

从题面上初步分析，主要考察字符串搜索算法，题目要求2026出现的最大次数，可以将202替换为6，

1. 那么首先要搜索原字符串中2026的个数，因为不可能将2026中的202替换为6；
2. 其次搜索202202的个数，因为202202可以通过替换变为2026，不过要注意判断202202后的字符是否为6，如果为6那么就不能计数，否则就属于重复了2026的计数；
3. 最后将两个个数相加就是答案。

2.2实现代码

#include<bits/stdc++.h>
#define uLL unsigned long long
using namespace std;

int n;
string s;
int res;

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>s;
	n=s.size();
	s=" "+s;
	for(int i=1; i<=n; i++)
	{
		if(i+3<=n)
		{
			if(s.substr(i,4)=="2026")
			{
				res++;
				i+=3;
				continue;
			}
		}
		if(i+5<=n)
		{
			if(i+5==n)
			{
				if(s.substr(i,6)=="202202")
				{
					res++;
				}	
			}
			else
			{
				if(s.substr(i,6)=="202202" && s[i+6]!='6')
				{
					res++;
					i+=5;
				}
			}
		}
	}
	cout<<res<<'\n';
	return 0;
 } 

2.3代码说明

代码整体逻辑较为清晰，

1. 代码中使用了substr函数进行字符串子串提取，该函数第一个参数为子串第一个字符所在原字符串的位置索引，第二个参数是子串的数目；
2. 计算复杂度为O(n)，而n最大为10的5次方，可以满足时间要求。

三、洛谷平台提交验证

3.1洛谷链接

该题已在洛谷平台上线，地址为https://www.luogu.com.cn/problem/P16248
题目名称为P16248 [蓝桥杯 2026 省研究生组] 2026 的出现次数

3.2提交结果

提交代码结果如下图所示，测试用例全部通过：

四、小结

该题整体难度不大，洛谷平台将该题难度定为普及—，考察的也是基础的字符串查找算法，想要写出解题代码并不难，唯一需要注意的是在分析和编写代码时需要细心一点，不要犯一些小错误。