Python教程

蓝桥杯第十一届省赛题解(Python)

本文主要是介绍蓝桥杯第十一届省赛题解(Python),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

第一题

在这里插入图片描述
  不出意料的签到题,遍历。

#法一
ans = 0
for i in range(1,2021):
    for j in str(i):
        if j == "2":
            ans += 1
print(ans)

#法二
s=0
for i in range(1, 2021):
    s+=str(i).count('2')  #count函数只能使用于字符串,因此需要将数字转换为字符串的形式
print(s)


第二题

在这里插入图片描述
  仔细看下来,这道题分作两步,第一步是读取文件,第二步就是按照题目的意思进行遍历。也没有多少技术可言,但是我们需要注意的是要重点关注边界条件,因为如果边界有时取到有时没取到就会让我们的代码少寻找到一个甚至更多的数字,最后有可能导致出错(在这种题里面一般都会有,因为它的技术不难,就是考你是否仔细)。

int_file = open(r"./int.txt")   #读取文件
matrix = []

while True:
    data = int_file.readline()  # 每次取出一行数据, 不过这样确实是浪费了好多时间。。。
    if data[-1] != '\n':  # 最后一行数据的最后一个元素为数字【0, 2】
        matrix.append(list(data))
        break
    else:
        data = data[:-1]
    a = list(data)
    matrix.append(a)
int_file.close()
row = len(matrix)  # 行
col = len(matrix[0])  # 列
count = 0
for i in range(row):
    for j in range(col):
        if matrix[i][j] == '2':  # 取出的数据类型都是字符串所以用字符'2'
            if j + 3 < col:
                if matrix[i][j] + matrix[i][j + 1] + matrix[i][j + 2] + matrix[i][j + 3] == "2020":
                    count += 1
            if i + 3 < row:
                if matrix[i][j] + matrix[i + 1][j] + matrix[i + 2][j] + matrix[i + 3][j] == "2020":
                    count += 1
            if i + 3 < row and j + 3 < col:
                if matrix[i][j] + matrix[i + 1][j + 1] + matrix[i + 2][j + 2] + matrix[i + 3][j + 3] == "2020":
                    count += 1
print(count)

第三题

在这里插入图片描述
  很明显,这道题考察我们对Python中的内置包datetime的了解程度,只要你掌握了datetime,那么这道题很快就能写出来(其实也不用太熟悉,了解一个函数就行),当然,手撸代码也是可以的,但是比较麻烦就是了。

import datetime
start = datetime.date(2000,1,1)
end = datetime.date(2020,10,1)
days = datetime.timedelta(days=1)  # 用以可用于计算的一天  timedelta代表两个时间之间的时间差
res = 0
while start <= end:
    if start.day == 1 or start.weekday() == 0:
        res += 2
    else:
        res += 1
    start += days
print(res)

第四题

在这里插入图片描述
  典型的大忽悠题,看上去贼拉复杂,但其实根本不用代码就能做。
  第二十行,第二十列,很明显,在对角线上,我们先观察对角线上的数字,分别是1、5、13…,当然,我们还可以继续写。依次是1、5、13、25、41…,写道这一步的时候,规律很自然的就出来了,他们相邻数之间的差是4、8、12、16…,也就是一个公差为4的等差数列,递推关系式为 a n − a n − 1 = 4 ( n − 1 ) a_n-a_{n-1} = 4(n-1) an​−an−1​=4(n−1) 并且 a 1 = 1 a_1=1 a1​=1。最终算出来 a n = 2 n ( n − 1 ) + 1 a_n = 2n(n-1)+1 an​=2n(n−1)+1。然后把 n = 20 n=20 n=20代入即可。
  当然,如果非要写代码的话也不是不行,只需要建立一个 2 × 20 − 1 = 39 2\times20-1=39 2×20−1=39的 39 × 39 39\times39 39×39的矩阵模拟数组的生成即可。只是这种方法显然不够简洁(就是懒,不想写)。

第五题

在这里插入图片描述
  显然的,这道题考察我们对冒泡排序的熟悉程度。我们都理解冒泡排序的时间复杂度是 O ( n 2 ) O(n^2) O(n2),但一般也就仅限于此了。但是这里具体到交换次数,那我们就要知道,冒泡排序的交换次数是 f ( n ) = n ( n − 1 ) / 2 f(n)=n(n-1)/2 f(n)=n(n−1)/2(完全逆序的情况),那么很明显,这道题要求字符串最短的情况,肯定就是采用完全逆序的情况。同时,它还要求字典序最小,那很明显,就是采用从A开始排列的情况,那么需要多少个字母呢?
  首先它的 f ( n ) f(n) f(n)一定要大于等于100,我们代入公式,发现离100最近的是 n = 15 n=15 n=15,对应 f ( n ) = 105 ) f(n)=105) f(n)=105),也就是说,如果我的排列方式是 o n m l k j i h g f e e d c b a onmlkjihgfeedcba onmlkjihgfeedcba,那运用冒泡排序就要交换105次,但是我们的要求是100次,如果仅是这样的话,我们有多种交换方式,把任意一个字母向前交换5次即可。
  这个时候字典序就发挥作用了,所谓字典序最小,就是字母序最小,那我们就要让比较字母表前面的字母尽可能的出现在最前面,但是由于主体需要是逆序,那我们就让首字母尽可能靠前,105次,那就把 o n m l k j i h g f e e d c b a onmlkjihgfeedcba onmlkjihgfeedcba的第六个字母交换五次放在首位。 j o n m l k i h g f e e d c b a jonmlkihgfeedcba jonmlkihgfeedcba就是我们的答案了。

第六题

在这里插入图片描述
  比第一题还像签到题。

