第十五届蓝桥杯大赛软件赛省赛Python 大学 C 组题目试做(上)
因为要考蓝桥省赛了,还是要准备一下的,虽然实力很一般,但总得挣扎一下。
文章目录
- 拼正方形
- 偷鸡解法
- 题目分析
- 劲舞团
- 思路分析
- 数字诗意
- 思路分析(错掉了)
- 思路再分析(对的)
- 错因与正因分析
- 正解分析综合
- 2 的倍数就肯定不是诗意
- 那么对于其它数的情况为什么就肯定是诗意的??
- 封闭图形个数
- 思路分析
- 自定义类
- 列表
- 下回更精彩
- 感谢大伙观看,别忘了三连支持一下
- 大家也可以关注一下我的其它专栏,同样精彩喔~
- 下期见咯~
拼正方形
题目链接:拼正方形
偷鸡解法
这是蓝桥杯那一届的算是签到题,只需要输出结果,所以我觉得我们其实没有那么大的必要去一定要解出这道题。
我们最后要输出的是边长,我们就先算一下所有的方块数:
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,对于这道题,我们总共是做三件事:
- 读取log,如果是比赛应该就是分次读取,大概就是
a , b , h = map(int, input().split())
- 然后判断敲击对不对,时间超不超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(n2),必然是会超时间的。
那么我们就该去想连续数能不能直接用一个公式去表示,这样就省下第二层循环的时间,也就是 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之前肯定是奇数,而且可以是任意奇数,那么这里就可以理解了吧。
封闭图形个数
题目链接:封闭图形个数
思路分析
其实这题的思路可能比前面的题目更清晰:
- 获取每一个数
- 算出每一个数的封闭图形数
- 排序
- 输出
这题的难点在于怎么去排序,相信大家都知道。我这里给出两种方式:
一种是用自定义类,设置出一个新的格式,用新的格式使用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,那么我们下回再见~