专栏文章

题解：P12143 [蓝桥杯 2025 省 A] 好串的数目

KKagamino_Natsumi
P12143题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipmrdlr
此快照首次捕获于
2025/12/03 14:32
3 个月前
此快照最后确认于
2025/12/03 14:32
3 个月前
查看原文

P12143 [蓝桥杯 2025 省 A] 好串的数目

思路

我们可以把一整个串分割为多个极大的“连续非递减子串”，称之为“块”。例如， 1225812258 可以被分割为 122122 ， 55 和 88 。
题目中要求一个好串长度为 11 （此时其本身为连续非递减子串），或可以拆分为两个连续非递减子串（注意到长度大于 11 的连续非递减子串也可以被拆分成两个连续非递减子串）。也就是，好串要么本身就是连续非递减子串，要么是两个连续非递减子串拼接的结果。
换句话说，好串必须在某个块内，或正好在相邻的两个块中。
据此可以写出代码，时间复杂度为 O(n)O(n)。

Code

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

int n;
char s[100007];
int cut[100007];
int cnt = 0;
long long ans = 0;

int main()
{
	cin >> (s + 1);
	n = strlen(s + 1);
	int last = 0;
	for(int i = 2; i <= n; i++)
	{
		if(s[i] == s[i - 1] || s[i] == s[i - 1] + 1)
			continue;
		cut[++cnt] = i - last - 1;
		last = i - 1;
	}
	cut[++cnt] = n - last;
	for(int i = 1; i <= cnt; i++)
	{
		ans += 1ll * cut[i] * (cut[i] - 1) / 2 + cut[i];//在块内，长度大于1或长度为1 
		ans += 1ll * cut[i] * cut[i - 1];//分在相邻两块中 
	}
		
	cout << ans << endl;
	return 0;
}

考场Code

考场上没来得及细想，使用了更劣、更丑陋的算法进行统计，不过也足以通过此题。思路是：枚举好串的首位，则在它所处的块的下一块末尾之前的所有数，都可以成为该好串的末位。
CPP
#include<bits/stdc++.h>
using namespace std;

int n;
char s[100007];
int cut[100007];
int cnt = 1;
long long ans = 0;

int main()
{
	cin >> (s + 1);
	n = strlen(s + 1);
	cut[1] = 1;
	for(int i = 2; i <= n; i++)
	{
		if(s[i] == s[i - 1] || s[i] == s[i - 1] + 1)
			continue;
		else 
		{
			cnt++;
			cut[cnt] = i;
		}
	}
	cnt++;
	cut[cnt] = n + 1;
	cnt++;
	cut[cnt] = n + 1;
	for(int i = 1; i <= n; i++)
	{
		int pos = upper_bound(cut + 1, cut + cnt + 1, i) - cut - 1;
		ans += (cut[pos + 2] - i);
	}
	cout << ans << endl;
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...