n = eval(input())
num1, num2 = 0, 0
for i in range(n):
    score = eval(input())
    if score >= 60:
        num1 += 1
        if score >= 85:
            num2 += 1
precent_qualified = format(num1 / n * 100, '.0f')
precent_excellent = format(num2 / n * 100, '.0f') 
print(str(precent_qualified) + "%")
print(str(precent_excellent) + "%")

第七题

在这里插入图片描述
在这里插入图片描述
  由于单词长度不超过1000,所以这也是一道签到题,最复杂也不过遍历 26 × 1000 26\times1000 26×1000次,完全能够在 1 s 1s 1s内完成执行。

lis, lit = [], [0] * 26
s = input()
for i in range(26):
    lis.append(chr(97+i))

for i in range(len(lis)):
    for k in s:
        if k == lis[i]:
            lit[i] += 1
for i in range(len(lit)):
    if lit[i] == max(lit):
        p = lis[i]
print(p)
print(max(lit))

第八题在这里插入图片描述

在这里插入图片描述
  学过算法的同学大概都知道,数字三角形是一道特别经典的动态规划入门题,网络上有大量的讲解,其中,我个人比较推荐的是大学MOOC里面由北京大学郭炜老师主讲的《程序设计与算法》(有兴趣可以自己去看看,这里就不放链接了)。对数字三角形这道题做了很详细的讲解。
  那么这道题我们就先把他当作数字三角形来看,我们在之前的文章中说过,动态规划最重要的部分是找到递推关系式,和起始条件。也就是初始化数组,最后找到遍历顺序。
  起始条件很明显,就是三角形的顶点数字。初始化数组在这道题里面我们可以就在输入数组里面进行修正,所以使用原数组即可。然后找递推公式,动态规划使得我们需要每一步都是尽可能的优化,所以我们可以写出递推公式是 d p [ i ] [ j ] + = m a x ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] ) dp[i][j]+=max(dp[i-1][j],dp[i-1][j-1]) dp[i][j]+=max(dp[i−1][j],dp[i−1][j−1])(大部分是这样的,反例我还没找到,但是在蓝桥杯官网上提交会报错,看了看别人的代码,应该是没有处理边界条件,即 i = j i=j i=j,和 j = 0 j=0 j=0的情况,添加上判断就没有问题了)。
  在处理完一般的数字三角形后,我们来看限制条件,向左和向右次数差不能超过1。那其实简单画一下就能知道,这样画的结果最后一定会落在最后一行的中间,如果是奇数行,那就是最中间那个,偶数行就找中间两个比较大的数就可以了

n = eval(input())
lst = []
for i in range(n):
    m = list(map(int,input().split()))
    lst.append(m)

list_1 = [[0 for _ in range(n)] for _ in range(n)]

list_1[0][0] = lst[0][0]

for k in range(1,n):
    for t in range(k+1):
        if t == 0:
            list_1[k][t] = list_1[k-1][t] + lst[k][t]
        elif t == k:
            list_1[k][t] = list_1[k-1][t-1] + lst[k][t]
        else:
            list_1[k][t] = max(list_1[k-1][t-1],list_1[k-1][t]) + lst[k][t]


            
if n % 2 == 0:
    print(max(list_1[n-1][n//2-1],list_1[n-1][n//2]))
else:
    print(list_1[n-1][n//2])

第九题

在这里插入图片描述
  老实讲,我一开始打算把它当作数学题来做的,奈何写了一堆推导,发现我很难对每一种情况给出公式,也就没办法计算,那就只有老老实实撸代码了。
  当然,现实是我也没撸出来,原因稍后解释。我从其它地方找了一篇文章,大家看看,代码也是这位博主的。

N = int(input()) #输入N
setpointline = set()
sumvalue =1
for i in range(N):
    seta = set()  #每次都遍历一次
    linex,liney = map(int,input().split())
    for x,y in setpointline:
        if(x==linex and y==liney): #如果重合
            sumvalue-=1  #
            seta=set()  #去掉原有集合种的元素
            break
        elif(x==linex):  #如果斜率相同,没有交点
            continue
        else:
            nodex = (y-liney)/(linex-x) #交点
            nodey = x*nodex + y #代入任意方程
            seta.add((nodex,nodey)) #进入集合
    sumvalue+=len(seta)+1  #也就是加入
    if ((linex, liney) not in setpointline):
        setpointline.add((linex, liney))  # 是不是有重边
print(sumvalue) #输出子平面个数

第十题

写在后面

  以前写文章都是随性而为,今年在元旦的时候为同学们写了一下十一届蓝桥杯国赛的题解,认识到了自己还有很多不足,于是希望今年能够坚持每周一篇博文,但是由于本人比较懒。一直拖到了这周的最后一天的最后几个小时,只有匆匆忙忙的看了前面的简单题,后面两道题已经没有时间看了,所以第九题代码没有撸出来,第十题甚至没有看。
  所以在这里立一个小小的 f l a g flag flag吧,希望新的一年能够改掉自己的拖延症吧,不要把所有事情拖到最后,这样确实不好。
  然后就是,写题解确实能够帮助我们找到许多的不足,比如说第八题,我自认为数字三角形了解的不错,动态规划学的也还行,但是今天重新写代码的时候,在蓝桥杯的系统提交了三次分别是10、70、20,最后还是看了别人代码才得了全分,这个事情也提醒我,写博客和题解有利于我们了解自己对知识的掌握程度。只有写出来才能知道自己的基础怎么样。
  最后,希望大家共同进步,2022,希望大家监督我,每周一更(可能是算法、数据结构、一些题解)

这篇关于蓝桥杯第十一届省赛题解(Python)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!