第16届 蓝桥杯C/C++ ?组 G 题：好串

引言

虽然这次我没有报名蓝桥杯，不过却报名了本校蓝桥杯考点的志愿者监考（毕竟有5个志愿时长和100块的补贴，还是不错的）。

这道题是某位选手提前交卷后我出于无聊在他考试用的电脑上看考题看到的。

因为这道题的题目在互联网有别的含义，所以对这个印象比较深，考试结束后也一直在想。

题目全凭记忆，不一定和本来的考题相同，不过还是能做的，锻炼下逻辑思维。

题目

给定一个数组串，判断其字串的是否为好串的数量

子串是指：

对于一个数组串，有元素从 $a_1$ 到 $a_n$，都是0~9之间的整数，那么从 $a_l$ 到 $a_r$ 的连续的元素组成的字符串，称为一个子串。

如果一个子串满足以下条件，则称为好串：

这个数组串可以被拆分为两个连续增的序列或者只有一个数字，即为好串

其中连续增的序列被定义为：数组中的任意两个相邻的元素，后一个元素比前一个元素要么大1，要么等于前一个元素。

思路

枚举

首先最容易想到的思路就是枚举所有可能的串，然后判断是否是好串。

具体怎么判断一个串是否是好串先不说，先假设有一个函数叫做is_good_arr(arr)，它返回True表示s是好串，返回False表示s不是好串。这个函数最快也就是 $O(n)$ 的时间复杂度

那么我们可以枚举所有可能的串，然后判断是否是好串。

一个数组串，一共有 $\frac{n(n+1)}{2} 个字串组合$

那么直接遍历的方法就是 $O(n^3)$ 的时间复杂度。先实现一下。

代码实现

先实现判断是否是好串的函数吧。

按照最直接的想法，就是先将数组中连续增的数字先拿出来组成一个序列，再看剩下的数字是否能否组成一个连续增序列。如果不行，就看能不能在不破坏第一个连续增序列的前提下，从第一个序列中拿取数字，组成第二个连续增序列。如果不行，那就应该不是好串。

python复制
def is_good_arr(arr):
    raise NotImplementedError

is_good_arr([5, 5, 4, 5, 6, 7, 6]) # True

is_good_arr([1, 2, 2, 2, 1]) # True
is_good_arr([1, 0, 0, 3, 1, 1, 1, 3, 2, 4]) # False
is_good_arr([5, 5, 4, 5, 6, 7, 6]) # True

思路续

失败了，上面的第二个例子是反例，说明这种思路是错的

既然想不到办法直接判断是否是好串，尝试使用分治的思想。

假设一个数组串 $a_0,a_2,...,a_n$ 可以表示为 Arr(n)

如果 Arr(n) 不是好串，容易知道 Arr(n+1) 也一定不是好串。<br>
同样的，如果 Arr(n+1) 是好串，那么 Arr(n) 就一定是好串。 — 结论①

那么就差当 Arr(n) 是好串时， 如何判断 Arr(n+1) 是否是好串。

---

从最基本的思路出发，既然我们已经知道了 Arr(n) 是好串，那么其一定是由某两个连续增的序列 A(l) 和 B(m) 组成，l + m = n。

并且 Arr(n)[-1]（最后一个元素）一定是属于某一个序列的，假设其属于 A(l)，即 Arr(n)[-1] = A(l)[-1]

然后，如果我们要判断 Arr(n+1) 是否是好串，只需要判断 Arr(n+1)[-1] 是否可以接续到 A(l) 或者 B(m) 上，如果可以，则 Arr(n+1) 就是好串。

即，只需要判断 Arr(n+1)[-1] 是否与 A(l)[-1] 或者 B(m)[-1]连续增。

虽然我们已经可以确定 A(l)[-1] 就是 Arr(n)[-1]，但是我们仍然不知道 B(m)[-1] 在哪里。

那么问题的关键就是确定 B(m)[-1] 可能的取值是什么。

---

要找到 B(m)[-1]，就需要我们从其的特征出发。

B(m)[-1]，也就是 B(m) 序列的最后一个元素，也就意味着，在 Arr(n) 中，在 B(m)[-1] 之后的元素均不属于 B(m) 序列。

又因为 Arr(n) 的元素均属于 A(l) 序列或者 B(m) 序列，所以 B(m)[-1] 之后的元素，必然属于 A(l) 序列。

又由 A(l) 是连续增的序列

所以 B(m)[-1] 之后的元素，必然是连续的。 — 结论②

---

有了这个结论，我们就可以自然得到一个猜想：

从 Arr(n) 倒序划分出一个连续的序列 C(k)，直到不能再继续往前划分 <br>
在 C(k) 序列之前第一个在 Arr(n)中的元素，可以作为某种划分得到的 B(m) 的最后一个元素，称为 bl

显然这个猜想是满足上面得到的结论的，因为假设猜想成立，也就是说在 Arr(n) 中 bl 之后的元素组成的就是 C(k) 序列，而 C(k) 序列被定义为连续的

