189 8069 5689

HNUCM蓝桥杯Python组寒假第二次练习-创新互联

文章目录
  • 1316: 选房子
  • 2158: 倍数问题
  • 2196: X星游戏
  • 1034: 近似回文词
  • 1749: 最少硬币
  • 2079: X星大学
  • 2086: 奖牌榜
  • 总结:

在鼓楼等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供网站建设、做网站 网站设计制作按需网站设计,公司网站建设,企业网站建设,品牌网站设计,全网整合营销推广,成都外贸网站制作,鼓楼网站建设费用合理。1316: 选房子

1316: 选房子
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
栋栋和李剑已经大四了,想要出去找房子住。他们一共看中了n套房子。其中第i套房子已经住了ai个人了,它最多能住bi个人。栋栋和李剑想要住在一起,那么请问他们有几套可以选择的房子?

输入
输入的第一行为一个正整数T (T<=1000),代表一共有T组测试数据。

每组测试数据的第一行有一个正整数n (1<=n<=100),代表一共有n套房子。接下来n行,每行有两个正整数ai,bi (1<=ai<=bi<=100),分别代表现在已经住了ai个人和最多能住bi个人。

输出
对于每组测试数据,输出一行包含一个整数,代表他们可以选择房子的数量。

样例输入 Copy
2
2
1 2
1 3
3
1 10
2 10
3 10
样例输出 Copy
1
3
来源/分类
首届全国中医药院校大学生程序设计竞赛

分析:由题意得只要b-a>=2即可
代码:

n=int(input())
for i in range(n):
    m=int(input())
    count=0
    for j in range(m):
        a,b=map(int,input().split( ))
        if b-a>=2:
            count=count+1
    print(count)
2158: 倍数问题

2158: 倍数问题
[命题人 : 202001080138]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数
使得这三个数的和是 K 的倍数,且这个和大。数据保证一定有解。
输入
第一行包括 2 个正整数 n, K。
第二行 n 个正整数,代表给定的 n 个数。
1<= n <= 10^5, 1<= K <= 10^3,给定的 n 个数均不超过 10^8。
输出
输出一行一个整数代表所求的和。
样例输入 Copy
4 3
1 2 3 4
样例输出 Copy
9
来源/分类
分析:利用插入排序最多保留同一个余数的前三大数,然后再利用cnt=(k-(i+j)%k)%k或者cnt=( 2*k-i-j) % k,两重循环得出满足条件的cnt,i,j三个数。细节如下:
代码:

n, k = map(int, input().split())
s = list(map(int, input().split()))
m = [[0 for i in range(3)] for i in range(k)] #只取同一个余数大的前三个
for i, t in enumerate(s):# 插入交换
    if t in m[t % k]:
        continue
    if t >m[t%k][0]:
        m[t%k][0],m[t%k][1],m[t%k][2]=t,m[t%k][0],m[t%k][1]
    elif t>m[t%k][1]:
        m[t % k][0], m[t % k][1], m[t % k][2] = m[t % k][0],t, m[t % k][1]
    elif t >m[t % k][2]:
        m[t % k][0], m[t % k][1], m[t % k][2] = m[t % k][0], m[t % k][1], t
sum1 = 0
for i in range(k):
    if m[i][0] ==0:
        continue
    for j in range(k):
        if m[j][0] == 0:#如果第一个数为0则代表这个列表里面没有元素
            continue
        z = ( 2*k-i-j) % k#z=(k-(i+j)%k)%k也可
        sum2=0  #分为5种情况:
        if i == j and j != z and m[z][0] >0 and m[i][0] >= 0:# i和j在一个余数列表里面,z不在,然后判断各自余数列表里面有没有这么多元素,没有就直接跳过,节约时间.
            sum2 =m[i][0] + m[i][1] + m[z][0]
        elif i == j and j == z and m[i][2] >0:#原理同上
            sum2 = m[i][0] + m[i][1] + m[j][2]
        elif i == z and j != z and m[i][1] >0 and m[j][0] >0:
            sum2 =  m[i][0] + m[i][1] + m[j][0]
        elif i != j and j != z and z != i and m[i][0] >0 and m[z][0] >0 and m[j][0] >0:
            sum2 =  m[i][0] + m[j][0] + m[z][0]
        elif j == z and i != z and m[j][1]>0 and m[i][0] >0:
            sum2 = m[i][0] + m[j][0] + m[j][1]
        if sum2>sum1: #注意为了防止超时,最好不要用python自带函数max.
            sum1=sum2
