write-up-蓝桥杯2020省赛一模

write-up 蓝桥杯2020省赛第一次模拟

这次模拟赛题目比较常规，难度感觉不如前几年的省赛真题，前几题直接送分，只有后面三题是有一定难度。前六题比较无脑，就直接跳过了，从第七题开始分析。

第七题 音节判断

题目

【问题描述】
小明对类似于 hello 这种单词非常感兴趣，这种单词可以正好分为四段，第一段由一个或多个辅音字母组成，第二段由一个或多个元音字母组成，第三段由一个或多个辅音字母组成，第四段由一个或多个元音字母组成。
给定一个单词，请判断这个单词是否也是这种单词，如果是请输出yes，否则请输出no。
元音字母包括 a, e, i, o, u，共五个，其他均为辅音字母。
【输入格式】
输入一行，包含一个单词，单词中只包含小写英文字母。
【输出格式】
输出答案，或者为yes，或者为no。
【样例输入】
lanqiao
【样例输出】
yes
【样例输入】
world
【样例输出】
no
【评测用例规模与约定】
对于所有评测用例，单词中的字母个数不超过100。

分析

一开始拿到这个题想到的就是暴力枚举，直接搜索。看到题解后，发现有更加巧妙的方法：根据题目要求，如果将元音映射为1，辅音为0的话，那么符合条件的序列必然是“0..01..10..01..1”这样的。可以发现，这序列的特点就是01交替出现的情况只有三次。可以证明，只要不符合这个条件，不管多一次还是少一次，那么一定不符合题意。因此，我们只要在O（N）时间内判断这个情况就行。

代码

if __name__ == "__main__":
    word = input()
    l = [int(i in 'aeiou') for i in word]
    if l[0] == 1 or l[-1] == 0:
        print('no')
        exit()
    cnt = 0
    for i in range(1, len(word)):
        if l[i]+l[i-1] == 1:
            cnt += 1
    print('yes') if cnt == 3 else print('no')

这道题目其实也还算简单，因为题目指明了其数据量少于100，而一般来说，只要运算次数少于$10^8$，基本都可以在1s内解决，这个可以根据时间复杂度估算一下。在题解中，大量使用了生成器，简化了代码，不知道是否对性能有影响。另外代码中使用了exit函数退出程序，这个用法类似于C++ 中的return 0，但是在python的主函数中，无法通过return结束主进程，只能通过这种方式结束。另外，题解还有一种解法是我万万没有想到的，直接用re库匹配解题。。看来python库还有待开发。下面附上代码。

import re
if __name__ == "__main__":
    word = input().strip()
    match = re.match('[^aeiou]+[aeiou]+[^aeiou]+[aeiou]+', word)
    print('no') if match == None or match.end() != len(word)

第八题 长草

题目

小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
请告诉小明，k 个月后空地上哪些地方有草。
【输入格式】
输入的第一行包含两个整数 n, m。
接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
接下来包含一个整数 k。
【输出格式】
输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
【样例输入】
4 5
.g...
.....
..g..
.....
2
【样例输出】
gggg.
gggg.
ggggg
.ggg.
【评测用例规模与约定】
对于 30% 的评测用例，2 <= n, m <= 20。
对于 70% 的评测用例，2 <= n, m <= 100。
对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。

分析

这个题其实已经很经典了，在leetcode中也有这样的题目，其实就是bfs的一种变形，就是一种多源bfs搜索。一般的bfs只有一个起始原点，多源bfs就是将多个起始原点看作是一个超级原点，然后再进行扩散即可。大体过程和一般的bfs差异不大，也算是一个模版题。

代码

