write-up 蓝桥杯2017省赛真题

蓝桥杯2017省赛真题

最近做了一下蓝桥杯2017年省赛的真题，越发让我感到自己水平低下🙃，看来上次三等奖名副其实。差不多一半的题目没有很好的思路，甚至有些题在看题解时又双触及到了知识盲区。对比前几年的情况，17年蓝桥杯感觉略有难度（暴力杯没错了），难度逐年上升。下面逐题分析。

真题分析

1. 迷宫

题目

X星球的一处迷宫游乐场建在某个小山坡上。它是由10x10相互连通的小房间组成的。房间的地板上写着一个很大的字母。我们假设玩家是面朝上坡的方向站立，则：
L表示走到左边的房间，
R表示走到右边的房间，
U表示走到上坡方向的房间，
D表示走到下坡方向的房间。
X星球的居民有点懒，不愿意费力思考。他们更喜欢玩运气类的游戏。这个游戏也是如此！开始的时候，直升机把100名玩家放入一个个小房间内。玩家一定要按照地上的字母移动。迷宫地图如下：
UDDLUULRUL
UURLLLRRRU
RRUURLDLRD
RUDDDDUUUU
URUDLLRRUU
DURLRLDLRL
ULLURLLRDU
RDLULLRDDD
UUDDUDUDLL
ULRDLUURRR
请你计算一下，最后，有多少玩家会走出迷宫?而不是在里边兜圈子。请提交该整数，表示走出迷宫的玩家数目，不要填写任何多余的内容。如果你还没明白游戏规则，可以参看一个简化的4x4迷宫的解说图：

分析

这是一个经典的dfs问题，没有什么太多的技巧，只需要对每个节点进行dfs搜索即可,同时用一个vis数组来记录遍历过的地方，避免重复。

代码

vis = [[False] * 10 for _ in range(10)]
maze = ['UDDLUULRUL',
        'UURLLLRRRU',
        'RRUURLDLRD',
        'RUDDDDUUUU',
        'URUDLLRRUU',
        'DURLRLDLRL',
        'ULLURLLRDU',
        'RDLULLRDDD',
        'UUDDUDUDLL',
        'ULRDLUURRR'
]

ans = 0

def dfs(x:int, y:int) -> int:
    if x > 9 or x < 0 or y > 9 or y < 0:
        return True
    if vis[x][y]:
        return False

    vis[x][y] = True
    c = maze[x][y]
    if c == 'U':
        return dfs(x-1, y)
    elif c == 'D':
        return dfs(i+1, j)
    elif c == 'L':
        return dfs(i, j-1)
    elif c == 'R':
        return dfs(i, j+1)
    else:
        return False

if __name__ == "__main__":
    global vis
    for i in range(10):
        for j in range(10):
            vis = [[False]*10 for _ in range(10)]
            if dfs(i, j):
                ans += 1
    print(ans)

题外话

一拿到这道题，我的第一想法就是dfs，也是一个很常见的dfs问题。但是为了降低时间复杂度，我突然想到了利用动态规划来解决这个问题（💩最近做多了有点上头），最后一顿分析+瞎写代码成功的未解决问题。仔细一想其实根本不是动态规划问题，并没有出现明显的递推关系。

2. 跳蚱蜢

题目

有9只盘子，排成1个圆圈。其中8只盘子内装着8只蚱蜢，有一个是空盘。我们把这些蚱蜢顺时针编号为 1~8每只蚱蜢都可以跳到相邻的空盘中，也可以再用点力，越过一个相邻的蚱蜢跳到空盘中。请你计算一下，如果要使得蚱蜢们的队形改为按照逆时针排列，并且保持空盘的位置不变（也就是1-8换位，2-7换位,...），至少要经过多少次跳跃？
注意：要求提交的是一个整数，请不要填写任何多余内容或说明文字。

分析

这道题是一个bfs的问题，乍一看，这个问题好像dfs也可以解决，但是由于求的是最小的跳跃次数，所以最终来说还是要用bfs来解决。将空白处记为0号点，我们每次都可以选择其相邻的左右各两位。如图，也就是0号可以和1， 2， 7， 8号互换位置。我们的初始状态记为“012345678”，目标状态记为“087654321”，只要有一个情况达到了目标状态，返回当前步数即可。

