蓝桥杯2023（十四届）省赛——子串简写（跳跳双指针、妙妙剪枝）

子串简写（跳跳双指针、妙妙剪枝）

1.子串简写 - 蓝桥云课 (lanqiao.cn)

这里的剪枝实在是泰妙啦！

回顾一下我这个蠢蛋的思路：一开始遍历len+i，结果只过了俩；然后遍历i和j，len直接计算，只过了70%；之后将a、b的位置全部存储，遍历ab的所有情况，过了80%；最后使用剪枝，确定了a，确定了首个满足的b，就可以计算得到以a为起点的所有满足条件的b的个数，然后直接break，这才能全过。

本题你可以学到的：存储关键位置解决子串问题、双指针+剪枝（用计算的方式求出当前情况下的数量：总数-首个位置）

#include <iostream>
#include <string>
#include <vector>
using namespace std;



//思路：把字符串中等于a的下标都存起来，把等于b的下标也都存起来。
// 然后判断两者下标之间有无大于等于k，直接加上
// （b的个数-当前b下标（因为cnt2等于b的个数加1，所以直接减就好，不用在加1）


int main()
{
	string s;
	int k;
	char a, b;
	long ans = 0;
	cin >> k >> s >> a >> b;
	vector<int>lista;
	vector<int>listb;
	for (int i = 0; i < s.size();i++)	//把a b的位置存起来
	{
		if (s[i] == a)	lista.push_back(i);
		else if (s[i] == b)	listb.push_back(i);
	}

	//这样遍历只能过80%
	/*for (int i = 0; i < lista.size(); i++)
	{
		for (int j = 0; j < listb.size(); j++)
			if (listb[j] - lista[i] + 1 >= k)
				ans++;
	}*/

	//优化一下，仔细想想，listb[j]<lista[i]的就完全没有必要再遍历一遍，所以我们可以通过一个jump来跳转	
	//同时，比如 aabbbbbbb这种，我们不必一个一个加，因为我们存进去的listb是递增的，
	// 所以当找到第一个满足要求的b的时候，就只需要用size-j就得到以i为起点的所有b的个数了
	int jump = 1;
	for (int i = 0; i < lista.size(); i++)
		for (int j = jump; j < listb.size(); j++)
			if (listb[j] - lista[i] + 1 >= k)
			{
				ans += listb.size() - j;
				jump = j;	//这里用jump=j，这样下次来的时候就不用再遍历jump之前的j了，那些都是不满足的
				break;	//这里直接跳出了，因为只要确定i和首个j就可以得到以i为起点的所有满足的个数，只用算这一次
			}

	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

二刷：

能成功自己做出来了，哇咔咔咔，刷到后面，脑海里面其实真的没有印象了，但是实际上潜意识还是会引导你走向正确的道路，所以，加油吧，刷题人QWQ。

//子串简写
#include <iostream>
#include <string>
#include <vector>
using namespace std;

//可以将对应位置记录下来，然后遍历，不，不用遍历，直接累加b数组后面没计算的个数 

int n; 
string s;
char a,b;
vector<int>amp;
vector<int>bmp;

int main()
{
	cin>>n>>s>>a>>b;
	for(int i=0;i<s.size();i++)
	{
		if(a==s[i])	amp.push_back(i);
		if(b==s[i])	bmp.push_back(i);
	}
	
	long long ans=0;	//不开long long 只能过90%

 	//没有跳转只能过90%，剩下一个超时，跳转是为了避免重复计算 bmp[j]-amp[i]+1<n 的内容
//	for(int i=0;i<amp.size();i++)
//	for(int j=0;j<bmp.size();j++)
//	{
//		if(bmp[j]-amp[i]+1>=n)
//		{
//			ans+=bmp.size()-j;
//			break;
//		}
//	}
	int temp=0; 
	for(int i=0;i<amp.size();i++)
	for(int j=temp;j<bmp.size();j++)
	{
		if(bmp[j]-amp[i]+1>=n)
		{
			ans+=bmp.size()-j;
			temp=j;
			break;
		}
	}
	cout<<ans;
	return 0;
 } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49