并且可以确定 bl 与 C(k)[0] 不连续 — 结论③

但是新的问题又来了，Arr(n) 显然有可能可以分为由多种不同的 A(l) 和 B(m) 组成的序列

在我们令 Arr(n)[-1] 属于 A(l) 序列的情况下，虽然我们可以确定 A(l)[-1] 就是 Arr(n)[-1]，但是我们仍然无法确定 B(m)[-1] 有多少种可能的取值。

目前我们只能通过猜想提到的方法，确定 B(m)[-1] 的其中一种可能的取值是 bl

所以我们要想办法进一步缩小 B(m)[-1] 可能的取值范围

---

先令按照猜想划分得到的 B(m)[-1] 为 bl

由 结论③，得到 bl 与 C(k)[0] 之间不连续

又由 结论②，得到 在 bl 之前的 Arr(n) 种的元素，不可能是某种划分得到的 B(m)[-1]

这样就一口气将 B(m)[-1] 的可能取值范围缩小到了 {bl} $\cup$ C(k)

再来看 C(k) 中有哪些元素可以作为 B(m)[-1] 的候选

---

情况一 首先假设 bl 属于 B(m)

那么在 C(k) 中找哪些元素可以作为 B(m)[-1] 的候选实际上就是在 C(k) 中找可以接续到 bl 中的元素，同时不能破坏剩下的元素的连续性。那么这些被找到的元素都可能是 B(m)[-1]

情况二 然后假设 bl 属于 A(l)

此时 C(k)[0] 就属于 B(m)

因为 C(k)[-1] 是定义为属于 A(l)， 又因为 A(l) 是连续增序列

所以这种假设成立需要能够从 C(k) 中找到可以接续到 bl 中的元素，并且要能一直接续到 C(k)[-1]，同时不能破坏剩下的元素的连续性，并且要尽量少拿。。。

后面思路不清晰，感觉自己证明不清楚了，总之，如图所示：

所以，结论是：

B(m)[-1] 的可能的值就是在 C(k) 中从 bl 开始重复（指个数大于等于2）并且连续的元素。

写代码实现吧

代码实现（关于判断好串）

python复制
# 判断两个数字是否连续增
def is_continuous(num1, num2):
    return num1 == num2 or num1 + 1 == num2


# 将一个连续增序列转化为用各个数字(0~9)的数目表示
def count_seq(seq):
    count = [0] * 10
    for num in seq:
        count[num] += 1
    return count


# 输入的arr是好串，如果在添加了某个数字后，仍然是好串，则返回True，否则返回False。
def is_still_good_by_adding(arr, added_num):
    # 如果可以加到最后，则是好串
    if is_continuous(arr[-1], added_num):
        return True

    # 倒序找到连续增的序列
    last = arr[-1]
    c_seq = [last]
    b_last = None
    for i in range(len(arr)-2, -1, -1):
        num = arr[i]
        # 如果连续增
        if is_continuous(num, last):
            c_seq.append(num)
            last = num
        else:
            b_last = num
            break
    c_seq.reverse()

    # 如果b_last是None，说明arr就是一个连续增序列，则是好串
    if b_last is None:
        return True

    # 找到在c_seq中的从 b_last 开始的重复连续序列
    c_seq_count = count_seq(c_seq)
    c_seq_count = [i - 1 if i > 0 else 0 for i in c_seq_count]

    possible_b_last = []

    for i in range(b_last, len(c_seq_count)):
        possible_b_last.append(i)
        if c_seq_count[i] == 0:
            break

    # 遍历所有可能的b_last，判断是否可以加到最后
    for b_last in possible_b_last:
        if is_continuous(b_last, added_num):
            return True

    return False


def is_good_arr(arr):
    # 如果是单个数字，则是好串
    if len(arr) == 1:
        return True
    # 如果子序列不是好串，则不是好串
    if not is_good_arr(arr[:-1]):
        return False

    # 如果子序列是好串，则判断加上最后一个数字是否仍然是好串
    return is_still_good_by_adding(arr[:-1], arr[-1])

print(is_good_arr([5, 5, 4, 5, 6, 7, 6])) # True

print(is_good_arr([1, 2, 2, 2, 1, 1, 1, 1, 2, 3])) # True

print(is_good_arr([1, 0, 0, 3, 1, 1, 1, 3, 2, 4])) # False

print(is_good_arr([4, 1, 2, 3, 5, 5, 6, 6, 7, 8, 8])) # True

plaintext复制
    True
    True
    False
    True

思路（关于判断数组串字串中好串的个数的部分）

接下来回到正题

既然已经知道了怎么判断好串了，这个问题就变得十分简单。

先说下最直接的枚举方法，也就是枚举所有字串的组合，然后判断是否是好串。

但是这种方法明显效率不高，因为在判断好串的时候我们已经使用了分治的思想，也就是说这个问题有重叠子问题性质。