另外，因为题目给出的是一个圆环，也就意味着0和8是相邻的，这里只要用取余的技巧处理一下即可。

代码

start = '012345678'
target = '087654321'

class Node:
    def __init__(self, status, pos, depth):
        self.status = status # 当前节点状态
        self.pos = pos # 当前0所在的位置
        self.depth = depth # 当前节点深度，即步数

q = [] # 队列
vis = set() # 利用set判重
def addNei(status, depth, pos, new_pos): # 添加子节点
    # 交换status的pos位置和new_pos位置。 由于python中str类型为不可变类型，故处理略微麻烦
    p0 = status[pos]
    np = status[new_pos]
    new_status = status[:pos]+np+status[pos+1:]
    new_status = new_status[:new_pos]+p0+new_status[new_pos+1:]

    if new_status not in vis: # 若这个状态未出现过 判重
        vis.add(new_status) 
        q.append(Node(new_status, new_pos, level+1)) #队列中添加该节点

if __name__ == "__main__":
    q.append(Node(start, 0, 0)) # 初始节点
    while q:
        node = q.pop(0) 
        status = node.status
        pos = node.pos
        depth = node.depth

        if status == target: # 到达目标状态，输出即可
            print(depth)
            break

        vis.add(status) # 将这个状态添加到vis中去重
        for i in range(-2, 3): # 遍历四种情况
            if i == 0:
                continue
            new_pos = (pos + i+9)%9 # 利用取余技巧处理圆环 即循环数组
            addNei(status, depth+1, pos, new_pos) # 将改节点添加至搜索队列中

小结

这道题本事其实并不太困难，主要是要及时利用“最少步数”看出是用bfs进行搜索即可，另外代码中有几处小细节的处理需要注意即可。

3. 魔方状态

题目

二阶魔方就是只有2层的魔方，只由8个小块组成。小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
前面：橙色
右面：绿色
上面：黄色
左面：绿色
下面：橙色
后面：黄色
请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。请提交表示状态数的整数，不要填写任何多余内容或说明文字。

分析

本题的描述很简单，就是求魔方有多少种状态，一种很浓烈的dfs的味道。但是仔细一想其实问题其实还挺复杂。

魔方的变化方式总共只有三种方式，每种选择方式都对应着4个小面的变化：

1. 前面旋转
2. 上面旋转
3. 侧面旋转

4. 方块分割

题目

6x6的方格，沿着格子的边线剪开成两部分。要求这两部分的形状完全相同。如图4-1,4-2,4-3：就是可行的分割法。试计算：包括这3种分法在内，一共有多少种不同的分割方法。注意：旋转对称的属于同一种分割法。请提交该整数，不要填写任何多余的内容或说明文字。


分析

本题其实还是一道dfs的题目，只不过需要一定的技巧来构造。

仔细观察图片的分割线，我们可以发现所有分割线都要经过图片的中心，即分割线都是关于图片中心对称的。因此，我们只要构造一条经过图片中心的分割线，就一定是对称的，符合题意的。因此，本题的dfs出发点就是这个图的中心点。只要我们从中心点出发，那么就一定会经过中心点，这样相当于极大的缩小了解空间。然后，根据题意排除重复情况即可（最终情况/4即可）。

代码

dire = [[0,1], [0, -1], [1, 0], [-1, 0]]
vis = [[False]*7 for _ in range(7)] # 用于判重
ans = 0
def dfs(x, y):
    global ans, vis
    if x == 0 or x == 6 or y == 0 or y == 6: # 超出边界 即分割完成
        ans += 1 
        return
    if vis[x][y]: # 重复情况
        return

    # 将 (x, y)和其中心对称的点标记
    vis[x][y] = True 
    vis[6-x][6-y] = True

    # 遍历四个方向
    for d in dire:
        dfs(x+d[0], y+d[1])

    # 完成当前节点的遍历后，需要回溯，避免对其他情况的影响
    # 由于每一次调用结束都会回溯一次，相当于递归回溯，即消除了由此节点引起的全部影响
    vis[x][y] = False
    vis[6-x][6-y] = False

