write-up-蓝桥杯2016省赛真题

蓝桥杯2016省赛真题

这两天又做了2016年的蓝桥杯题目，感觉难度比2017年简单一些，是正常的蓝桥杯题目难度，难度逐年降低（反序😋）。话不多说，下面开始逐题分析。

ps: 最近被win折磨的不行，动不动explorer.exe cpu占用80%+，体验极差，已经下定决心装黑苹果或者Ubuntu，如果成功可能会简单的记录一下。

真题分析

1. 网友年龄

题目

某君新认识一网友。当问及年龄时，他的网友说：“我的年龄是个2位数，我比儿子大27岁,如果把我的年龄的两位数字交换位置，刚好就是我儿子的年龄”请你计算：网友的年龄一共有多少种可能情况？提示：30岁就是其中一种可能哦.
请填写表示可能情况的种数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

分析

全是废话，就是枚举，没啥好说的

代码

ans = 0
for i in range(10, 100):
    a = i // 10
    b = i % 10
    s = b*10+a
    if i-s == 27:
        ans += 1
print(ans)

2. 生日蜡烛

题目

某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。现在算起来，他一共吹熄了236根蜡烛。请问，他从多少岁开始过生日party的？请填写他开始过生日party的年龄数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

分析

等差数列求和+枚举

代码

for x in range(1, 100):
    for n in range(1, 100):
        if n*x+n*(n-1)//2 == 236:
            print(x)

3. 方格填数

题目

方格填数
如下的10个格子
   +--+--+--+
   |  |  |  |
+--+--+--+--+
|  |  |  |  |
+--+--+--+--+
|  |  |  |
+--+--+--+
填入0~9的数字。要求：连续的两个数字不能相邻。（左右、上下、对角都算相邻）一共有多少种可能的填数方案？
请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

分析

本题其实就是一个全排列的问题。最开始做的时候最直观的想法就是构造一个二维数组，以每个点为起点开始填一遍（暴力枚举），但是最终做下来耗时较长。看了题解以后恍然大悟，这只不过是全排列的一种变形。我们只要对10个数进行全排列然后按序填入10个方格即可。然后根据方格位置固定关系check即可。

代码

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
ans = 0

def check():
    if(abs(a[0]-a[1])==1 or
        abs(a[0]-a[3])==1 or
        abs(a[0]-a[4])==1 or
        abs(a[0]-a[5])==1 or 

        abs(a[1]-a[2])==1 or
        abs(a[1]-a[4])==1 or 
        abs(a[1]-a[5])==1 or 
        abs(a[1]-a[6])==1 or 

        abs(a[2]-a[5])==1 or 
        abs(a[2]-a[6])==1 or 

        abs(a[3]-a[4])==1 or 
        abs(a[3]-a[7])==1 or 
        abs(a[3]-a[8])==1 or 

        abs(a[4]-a[5])==1 or 
        abs(a[4]-a[7])==1 or 
        abs(a[4]-a[8])==1 or 
        abs(a[4]-a[9])==1 or 

        abs(a[5]-a[6])==1 or 
        abs(a[5]-a[8])==1 or 
        abs(a[5]-a[9])==1 or 

        abs(a[6]-a[9])==1 or 

        abs(a[7]-a[8])==1 or

        abs(a[8]-a[9])==1):
        return False
    return True

def swap(x, y):
        t = a[i]
        a[i] = a[k]
        a[k] = t

def f(k):
    global ans
    if k == 10:
        if check():
            ans += 1
            return

    for i in range(k, 10):
        # 枚举
        swap(k, i)
        # 递归 选择下一位
        f(k+1)
        # 回溯
        swap(k, i)

if __name__ == "__main__":
    f(0)
    print(ans)

4. 快速排序

题目

原题目说的乱七八糟，其实就是实现快速排序算法。

分析

经典排序算法，不再分析

代码

def swap(a, x, y):
    t = a[x] 
    a[x] = a[y]
    a[y] = t

def partition(a, l, r):
    i = l
    j = r+1
    x = a[l]

    while True:
        i += 1
        while i < r and a[i] < x:
            i += 1
        j -= 1
        while a[j] > x and j >= i:
            j -= 1
        if i >= j:
            break
        swap(a, i, j)
    swap(a, l, j)
    return j

def quick_sort(a, l, r):
    if l < r:
        q = partition(a, l, r)
        quick_sort(a, l, q-1)
        quick_sort(a, q+1, r)

5. 消除尾一

题目

消除尾一
下面的代码把一个整数的二进制表示的最右边的连续的1全部变成0
如果最后一位是0，则原数字保持不变。
如果采用代码中的测试数据，应该输出：
00000000000000000000000001100111   00000000000000000000000001100000
00000000000000000000000000001100   00000000000000000000000000001100
请仔细阅读程序，填写划线部分缺少的代码。

