第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组题目试做（上）

因为要考蓝桥省赛了，还是要准备一下的，虽然实力很一般，但总得挣扎一下。

拼正方形

题目链接：拼正方形

偷鸡解法

这是蓝桥杯那一届的算是签到题，只需要输出结果，所以我觉得我们其实没有那么大的必要去一定要解出这道题。
我们最后要输出的是边长，我们就先算一下所有的方块数：

7385137888721 * 4 + 10470245 * 1 = 29,540,562,025,129
再开根号是5,435,123

我们就去试它对不对就好，不对再一点点变小，肯定是在这附近的，花不了多少时间就能猜出来。

题目分析

我们这里尝试一下正经去解一下这个题。我们最后要求出最大边长，边长主要分为两种 —— 奇数 和 偶数。
奇数毫无疑问就肯定会有奇数层的 1 x 1 的方块。
偶数就没办法判断了。
所以我的想法就是去遍历，优先 2 x 2 的方块去填充，然后判断剩下的不能填充的值和 1 x 1 方块的大小。

按照这么个想法我们来写一下代码吧~

import os
import sys

# 请在此输入您的代码
t_t = 7385137888721 # two - two
o_o = 10470245 #one - one

n_2 = t_t * 4 + o_o * 1
n = int(pow(n_2, 0.5))

for i in range(n, 0, -1):
    if i % 2 == 0: # 偶数可以直接除 2 
        if i ** 2 <= t_t * 4 + o_o: #偶数的话就可以随便放，不用考虑2 x 2的不能放
            print(i)
            break
    else: # 奇数需要先 -1变成偶数
        t = i - 1
        if t ** 2 > t_t * 4:
            x = t ** 2 - t_t * 4 #放完2 x 2方块之后还需要多少1 x 1的方块
        else:
            x = 0
        if i ** 2 - t ** 2 + x < o_o: #只能放1 x 1的数量加上2 x 2放完不够的数量
            print(i)
            break

我是觉得这个思路是合理的，如果大佬们觉得有漏洞可以在评论区讨论一下。
我看了其它大佬的一些博客，都是用的二分去对 n 进行一个锁值，但我觉得这个数肯定和那个开完根号后的数很接近，所以我觉得不需要用二分去算。

劲舞团

题目链接：劲舞团

思路分析

其实我感觉这一题比上一题简单一点，就是两个判断这题，然后累加，取最大值。
虽然但是，我有一点不理解的就是为什么计数的 cnt 要从 1 开始。

按照我的理解，当前位如果不符合就该从0开始，直到遇到下一个符合的数，才会变成 1 有路过的大佬可以帮忙解答一下吗？？

OK，对于这道题，我们总共是做三件事：

1. 读取log，如果是比赛应该就是分次读取，大概就是

a , b , h = map(int, input().split())

2. 然后判断敲击对不对，时间超不超1000ms

x[i][0] != x[i][2] or int(x[i][4:]) - int(x[i-1][4:]) > 1000

3.存下最大值

Max = max(Max, cnt)

完整版

x = open('log.txt', 'r').read().split('\n') #测试我就把数据存到txt文件里了，这句是读取文件

cnt = Max = 0
if x[0][0] == x[0][2]:
    cnt = 1
for i in range(1, len(x)):
    if x[i][0] != x[i][2] or int(x[i][4:]) - int(x[i-1][4:]) > 1000:
        Max = max(Max, cnt)
        cnt = 1
        print(Max)
    else:
        cnt += 1
print(Max)

数字诗意

题目链接：数字诗意

思路分析（错掉了）

看到题目我最直接的想法就是遍历，从1 到 a所有数一直遍历，然后再一个循环去判断能不能有一个连续的数相加等于 a 。

但是我们看到下面的测评规模，就可以排除遍历的想法了，按照上面的想法我们的时间复杂度是 O（n²），必然是会超时间的。

那么我们就该去想连续数能不能直接用一个公式去表示，这样就省下第二层循环的时间，也就是 O（n）这样大概是能够符合时间要求的。

然后我们再分析一下它有什么关系：

# x x+1 x+2 x+3 ... x+n
# (x + x + n) * n / 2

大概是这么回事，那么我们只需要遍历 n 就可以得出这个数是不是有诗意的了。

OK，看到题目之后的分析大概是这样，我们先来试试。

代码是这样的：

n = int(input())
lst = list(map(int, input().split()))
cnt = 0 # 用来记录要删除的个数
for i in range(n):
    x = lst[i]
    j = 2
    while j < x:
        y = (x * 2 / j - j) / 2
        if y % 1 == 0:
            break
        j += 1
    else:
        cnt += 1
        print(x)
print(cnt)

# x x+1 x+2 x+3 ... x+n
# (x + x + n) * n / 2

思路再分析（对的）

结果是错掉了，说明我一开始的思路不对，这下就得重新想一下了，我先用遍历的方法把前面的一些数罗列出来。
测试代码如下：

for i in range(100):
    for j in range(1, i):
        flag = 1
        t = i
        for k in range(j, i):
            t -= k
            if t == 0 and k - j >= 1:
                flag = 0
                break
        if flag == 0:
            print(i, end = ' ')
            break

在一百以内是诗意的数有：

3 5 6 7 9 10 11 12 13 14 15 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