if __name__ == "__main__":
    dfs(3,3)
    print(ans//4) # 每旋转90°是一个对称的情况，所以要除以4

5. 字母组串

本题是一个代码填空题，较为简单，跳过

6.最大公共子串

同上，dp的模板代码填空题

7.正则问题

题目

考虑一种简单的正则表达式： 只由 x ( ) | 组成的正则表达式。 小明想求出这个正则表达式能接受的最长字符串的长度。例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是6。一个由x()|组成的正则表达式。输入长度不超过100，保证合法。这个正则表达式能接受的最长字符串的长度。
输入：
((xx|xxx)x|(x|xx))xx  
1
输出：
6 

分析

本题也是一道dfs的题目。仔细观察分析一下，题目的输入只有“（”， “）”， “x”， “|”这四种。总体上看，题目的答案等于括号外直接的‘x’数量+括号内的数量，遇到‘|”取两边的最大值即可。如何得到括号内的数量？只需要再次重复上述过程即可，很明显这是一个递归的过程。我们只要用一个全局的指针来遍历字符串，根据不同的符号来进行不同操作即可。

1. “（”

   当我们遇到“（”时，代表我们需要递归的处理括号内的情况；抽象的来说这里就相当于得到括号内的值。

2. “）”

   这种情况意味着当前“（”情况的结束，我们只需要返回当前括号内的值即可。

3. “x”

   这是最直接的情况，只需要计数并指针移动即可。

4. ”|“

   遇到”|“时，我们需要对”|“前的情况（”（“内）进行一次结算；为与”|“后的数量比较大小做准备；

下面看具体代码。

代码

s = ''　# 待处理字符串
pos = 0 # 全局指针
l = 0 # 总长度

def dfs(): # 递归模拟
    global pos

    tmp = 0 # 临时保存每一次结果，每个“|”重置一次， 便于比较两部分取最优
    ans = 0 # 最终结果
    while(pos < l): # 未到终点
        if s[pos] == "x": # 直接统计即可
            pos += 1
            tmp += 1

        if s[pos] == "(": # 需要递归处理 抽象为得到这个括号
            pos += 1
            tmp += dfs() # 暂存结果

        if s[pos] == ")": # 结束当前括号的情况 返回当前括号的最终结果
            pos += 1
            ans = max(ans, tmp) # 选取最优解
            return ans

        if s[pos] == "|": # 暂存当前结果 需要选取最优解 
            pos += 1
            ans = max(tmp, ans) # 取最优
            tmp = 0 # 重置
    return max(ans, tmp) # 如果没有遇到“）”， 直接返回结果

if __name__ == "__main__":
     s = '((xx|xxx)x|(x|xx))xx'
    l = len(s)
    print(dfs())

8. 包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100) 
输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，
输入：
2  
4  
5  
程序应该输出：
6 
再例如，
输入：
2  
4  
6   
程序应该输出：
INF
样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。  
对于样例2，所有奇数都凑不出来，所以有无限多个。 

分析

本题可以说是一道数学问题，如果没有相关的知识可能会很难做（我）。但是如果了解了相关知识，其实代码并不复杂。下面补充一下相关数学知识：

扩展欧几里得算法

已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式:

$ax+by=gcd(a,b)$

由定理可知，如果$gcd(a, b)=1$,那么就可以凑出任意包子数。即如果a,b互质的话就可以凑出任意的包子数了。到这里，这个问题就基本解决了。

代码

a = [0]*101 # 存储蒸笼数据
f = [False]*10000 # 类dp数组

def gcd(a, b): # gcd python中其实有内置函数
    if not b:
        return a
    return gcd(b, a%b)

if __name__ == "__main__":
    n = int(input())
    f[0] = True # base case 0当然可以凑出
    for i in range(1, n+1):
        a[i] = int(input()) # 读入蒸笼
        if i == 1: # 如果是第一个 公约数是自己
            g = a[i]
        else:
            g = gcd(a[i], g) # g是公约数
            for j in range(10000): # 每读入一个新的蒸笼，扫描一遍 更新可以凑出的数量
                if f[j] and j+a[i] < 10000: # 如果f[j]可以凑出，那么f[j+a[i]]一定可以凑出
                    f[j+a[i]] = True

    if g != 1:
        print("INF\n")
    else:
        ans = 0
        for i in range(10000):
            if f[i]:
                ans += 1
    print(ans)

9.分巧克力