分析

本题是代码填空题，主要是利用了按位运算的规律；核心为将原数+1后与原数做and操作即可。即 x&(x+1)。代码不再给出。

6. 寒假作业

题目

现在小学的数学题目也不是那么好玩的。看看这个寒假作业：
  □ + □ = □
  □ - □ = □
  □ × □ = □
  □ ÷ □ = □
(如果显示不出来，可以参见【图7-1.jpg】)每个方块代表1~13中的某一个数字，但不能重复。
比如：
 6 + 7 = 13
 9 - 8 = 1
 3 * 4 = 12
 10 / 2 = 5
以及：
 7 + 6 = 13
 9 - 8 = 1
 3 * 4 = 12
 10 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）你一共找到了多少种方案？

分析

本题其实也是一道全排列的问题，只不过是把各个数位之间的关系改了一下。只需要根据题目更改一下check即可。但是由于问题的规模比较大$（12!）$,所以需要一些提前剪枝的技巧来提高效率。

代码

a = [i for i in range(1, 14)]
ans = 0

def check():
    if a[0]+a[1] == a[2] and \
        a[3]-a[4] == a[5] and \
        a[6]*a[7] == a[8] and \
        a[9]//a[10] == a[11] and \
        a[9]%a[10] == 0:
        return True
    return False

def swap(x, y):
    global a
    t = a[x]
    a[x] = a[y]
    a[y] = t

def dfs(pos):
    global ans, a
    if pos == 13 and check():
        ans += 1
        return 

    for i in range(pos, 13):
        swap(i, pos)
        # 此处为提前剪枝
        if (pos == 2 and a[0]+a[1] != a[2]) or (pos == 5 and a[3]-a[4] != a[5]):
            dfs(pos+1)
        swap(i, pos)

if __name__ == "__main__":
    dfs(0)
    print(ans)

7. 剪邮票

题目

如【图1.jpg】, 有12张连在一起的12生肖的邮票。现在你要从中剪下5张来，要求必须是连着的。（仅仅连接一个角不算相连）比如，【图2.jpg】，【图3.jpg】中，粉红（紫）色所示部分就是合格的剪取。请你计算，一共有多少种不同的剪取方法。请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。

分析

本题还是一道全排列题目的变种，只不过是带有重复的全排列。将12个格子放在一维数组中，选中为1，未选中为0；然后再利用dfs检查连通性即可。

代码