首先我们观察到的是 —— 奇数都是诗意的，这个很好理解，n // 2 和 n // 2 + 1这两个数相加肯定是等于 n 的。

所以我们可以把数分成两类 —— 奇数和偶数
所以我们再观察偶数，这里不好观察，我就把不是诗意的数给列了出来：

1 2 4 8 16 32 64

这一列出来，就很好发现了， 2的指数幂全都不是诗意的，那么我们的思路就出来了，就是判断这个数是不是2的指数幂。原因是什么我们晚点再分析。

代码：

n = int(input())
lst = list(map(int, input().split()))
cnt = 0
for i in range(n):
    x = lst[i]
    while x % 2 == 0:
        x = x // 2
    if x == 1:
        cnt += 1
print(cnt)

错因与正因分析

OK，这个是对的。我们先来分析一下为什么 2 的倍数就肯定不是诗意的。
根据题目的意思，我感觉我们一开始推出的公式是对的 ——

x，x+1，x+2，x+3 … x+n
它的所有符合的数肯定是符合这个规律的，所以，肯定是满足递增数列求和公式的。
……
相信有大佬应该看出来了，我前面的公式写错了。
应该是(x + x + n) * (n + 1) / 2

看来我们分析出原来的写法为什么错掉了。
那么这里先给出我修改之后的代码，但是测试之后还错的，超时了 ——

n = int(input())
lst = list(map(int, input().split()))
cnt = 0 # 用来记录要删除的个数
for i in range(n):
    x = lst[i]
    j = 2
    while j < x:
        y = (x * 2 / (j + 1) - j) / 2
        if y % 1 == 0:
            break
        j += 1
    else:
        cnt += 1
print(cnt)

# x x+1 x+2 x+3 ... x+n
# (x + x + n) * (n + 1) / 2

但是这种方式我不推荐，因为复杂度还是太高了，demo1的时间复杂度是O（n），demo2的时间复杂度是O（log n），可想而知哪种方式更好。

正解分析综合

2 的倍数就肯定不是诗意

OK，继续分析 2 的倍数就肯定不是诗意的，但是证明了我们前面的公式是对的，那么我们就可以直接代入公式 ——

2 ^y == (x + x + n) * (n + 1) / 2

我们把 x 当作一个数 i，**（x + n）**当作另一个数 j

那么式子就会变成 (i + j) ( i - j + 1) / 2
对于任意 i 和 j 的值，(i + j) 和 ( i - j + 1) 的奇偶性肯定是不同的，大家可以验证一下。

到这里， 2 的倍数就肯定不是诗意的就已经证明出来了。

那么对于其它数的情况为什么就肯定是诗意的？？

对于奇数，这个在前面说过了。

n // 2 和 n // 2 + 1这两个数相加肯定是等于 n 的。

对于不是 2 的指数幂的偶数。
首先，有前面可以知道**(i + j) 和 ( i - j + 1)** 的奇偶性肯定是不同的，所以在公式中/2之前肯定是奇数，而且可以是任意奇数，那么这里就可以理解了吧。

封闭图形个数

题目链接：封闭图形个数

思路分析

其实这题的思路可能比前面的题目更清晰：

1. 获取每一个数
2. 算出每一个数的封闭图形数
3. 排序
4. 输出

这题的难点在于怎么去排序，相信大家都知道。我这里给出两种方式：

一种是用自定义类，设置出一个新的格式，用新的格式使用sort()函数去排序。
另一种是使用 列表 类比的设置出新的格式使用sort()函数的lambda关键字去排序。
两者比较的话，我喜欢下面的，我不喜欢在写算法题里用到自定义类，感觉好难。

当然，大家也可以直接用基本排序算法，但是我喜欢直接用sort函数所以就没这么写，但是只要能写出来就都是好办法。

自定义类

import os
import sys

# 请在此输入您的代码
class num():
    def __init__(self, num, value):
        self.num = num
        self.value = value
    def __lt__(self, other):
        if self.value != other.value:
            return self.value < other.value
        return self.num < other.num


def get_value(num):
    size = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1] #记录所有数字的 封闭图形 的数目
    value = 0
    while num > 0:
        value += size[num % 10]
        num //= 10
    return value


n = int(input())
lst = list(map(int, input().split()))

lst1 = []
for i in range(n):
    lst1.append(num(lst[i], get_value(lst[i])))

lst1.sort()

for i in lst1:
    print(i.num, end = " ")

列表

import os
import sys

# 请在此输入您的代码
n = int(input())
lst = list(map(int, input().split()))

size = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1]  # 记录所有数字的 封闭图形 的数目
lst1 = []

for i in range(n):
    num = lst[i]
    value = 0
    while num > 0:
        value += size[num % 10]
        num //= 10
    lst1.append([lst[i], value])# 这里也可以在弄出所有value之后用zip来实现，但我感觉这样会简单一点

lst1.sort(key=lambda x: (x[1], x[0]))

for i in range(n):
    print(lst1[i][0], end=' ')

下回更精彩

这一期就先到这里吧，已经写了很多了，剩下的放在下一期里写。
OK，那么我们下回再见~

感谢大伙观看，别忘了三连支持一下

大家也可以关注一下我的其它专栏，同样精彩喔~

下期见咯~