当前位置: 首页 > article >正文

第十五届蓝桥杯大赛软件赛省赛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,对于这道题,我们总共是做三件事:

  1. 读取log,如果是比赛应该就是分次读取,大概就是
a , b , h = map(int, input().split())
  1. 然后判断敲击对不对,时间超不超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之前肯定是奇数,而且可以是任意奇数,那么这里就可以理解了吧。

封闭图形个数

题目链接:封闭图形个数

在这里插入图片描述
在这里插入图片描述

思路分析

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

  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,那么我们下回再见~

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

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

下期见咯~

请添加图片描述


http://www.kler.cn/a/588057.html

相关文章:

  • vulnhub-Hackme-隧道建立、SQL注入、详细解题、思路清晰。
  • CSS:使用内边距时,解决宽随之改变问题
  • C#通过API接口返回流式响应内容---SSE方式
  • rk3568 yt8521S phy设备层丢包定位处理
  • Smart Time Plus smarttimeplus-MySQLConnection SQL注入漏洞(CVE-2024-53544)
  • 链表题目2(leetcode24题)交换链表里面的节点
  • Flutter FloatingActionButton 从核心用法到高级定制
  • 从LLM出发:由浅入深探索AI开发的全流程与简单实践(全文3w字)
  • ElasticSearch组合查询及实际应用
  • python unity通讯数据解析2
  • WindowsPE文件格式入门01.PE头
  • [Windows] OfficeScrubber_13--office卸载清理工具
  • 【JavaEE】快速上手JSON:构建高效 Java 后端数据桥梁,开启交互新篇,以 @RequestBody 为引的探索之旅
  • 类和对象C++ (未完:对象特征)
  • linux - 基础IO之操作与文件描述符全解析:从C语言到系统调用底层实现
  • python爬虫Scrapy(5)之增量式
  • 生物角度分析
  • PHP语言的死锁
  • GBase8c 删除备机
  • 【Java 优选算法】分治 - 快速排序