if __name__ == "__main__":
    tmp = input().split()
    n, m = int(tmp[0]), int(tmp[1])
    g = []
    for i in range(n):
        g.append(list(input()))
    k = int(input())
    month = 0
    q = []
    for i in range(n):
        for j in range(m):
            if g[i][j] == 'g':
                q.append((i, j))
    while q and month < k:
        new_q = q[:]
        q = []
        while new_q:
            i, j = new_q.pop(0)
            for d in dire:
                new_x = i+d[0]
                new_y = j+d[1]
                if new_x >= 0 and new_x < n and new_y >= 0 and new_y < m and \                        g[new_x][new_y] == '.':
                    g[new_x][new_y] = 'g'
                    q.append((new_x, new_y))
        month += 1
    for r in g:
        print(''.join(r))

第九题 序列计数

题目

【问题描述】
小明想知道，满足以下条件的正整数序列的数量：
1. 第一项为 n；
2. 第二项不超过 n；
3. 从第三项开始，每一项小于前两项的差的绝对值。
请计算，对于给定的 n，有多少种满足条件的序列。
【输入格式】
输入一行包含一个整数 n。
【输出格式】
输出一个整数，表示答案。答案可能很大，请输出答案除以10000的余数。
【样例输入】
4
【样例输出】
7
【样例说明】
以下是满足条件的序列：
4 1
4 1 1
4 1 2
4 2
4 2 1
4 3
4 4
【评测用例规模与约定】
对于 20% 的评测用例，1 <= n <= 5；
对于 50% 的评测用例，1 <= n <= 10；
对于 80% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 1000。

分析

刚拿到这道题，没有什么特别好的思路，就想着用暴力法来测一测，但是仔细考虑了一下，如果用暴力法枚举每种情况的话，时间复杂度是指数级的，肯定不可行。而且测评用例给的是1000个，也就是说最多可以用$O（n^2）$的算法来解决这个问题。看了一下题解，用的备忘录（dp）的方法来解决这个问题。memo数组的定义是 memo[pre][cur], 表示上一个数是pre时，从1...cur的合法序列数量。因此，递推关系为

memo[pre][cur] = (1+dfs(pre, cur-1)+dfs(cur, abs(pre-cur)-1))

代码

import sys
MOD = 10000
memo = [[0]*1001 for _ in range(1001)]
sys.Setrecursionlimit(2000) # 修改递归层数限制 其实改为dp方式即可

def dfs(pre, cur):
    if cur <= 0:
        return 0
    if memo[pre][cur]:
        return memp[pre][cur]
    memo[pre][cur] = (1+dfs(pre, cur-1)+dfs(cur, abs(pre-cur)-1))%MOD
    return memo[pre][cur]

if __name__ == "__main__":
    N = int(input().strip())
    print(dfs(N, N))

第十题 节目晚会单

题目

【问题描述】
小明要组织一台晚会，总共准备了 n 个节目。然后晚会的时间有限，他只能最终选择其中的 m 个节目。
这 n 个节目是按照小明设想的顺序给定的，顺序不能改变。
小明发现，观众对于晚会的喜欢程度与前几个节目的好看程度有非常大的关系，他希望选出的第一个节目尽可能好看，在此前提下希望第二个节目尽可能好看，依次类推。
小明给每个节目定义了一个好看值，请你帮助小明选择出 m 个节目，满足他的要求。
【输入格式】
输入的第一行包含两个整数 n, m ，表示节目的数量和要选择的数量。
第二行包含 n 个整数，依次为每个节目的好看值。
【输出格式】
输出一行包含 m 个整数，为选出的节目的好看值。
【样例输入】
5 3
3 1 2 5 4
【样例输出】
3 5 4
【样例说明】
选择了第1, 4, 5个节目。
【评测用例规模与约定】
对于 30% 的评测用例，1 <= n <= 20；
对于 60% 的评测用例，1 <= n <= 100；
对于所有评测用例，1 <= n <= 100000，0 <= 节目的好看值 <= 100000。

分析