题目

 儿童节那天有 K 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。小明一共有 N 块巧克力，其中第 i 块是 Hi x Wi 的方格组成的长方形。为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数  
2. 大小相同  
例如一块 6x5 的巧克力可以切出 6 块 2x2 的巧克力或者 2 块 3x3 的巧克力。当然小朋友们都希望得到的巧克力尽可能大，你能帮小 Hi 计算出最大的边长是多少么？
输入
第一行包含两个整数 N 和 K。(1 <= N, K <= 100000)  
以下 N 行每行包含两个整数 Hi 和 Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块 1x1 的巧克力。   
输出
输出切出的正方形巧克力最大可能的边长。
样例输入：
2 10  
6 5  
5 6  
样例输出：
2

分析

这道题直接的思路其实很简单，就直接暴力搜索就可以了。由于求最大边长，我们只要从高到低的顺序搜索即可。但是这样做了以后超时了。仔细一想，我们只需要在搜索巧克力大小时候使用二分法的技巧来处理即可大大降低时间复杂度。

代码

if __name__ == "__main__":
    h = [0] * 100000
    w = [0] * 100000
    tmp = input().split()
    n, k = int(tmp[0]), int(tmp[1])
    for i in range(n):
        tmp = input().split()
        h[i], w[i] = int(tmp[0]), int(tmp[1])
    r = 100001
    l = 1
    ans = 0
    while r>=l:
        mid = (r+l)//2
        cnt = 0
        for i in range(n):
            cnt += (h[i]//mid)*(w[i]//mid)
        if cnt > k:
            l = mid + 1
            ans = mid
        else:
            r = mid - 1
    print(ans)

10.油漆面积

题目

X星球的一批考古机器人正在一片废墟上考古。 该区域的地面坚硬如石、平整如镜。 管理人员为方便，建立了标准的直角坐标系。每个机器人都各有特长、身怀绝技。它们感兴趣的内容也不相同。 经过各种测量，每个机器人都会报告一个或多个矩形区域，作为优先考古的区域。矩形的表示格式为(x1,y1,x2,y2)，代表矩形的两个对角点坐标。为了醒目，总部要求对所有机器人选中的矩形区域涂黄色油漆。 小明并不需要当油漆工，只是他需要计算一下，一共要耗费多少油漆。其实这也不难，只要算出所有矩形覆盖的区域一共有多大面积就可以了。 注意，各个矩形间可能重叠。本题的输入为若干矩形，要求输出其覆盖的总面积。
输入格式：
第一行，一个整数n，表示有多少个矩形(1<=n<10000) 接下来的n行，每行有4个整数x1 y1 x2 y2，空格分开，表示矩形的两个对角顶点坐标。 (0<= x1,y1,x2,y2 <=10000)
输出格式：
一行一个整数，表示矩形覆盖的总面积。
输入：
3
1 5 10 10
3 1 20 20
2 7 15 17
输出：
340
输入：
3
5 2 10 6
2 7 12 10
8 1 15 15
输出：
128

分析

本题是一道线段树+扫描线的很经典的题目，代码较为复杂，但是也有一个简便但是低效的做法就是用一个数组将所有的区域都表示出来，然后每输入一个区域就将该区域所有点标记上，最后统计所有点数即可。由于内容较多，因此会单独出来分析。

2017省赛总结

2017年分体考点如下：

1. 迷宫

   暴力dfs

2. 跳蚱蜢

   bfs

3. 魔方状态

   模拟过程+判重

4. 方块分割

   图形 dfs 模拟过程

5. 字母组串

   递归

6. 最大公共子串

   dp

7. 正则问题

   dfs 模拟过程 抽象

8. 包子凑数

   数学问题 扩展欧几里得

9. 分巧克力

   二分搜索

10. 油漆面积

    线段树+扫描线

2017年的省赛题目整体做下来其实感觉稍微有些难度，没有了往年的前两题的送分题，后面也越来越重视对一些特定算法，数学知识以及代码能力的考查，但是其实大部分题还是用的是暴力求解的思路。从这些题目中也能学到很多经验，比如对于一些题目可能就没有什么特殊的解法，只需要模拟出题目描述的过程就可以；还有一些题目考察的是一些数学问题，这方面需要学习一下；另外遇到一些难题暂时想不出解答时，可以直接用暴力解法获得一部分分数。