这个性质的根源在于有这个结论：子序列不是好串，那么父序列一定不是好串。

那么对于从 $a_l$ 到 $a_r$ 这样的字串，用二维矩阵m的m[l][r]表示其是否是好串，如果是为1，否则为0。

那么我们可以用动态规划的方法来求解这个问题。

1. 首先初始化矩阵m，当 $l=r$ 时，m[l][r]为1，表示长度为1的字串都是好串。
2. 然后有以下递推关系：
   • if m[i][j-1] = 0，m[i][j] = 0
   • if m[i][j-1] = 1，if m[i+1][j] = 0，m[i][j] = 0
   • if m[i][j-1] = 1，if m[i+1][j] = 1，m[i][j] = is_still_good_by_adding(arr[i:j], arr[j])

从左下到右上，逐个填充矩阵m。

代码实现

python复制
from line_profiler import profile

枚举法

python复制
@profile
def count_of_good_arr_in_subarr(arr):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i, n):
            subarr = arr[i:j+1]
            if is_good_arr(subarr):
                count += 1
    return count

print(count_of_good_arr_in_subarr([1]))
print(count_of_good_arr_in_subarr([5, 7]))
print(count_of_good_arr_in_subarr([7, 5]))
print(count_of_good_arr_in_subarr([1, 3, 2]))
print(count_of_good_arr_in_subarr([1, 3, 5]))

plaintext复制
    1
    3
    3
    6
    5

动态规划

python复制
@profile
def count_of_good_arr_in_subarr_by_dp(arr):
    n = len(arr)
    m = [[1 if l == r else 0 for l in range(n)] for r in range(n)]

    for i in range(n-2, -1, -1):
        for j in range(i+1, n):
            if m[i][j-1] == 0:
                m[i][j] = 0
            else:
                if m[i+1][j] == 0:
                    m[i][j] = 0
                else:
                    m[i][j] = int(is_still_good_by_adding(arr[i:j], arr[j]))
  
    return sum([sum(row) for row in m])

print(count_of_good_arr_in_subarr_by_dp([1]))
print(count_of_good_arr_in_subarr_by_dp([5, 7]))
print(count_of_good_arr_in_subarr_by_dp([7, 5]))
print(count_of_good_arr_in_subarr_by_dp([1, 3, 2]))
print(count_of_good_arr_in_subarr_by_dp([1, 3, 5]))

plaintext复制
    1
    3
    3
    6
    5

速度对比

python复制
import random
def test(l):
    arr = [random.randint(0, 9) for _ in range(l)]

    count_of_good_arr_in_subarr(arr)
    count_of_good_arr_in_subarr_by_dp(arr)

python复制
%reload_ext line_profiler
%lprun -f test test(1)

plaintext复制
    Timer unit: 1e-07 s    Total time: 2.78e-05 s
    File: C:\Users\18499\AppData\Local\Temp\ipykernel_9800\3995133507.py
    Function: test at line 2    Line #      Hits         Time  Per Hit   % Time  Line Contents
    ==============================================================
         2                                           def test(l):
         3         1        134.0    134.0     48.2      arr = [random.randint(0, 9) for _ in range(l)]
         4
         5         1         58.0     58.0     20.9      count_of_good_arr_in_subarr(arr)
         6         1         86.0     86.0     30.9      count_of_good_arr_in_subarr_by_dp(arr)

python复制
%reload_ext line_profiler
%lprun -f test test(10)

plaintext复制
    Timer unit: 1e-07 s    Total time: 0.0017428 s
    File: C:\Users\18499\AppData\Local\Temp\ipykernel_9800\3995133507.py
    Function: test at line 2    Line #      Hits         Time  Per Hit   % Time  Line Contents
    ==============================================================
         2                                           def test(l):
         3         1        859.0    859.0      4.9      arr = [random.randint(0, 9) for _ in range(l)]
         4
         5         1      12630.0  12630.0     72.5      count_of_good_arr_in_subarr(arr)
         6         1       3939.0   3939.0     22.6      count_of_good_arr_in_subarr_by_dp(arr)

python复制
%reload_ext line_profiler
%lprun -f test test(100)

plaintext复制
    Timer unit: 1e-07 s    Total time: 0.253917 s
    File: C:\Users\18499\AppData\Local\Temp\ipykernel_9800\3995133507.py
    Function: test at line 2    Line #      Hits         Time  Per Hit   % Time  Line Contents
    ==============================================================
         2                                           def test(l):
         3         1       4026.0   4026.0      0.2      arr = [random.randint(0, 9) for _ in range(l)]
         4
         5         1    2478469.0    2e+06     97.6      count_of_good_arr_in_subarr(arr)
         6         1      56676.0  56676.0      2.2      count_of_good_arr_in_subarr_by_dp(arr)

虽然是同一个时间复杂度（最坏情况），但是速度碾压，大概率是因为越长的随机数组串，是好串的概率越低