这个题具有一定的误导性，第一次读题以为就两次排序就完事了，一看测试用例也符合，但是仔细一想，毕竟是最后一题，不太可能这么简单。仔细读题，发现题目要求了顺序不变，并且节目是尽可能好看，而不是最好看。因此，应该是区间范围内的最大值。那这个区间范围怎么选取？这样考虑问题：设节目为数组s[n]如果我们在前面尽量选择好看的节目，假设选择了一个并且位置稍微靠前的节目s[i]，那么为了凑齐m个节目，我们必须再从后面选取m-1个节目出来， 即选择s[n-m+1:]。整理一下思路，我们选择的过程就是对于第1个节目，我们选择的范围就是s[0:n-m+1], 若选择出来的节目为i，第二个节目就是s[i+1: n-m+1]这个区间中进行选择，直到剩下的节目必须全选以凑够数量。这里就涉及到了一个多次区间查询的问题，可以用往期分析过的线段树做到$O(log_2^n)$复杂度的查询，这里用另一种思路，使用ST矩阵来做区间查询。

ST算法的本质其实是动态规划， 对于给定的序列，提前构建好dp数组，在查询时的时间复杂度为$O(1)$,而构建过程的时间复杂度是$O(nlog_2^N)$（这个思想类似于kmp算法，离线处理，在线查询）。

ST 算法的离线预处理过程非常巧妙，对于给定的序列a[n], ST算法这样定义DP数组：dp[i][j]表示区间a[i:i+2**j]的最值。比如对于dp[0][2]，其表示区间范围是a[0: 4]。ST算法的状态转移思想是：对于区间dp[i][j]，首先将其分为两份，即dp[i][j-1], dp[i+2**(j-1)][j-1]，然后取这两者的最值即可。 由于这样特殊的定义，因此在查询一个区间的时候，也需要将区间按照2的次方进行分割。例如：对于区间a[i: j]，首先要将j-i取对数k，然后求dp[i][k], dp[j-2**k][k]的最值即可。

代码

MAX_N = 100010 # dp数组的最大范围
MAX_POW = 20 # 2的最大的次方数
N, M = 0, 0

st = [[0]*MAX_POW for _ in range(MAX_N)] # dp数组
log = [0 for _ in range(MAX_N)] # 提前计算好log值 减小时间复杂度

def init_log():
    for i in range(2, N+1):
        log[i] = log[i//2]+1

def init_st(data): # dp过程
    for i in range(N):
        st[i][0] = i # bast case 区间[i:i+1]的最值就是i本身
    for j in range(1, log[N]): # 开始填表 遍历顺序是从左到右，从上到下
        for i in range(N-(2**(j-1))):  
            # 由于下面需要访问i+(2**(j-1))，所以范围是N-(2(j-1)), 实际上是把0到N都遍历了的。
            idx1, idx2 = st[i][j-1], st[i+(2**(j-1))][j-1] # 先取出下表
            st[i][j] = idx1 if data[idx1] >= data[idx2] else idx2 # 根据题意 取最大值

def query(data, l, r):
    length = l - r + 1
    k = log[length]
    idx1, idx2 = st[l][k], st[r-2**(k)+1][k]
    return idx1 if data[idx1] >= data[idx2] else idx2

if __name__ == "__main__":
    N, M = [int(x) for x in input().strip().split()]
    data = [int(x) for x in input().strip().split()]
    init_log()
    init_st(data)
    pos_max, pos_1, pos_2 = 0, 0, N-M # 初始化查询范围 有点类似滑动窗口的意思
    while pos_1 < pos_2 < N:
        pos_max = query(data, pos1, pos2) # 当前范围内的最大值位置
        print(data[pos_max], end=' ')
        pos_1, pos_2 = pos_max+1, pos_2+1 
        # 左端点从最大值下一个开始，右端点+1 这里可以将左右端点看成一个区间 也可以将右端点到末尾看        # 成一个区间 右端点控制的是这一区间的长度

    while pos_2 != N: # 节目没有选慢 剩下的就必须全选
        print(data[pos_2], end=' ')
        pos_2 += 1
    print()

小结

这一次的省赛模拟题感觉难度没有往年真题难，好像去年的模拟题也是这样一个难度的，但是还是学到了一些东西。