ans = 0
a = [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
vis = [False]*12 # 用于全排列去重

def dfs(g, i, j): # 检查连通性
    g[i][j] = 0 # 该点被遍历
    if i - 1 >= 0 and g[i-1][j] == 1:
        dfs(g, i-1, j)
    if i + 1 <= 2 and g[i+1][j] == 1:
        dfs(g, i+1, j)
    if j - 1 >= 0 and g[i][j-1] == 1:
        dfs(g, i, j-1)
    if j + 1 <= 3 and g[i][j+1] == 1:
        dfs(g, i, j+1)

def check(path): # 检查该答案合法性
    # 将全排列结果还原到数组中 便于check
    g = [[0]*4 for _ in range(3)]
    for i in range(3):
        for j in range(4):
            if path(i*4+j)==1:
                g[i][j] = 1

    cnt = 0 # 连通子集个数
    for i in range(3):
        for j in range(4):
            if g[i][j] == 1: # 从存在点的地方开始搜索
                dfs(g, i, j)
                cnt += 1 # 搜索完成后个数加一
    return cnt == 1 # 如果只有一个连通集合，符合条件

def f(k, path):
    # k为a数组中的索引 path为记录已做的选择
    global ans
    if k == 12 and check(path): # 出口条件
        ans += 1
        return
    for i in range(12): # 枚举 全排列
        if i > 0 and a[i] == a[i-1] and not vis[i-1]: # 去重
            continue
          if not vis[i]: # 没有选取过 选取并遍历
            # 记录当前选择
            vis[i] = True 
            path[k] = a[i]

            f(k+1, path) # 继续选择

            vis[i] = False # 回溯

if __name__ == "__main__":
    path = [0]*12
    f(0, path)
    print(ans)

8. 四平方和

题目

四平方和定理，又称为拉格朗日定理：每个正整数都可以表示为至多4个正整数的平方和。如果把0包括进去，就正好可以表示为4个数的平方和。
比如：
5 = 0^2 + 0^2 + 1^2 + 2^2
7 = 1^2 + 1^2 + 1^2 + 2^2
（^符号表示乘方的意思）
对于一个给定的正整数，可能存在多种平方和的表示法。要求你对4个数排序：
0 <= a <= b <= c <= d
并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。程序输入为一个正整数N (N<5000000)要求输出4个非负整数，按从小到大排序，中间用空格分开
例如，输入：
5
则程序应该输出：
0 0 1 2
再例如，输入：
12
则程序应该输出：
0 2 2 2
再例如，输入：
773535
则程序应该输出：
1 1 267 838

分析

本题思路其实比较简单，暴力做法就是直接枚举。但是这样代码会超时，因此我们需要利用问题特性以及cache缓存来降低时间复杂度。在本问题中，设四个数字为a, b, c, d,总数量为N 他们满足如下关系： $a^2<= N/4, b^2<=N/3, c^2<=N/2, d^2<=N$

代码

import math
if __name__ == "__main__":
    N = int(input())
    cache = {} # cache 缓存数据 cache[c*c+d*d] = y: 平方和为c*c+d*d的c的最小值为y

    # 此处有一个小技巧 先计算c, d 便于构建缓存，同时降低复杂度到O(N^2)
    for c in range(N//2):
        d = c
        while d < N and c*c+d*d <= N:
            if c*c+d*d not in cache:
                cache[c*c+d*d] = c
            d += 1

    for a in range(N//4):
        b = a
        while b < N//2 and a*a+b*b<=N/2:
            if N-a*a-b*b in cache:
                c = cache[N-a*a-b*b]
                d = int(math.sqrt(N-a*a-b*b-c*c))
                print(a, b, c, d)
                break
            b += 1
        else:
            continue
        break

9. 密码脱落

题目

X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：
ABCBA
则程序应该输出：
0
再例如，输入：
ABECDCBABC
则程序应该输出：
3

分析

本题题目表述的比较花里胡哨，但是其实它只不过是利用了LCS来求解。但是这一层次比较难以想到，所以还是有一定难度的。如果用暴力法求解肯定只能获得一部分分数（超时）。

该问题是求镜像串，而镜像串的特点就是关于中心点对称，换句话说就是将原串反转后的得到的字符串与原串相同。现在的问题是原镜像串有一定的缺失，不满足镜像串的特性。我们可以这样处理：将缺失的串反转，然后和原串求其最长公共子序列，这样得到的串必定是原本不缺失的串的子序列。由于求的是最小数量，于是我们只需要将公共子序列根据给定的串补全即可；即用给定的缺失串的长度减去最长公共子序列的长度，即为答案。

代码

代码主要为LCS的dp解法，不再详细注释。

if __name__ == "__main__":
    s = input()
    n = len(s)
    re_s = s[::-1]
    dp = [[0]*(n+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, n+1):
            if s[i-1] == re_s[j-1]:
                dp[i][j] = dp[i-1][j-1]+1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return n - dp[-1][-1]

10. 最大比例

题目

X星球的某个大奖赛设了M级奖励。每个级别的奖金是一个正整数。并且，相邻的两个级别间的比例是个固定值。也就是说：所有级别的奖金数构成了一个等比数列。比如：16,24,36,54 其等比值为：3/2。现在，我们随机调查了一些获奖者的奖金数。请你据此推算可能的最大的等比值。输入格式：第一行为数字N(n<100)，表示接下的一行包含N个正整数。第二行N个正整数Xi(Xi<1 000 000 000 000)，用空格分开。每个整数表示调查到的某人的奖金数额
要求输出：一个形如A/B的分数，要求A、B互质。表示可能的最大比例系数。测试数据保证了输入格式正确，并且最大比例是存在的。
例如，输入：
3
1250 200 32
程序应该输出：
25/4
再例如，输入：
4
3125 32 32 200
程序应该输出：
5/2
再例如，输入：
3
549755813888 524288 2
程序应该输出：
4/1

分析

本题就是一个数学问题，主要是等比数列的性质的应用。看了题解以后，发现思路其实并没有很复杂，但是代码量比较大，暂时未做python实现，代码实现以后待补充。

2016省赛总结

2016年的省赛一共考察了三个全排列的题目，常见的全排列套路都进行了考察，从最基础的全排列，到全排列的优化到全排列的去除重复等都有考察，其余题目还是常规，前三题热身，代码填空消除尾一需要一定技巧，四平方和考察的是对大量枚举的优化，密码脱落可以说并不是考察LCS，而是考察对于问题的转化和平时的积累，最后一题则是蓝桥杯惯例的一道数学方面的问题了。整体来说难度适中，遇到一些很巧妙的题目时可以战略性跳过或者可以快速写出暴力解得到一部分分数。感觉全排列在这里出现的比较多了，考虑单独开一篇文章总结一下。