print(sum1)

蓝桥云课AC截图
在这里插入图片描述

2196: X星游戏

2196: X星游戏
[命题人 : admin]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
X星人这几天很无聊,他发明了一个自娱自乐的小游戏。
现在有若干张写有0、1、2、3、…、9这10个数字之一的纸牌,每一次可以拿出一张牌。
将抽取到的牌中的数字连成一个数列,如果当前抽的牌中的数字在前面出现过,则收取这两张牌及其它们之间所有的牌。
请你编写一个程序,计算最多的一次可以收取到多少张牌?
【注:可能最后还留有一些牌没有被收取】
输入
单组输入。
第1行输入一个数字N,表示X星人总共抽取的牌数,N<=1000。
第2行输入N个数字,分别对应X星人每一次抽取到的纸牌上的数字,两两之间用空格隔开。
输出
输出最多一次可以收取到的牌的数量。
样例输入 Copy
10
0 1 2 3 1 1 0 4 2 1
样例输出 Copy
4
提示
对于样例数据而言,最多收取4张牌,对应的数字序列是:1 2 3 1,即第2张牌到第5张牌。
来源/分类
分析:由题意模拟即可,用栈模拟也可。
代码:

def find(n,k):#从前面找到和n相同的数字的序号
    for i in range(len(k)-1,-1,-1):
        if k[i]==n:
            return i
def pick(a,b,k):#将a到b的值设为“p”
    for i in range(a,b):
        if k[i]!='p':
           k[i]="p"
def maxs(a,b,k):#计算a,b两张牌之间一共还有几张牌
    sum1=1
    for i in range(a,b):
        if k[i]!='p':
            sum1+=1
    return sum1
while True:
    n=int(input())
    s=list(map(int,input().split()))
    k=[]
    max1=0
    for t in s:#如果t不在列表,就加入
        if t not in k:
            k.append(t)
        else:
            index=find(t,k)#找到前面和t相同数字的序号
            max1=max(max1,maxs(index,len(k),k))#更新相同两张牌之间的大数目
            pick(index,len(k),k)#将前面和数字t相同的数字到数字t给去掉,为了防止频繁的插入和删除超时,就直接将其值改为“p”
    print(max1)
1034: 近似回文词

1034: 近似回文词
[命题人 : 外部导入]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
输入一行文本,输出最长近似回文词连续子串。所谓近似回文词是指满足以下条件的字符串:

  1. S以字母开头,字母结尾
  2. a(S)和b(S)最多有2k个位置不同,其中a(S)是S删除所有非字母字符之后得到的串,b(S)是a(S)的逆序串。
    比如当k=1时,Race cat是一个近似回文词,因为a(S)=racecat和b(S)=tacecar只有2个位置不同。

输入
输入包含不超过25组数据,每组数据包含两行。第一行是整数k(0<=k<=200),第二行为字符串S,包含不超过1000个字符(换行符不算)。S只包含字符、空格和其他可打印字符(比如逗号,句号),并且不会以空白字符开头。

输出
对于每组测试数据,输出最长近似回文子串的长度和起始位置(S的第一个字符是位置1)。如果有多个最长近似回文子串解,起始位置应尽量小。

样例输入 Copy
1
Wow, it is a Race cat!
0
abcdefg
0
Kitty: Madam, I’m adam.
样例输出 Copy
Case 1: 8 3
Case 2: 1 1
Case 3: 15 8
来源/分类
湖南省第九届大学生计算机程序设计竞赛
分析:我用暴力模拟直接超时,oj只过了50%,然后在看到大佬的博客之后醍醐灌顶,以后遇到这类问题再也不怕超时了。思路:先记录字母和其序号,然后再以i为回文串的中心,以j为回文串的半径循环枚举,如果有k个不同就直接退出,进入下轮循环。注意要区分字符串长度的奇偶,细节如下:
代码:

cnt = 0
while True:
    try:
        cnt += 1
        k = int(input())
        p = input()
        maxlen, index = 0, 0
        s=[]
        sign=[]
        for i, t in enumerate(p):#记录字母和其序号,并将字母全部变为小写
            if t.isalpha():
                sign.append(i)
                s.append(t.lower())
        for i in range(len(s)):#以i为中心
            j, count = 0, 0
            while i + j< len(s) and i - j >= 0:#以j为半径的回文字符串,偶数情况下
                if s[i + j] != s[i - j]:#如果两边不等就记录+1
                    count += 1
                if count >k:#
                    break
                j += 1
            j-=1# 因为j退出时多加了1
            if sign[i + j] - sign[i - j]+1 >maxlen:#sign[i + j] - sign[i - j]+1,+1是因为列表是从下标为0开始的
                maxlen = sign[i + j] - sign[i - j] + 1
                index = sign[i - j]#记录开始的点
            j, count = 0, 0
            while i + j + 1< len(s) and i - j >= 0:#奇数情况,其他同上
                if s[i + j+1] != s[i - j]:
                    count += 1
                if count >k:
                    break
                j += 1
            j-=1
            if j<0:continue
            if sign[i + j+1] - sign[i - j]+1 >maxlen:
                maxlen = sign[i + j+1] - sign[i - j] + 1
                index = sign[i - j]
        print('Case %d: %d %d'%(cnt, maxlen, index+1))
    except:
        break

AC截图:
在这里插入图片描述

1749: 最少硬币

1749: 最少硬币
[命题人 : admin]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
假设有4种硬币,它们的面值分别为1分、5分、10分和25分。
现在要找给顾客n分钱。
请问怎样找零钱才能使给顾客的硬币个数最少?
输出所需最少硬币的枚数。
输入
输入需要找给顾客的零钱n(单位:分)。
输出
输出所需最少硬币的枚数。
样例输入 Copy
8
10
63
样例输出 Copy
4
1
6
来源/分类
算法分析与设计 贪心
分析:可以直接贪心从大的硬币名额遍历求得最少硬币的枚数,也可以采用dp算法时效性最好。
dp算法:

while True:
    n=int(input())
    s=[1,5,10,25]
    m=[0 for i in range(n+1)]
    def solve():
        for i in range(n+1):
            m[i]=float("inf")
        m[0]=0
        for j in range(4):
            for i in range(s[j],n+1):
                m[i]=min(m[i],m[i-s[j]]+1)#滚动数组
    solve()
    print(m[n])

在这里插入图片描述

贪心算法:

k=[25,10,5,1]
while True:
      count=0
      n=int(input())
      for i in range(4):
            z=0
            if n>=k[i]:
                  z=n//k[i]
                  n=n-z*k[i]
                  count=count+z
            else:
                  continue
      print(count)

在这里插入图片描述

2079: X星大学

2079: X星大学
[命题人 : admin]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
X星大学新校区终于建成啦!
新校区一共有N栋教学楼和办公楼。现在需要用光纤把这N栋连接起来,保证任意两栋楼之间都有一条有线网络通讯链路。
已知任意两栋楼之间的直线距离(单位:千米)。为了降低成本,要求两栋楼之间都用直线光纤连接。
光纤的单位成本C已知(单位:X星币/千米),请问最少需要多少X星币才能保证任意两栋楼之间都有光纤直接或者间接相连?
注意:如果1号楼和2号楼相连,2号楼和3号楼相连,则1号楼和3号楼间接相连。
输入
单组输入。
第1行输入两个正整数N和C,分别表示楼栋的数量和光纤的单位成本(单位:X星币/千米),N<=100,C<=100。两者之间用英文空格隔开。
接下来N*(N-1)/2行,每行包含三个正整数,第1个正整数和第2个正整数表示楼栋的编号(从1开始一直到N),编号小的在前,编号大的在后,第3个正整数为两栋楼之间的直线距离(单位:千米)。
输出
输出最少需要多少X星币才能保证任意两栋楼之间都有光纤直接或者间接相连。
样例输入 Copy
3 10
1 2 5
1 3 6
2 3 7
样例输出 Copy
110
来源/分类
分析:可以采用prime算法最小生成树,这里采用并查集,利用路径压缩优化查询。
代码:

def init(n, k):#初始化并查集,每个人得祖先是自己
    for i in range(1, n + 1):
        k[i] = i
    return k
def find(x, k):#递归寻找祖先
    if x != k[x]:
        k[x] = find(k[x],k)
    return k[x]
def union(x, y, k):#合并,指向同一个祖先
    x = find(x,k)
    y = find(y,k)
    if x != y:
        k[x] = k[y]
while True:
    n, c1 = map(int, input().split())
    k = [[] for i in range(n + 1)]
    init(n, k)
    sum1 = 0
    w = [[] for i in range((n * (n - 1) // 2))]
    for i in range(n * (n - 1) // 2):#列举路径数
        a, b, c = map(int, input().split())
        w[i].append(a)
        w[i].append(b)
        w[i].append(c)
    w.sort(key=lambda x: x[2], reverse=False)#将路径小的排前面
    for t in w:
        x, y, z = t[0], t[1], t[2]
        x1 = find(x, k)#寻找两个的祖先
        y1 = find(y, k)
        if x1 != y1:#不同则合并指向同一个祖先
            union(x, y, k)
            sum1 += z
    print(sum1*c1)
2086: 奖牌榜

2086: 奖牌榜
[命题人 : admin]
时间限制 : 1.000 sec 内存限制 : 128 MB

题目描述
X星学校的运动会正在激烈进行中。
现在需要请你编写一个程序来显示所有班级的奖牌榜,显示规则如下:
(1) 优先按照金牌数量降序排列后显示。
(2) 如果金牌数相等则比较银牌数,银牌数多者显示在前。
(3) 如果金牌和银牌数都相等,则比较铜牌数,铜牌数多者显示在前。
(4) 如果金、银、铜数量均相等,则按照班级编号从小到大排列后显示。
(5) 需要按照班级编号、金牌数、银牌数、铜牌数、奖牌总数的顺序显示每个班级的奖牌情况。
已知X星学校的班级编号为一个四位正整数,且班级编号具有唯一性。

输入
单组输入。
第1行输入一个正整数N,表示班级的总数量,N<=9000。
接下来N行,每1行包含四个正整数,分别表示班级编号、金牌数、银牌数和铜牌数。金牌数、银牌数和铜牌数均小于100。两两之间用英文空格隔开。
输出
显示按照规则排序之后的奖牌榜,每一行都包含班级编号、金牌数、银牌数、铜牌数和奖牌总数,两两之间用英文空格隔开。
样例输入 Copy
4
1000 4 10 5
1001 5 11 6
1002 4 11 4
1003 4 10 5
样例输出 Copy
1001 5 11 6 22
1002 4 11 4 19
1000 4 10 5 19
1003 4 10 5 19
来源/分类
分析:多维数组排序,细节见:python如何自定义排序
代码:

while True:
    n=int(input())
    s=[]
    for i in range(n):
        s.append(list(map(int,input().split())))
    s.sort(key=lambda x:(x[1],x[2],x[3],-x[0]),reverse=True)
    for i in range(n):
        s[i].append(sum(s[i][1:]))
        for j in range(5):
            if j!=0:
                print(" ",end="")
            print(s[i][j],end="")
        print()
总结:

代码写的比较烂,各位大佬多多指教

你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧


当前文章:HNUCM蓝桥杯Python组寒假第二次练习-创新互联
网站地址:http://cdxtjz.cn/article/dhddop.html

其他资讯