蓝桥杯2025年第十六届省赛真题-好串的数目

对于一个长度为 n 的字符串 s = s₀ s₁ · · · s_n−1 来说，子串的定义是从中选出 两个下标 l,r (0 ≤ l ≤ r ≤ n − 1)，这之间所有的字符组合起来的一个新的字符串： s’ = s_ls_l+1 · · · s_r 就是其中一个子串。 

现在给出一个只有数字字符 0 ∼ 9 组成的数字字符串，小蓝想要知道在其 所有的子串中，有多少个子串是好串。一个子串是好串，当且仅当它满足以下 两个条件之一： 

1）单字符子串一定是好串，即当子串长度为 1 时，它总是好串； 

2）长度大于 1 时，可以拆分为两个连续非递减子串。 

其中，一个串 p = p₀ p₁ . . . p_k−1 为连续非递减子串 是指，对于所有 1 ≤ i < k ，满足 p_i = p_i−1 或 p_i = p_i−1 + 1 。即数字串中的每一个数字，要么等于上一个 数字，要么等于上一个数字加 1 。例如 12233 、456 是连续非递减子串。

输入一行包含一个字符串 s 。

输出一行包含一个整数表示答案，即好串的数目 。

12258

12

【样例说明 1】 

长度为 1 的好串：1 、2 、2 、5 、8 。它们长度都为 1 ，都是好串。 

长度为 2 的好串：12 、22 、25 、58 。12 可以分割为 1 、2 两个连续非递减子串，其它类似。 

长度为 3 的好串：122 、225 。122 可以分割为 12 、2 两个连续非递减子 串；225 可以分割为 22 、5 两个连续非递减子串。 

长度为 4 的好串：1225 。1225 可以分割为 122 、5 两个连续非递减子串。 

总计 12 个好串。 

【样例输入 2】 

97856 

【样例输出 2】 

13 

【样例说明 2】

 长度为 1 的好串：9 、7 、8 、5 、6 ；长度为 2 的好串：97 、78 、85 、 56 ；长度为 3 的好串：978 、785 、856 ；长度为 4 的好串：7856 ； 

总计 13 个好串。 

【评测用例规模与约定】 

本题中，n 表示字符串 s 的长度。 

对于 20% 的评测用例，1 ≤ n ≤ 5 ； 

对于 40% 的评测用例，1 ≤ n ≤ 20 ； 

对于 60% 的评测用例，1 ≤ n ≤ 100 ； 

对于 70% 的评测用例，1 ≤ n ≤ 10³ ； 

对于 80% 的评测用例，1 ≤ n ≤ 10⁴ ；

对于所有评测用例，1 ≤ n ≤ 10⁵，s 中只包含数字字符 0 ∼ 9 。