HNUCM-蓝桥杯PythonB组寒假练习2
问题 A: 选房子
题目描述
栋栋和李剑已经大四了，想要出去找房子住。他们一共看中了n套房子。其中第i套房子已经住了ai个人了，它最多能住bi个人。栋栋和李剑想要住在一起，那么请问他们有几套可以选择的房子？
输入
输入的第一行为一个正整数T (T<=1000)，代表一共有T组测试数据。
每组测试数据的第一行有一个正整数n (1<=n<=100)，代表一共有n套房子。接下来n行，每行有两个正整数ai，bi (1<=ai<=bi<=100)，分别代表现在已经住了ai个人和最多能住bi个人。
输出
对于每组测试数据，输出一行包含一个整数，代表他们可以选择房子的数量。
思路
简单的减法判断题，判断b - a 是否大于2即可。
代码
t = int(input())
while t > 0:
t, n, cnt = t - 1, int(input()), 0
for _ in range(n):
a, b = map(int, input().split())
if b - a >= 2:
cnt += 1
print(cnt)
问题 B: 倍数问题
题目描述
众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数，希望你从这 n 个数中找到三个数
使得这三个数的和是 K 的倍数，且这个和最大。数据保证一定有解。
输入
第一行包括 2 个正整数 n, K。
第二行 n 个正整数，代表给定的 n 个数。
1 <= n <= 10^5, 1 <= K <= 10^3，给定的 n 个数均不超过 10^8。
输出
输出一行一个整数代表所求的和。
思路
题目可以使用枚举也可以使用动态规划（0-1背包）的思路进行解题，以下为枚举法。因为题目要求选取三个数，通过推理我们不难发现，在某一余数情况下，最多选取三个数，最少选取零个数。同时为了满足“最大"的要求，可以使用一个二维列表结合插入排序对输入进行处理，每个余数情况下，至多保留三个最大的数，以此降低题目规模。然后枚举三个数的余数，确定这三个数。
代码
while True:
try:
n, k = map(int, input().split())
# remainder二维列表用来存储处理余数后的输入，res存储结果
remainder, nums, res = [[0] * 3 for i in range(k)], list(map(int, input().split())), 0
for num in nums: # 使用插入排序，保证每个余数列表remainder[i]不会超过三个数，且存储的数为最大的三个数
re = num % k # 获取余数
if num > remainder[re][0]: # 插入排序
remainder[re][0], remainder[re][1], remainder[re][2] = num, remainder[re][0], remainder[re][1]
elif num > remainder[re][1]:
remainder[re][1], remainder[re][2] = num, remainder[re][1]
elif num > remainder[re][2]:
remainder[re][2] = num
# 枚举余数，获得三个数，三个数分别为a, b, c
for i in range(k): # i代表a的余数
for j in range(i, k): # j代表b的余数
z = (k - i + k - j) % k # z代表c的余数
a = remainder[i][0] # 根据a的余数获得a
if i == j: # 如果a的余数和b的余数相同
b = remainder[i][1] # 根据b的余数获得b
c = remainder[i][2] if i == z else remainder[z][0] # 根据c的余数获得c
else: # 如果a的余数和b的余数不同
b = remainder[j][0] # 根据b的余数获得b
c = remainder[i][1] if i == z else remainder[j][1] if j == z else remainder[z][0] # 根据c的余数获得c
if a + b + c > res: # 比较，获得结果
res = a + b + c
print(res) # 输出结果
except:
break
问题 C: X星游戏
题目描述
X星人这几天很无聊，他发明了一个自娱自乐的小游戏。
现在有若干张写有0、1、2、3、......、9这10个数字之一的纸牌，每一次可以拿出一张牌。
将抽取到的牌中的数字连成一个数列，如果当前抽的牌中的数字在前面出现过，则收取这两张牌及其它们之间所有的牌。
请你编写一个程序，计算最多的一次可以收取到多少张牌？
【注：可能最后还留有一些牌没有被收取】
输入
单组输入。
第1行输入一个数字N，表示X星人总共抽取的牌数，N<=1000。
第2行输入N个数字，分别对应X星人每一次抽取到的纸牌上的数字，两两之间用空格隔开。
输出
输出最多一次可以收取到的牌的数量。
思路
简单的模拟题，模拟游戏的操作，对列表进行删除即可。
代码
def add(x: int, y: int):
global res, index
res = max(res, y - x + 1)
for i in range(y, x - 1, -1):
del nums[i]
index = x
n, nums, index, res = int(input()), [int(i) for i in input().split()], 1, -1
while True:
try:
tmp = nums[index]
if tmp in nums[:index]:
add(nums[:index].index(tmp), index)
else:
index += 1
except:
break
print(res)
问题 D: 近似回文词
题目描述
输入一行文本，输出最长近似回文词连续子串。所谓近似回文词是指满足以下条件的字符串：
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）。如果有多个最长近似回文子串解，起始位置应尽量小。
思路
利用其他的列表存储源字符串的字母与下标信息，对字符串的字母进行回文串的判断（枚举中间位，分奇数与偶数两种长度情况）。
代码
cnt = 0
while True:
try:
cnt, k, buf = cnt + 1, int(input()), list(input().lower())
n, p, ch, res = len(buf), [], [], -1
# print(buf)
for i in range(n):
if buf[i].isalpha():
p.append(i + 1), ch.append(buf[i])
# print(buf, p, ch)
f, n = 0, len(p)
for i in range(n):
err, j = k, 0
while i - j >= 0 and i + j < n:
if ch[i - j] != ch[i + j]:
err -= 1
if err < 0:
break
t = p[i + j] - p[i - j] + 1
if t > res:
res, f = t, p[i - j]
j += 1
err, j = k, 0
while i - j >= 0 and i + j + 1 < n:
if ch[i - j] != ch[i + j + 1]:
err -= 1
if err < 0:
break
t = p[i + j + 1] - p[i - j] + 1
if t > res:
res, f = t, p[i - j]
j += 1
print(f"Case {cnt}: {res} {f}")
except:
break
E: 最少硬币
题目描述
假设有4种硬币，它们的面值分别为1分、5分、10分和25分。
现在要找给顾客n分钱。
请问怎样找零钱才能使给顾客的硬币个数最少？
输出所需最少硬币的枚数。
输入
输入需要找给顾客的零钱n（单位：分）。
输出
输出所需最少硬币的枚数。
思路
经典的贪心问题，从最大的硬币开始找即可。
代码
money = [25, 10, 5, 1]
while True:
try:
n, cnt, index = int(input()), 0, 0
while n > 0:
if n >= money[index]:
n, cnt = n % money[index], cnt + n // money[index]
else:
index += 1
print(cnt)
except:
breakF: X星大学
题目描述
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星币才能保证任意两栋楼之间都有光纤直接或者间接相连。
思路
最短路径问题，可以采用对应的算法即可。
代码
N, C = map(int, input().strip().split(' '))
v = set()
load = []
cost = 0
uuu = N * (N - 1) // 2
while uuu > 0:
uuu -= 1
a, b, c = map(int, input().strip().split(' '))
load.append((c, a, b))
load.sort()
# print(loads)
c, a, b = load.pop(0)
v.add(a)
v.add(b)
cost += c
while len(v) < N:
for c, a, b in load:
if (a in v and b not in v) or (a not in v and b in v):
v.add(a)
v.add(b)
cost += c
break
# print(11)
# print(v)
print(cost * C)
G: 奖牌榜
题目描述
X星学校的运动会正在激烈进行中。
现在需要请你编写一个程序来显示所有班级的奖牌榜，显示规则如下：
(1) 优先按照金牌数量降序排列后显示。
(2) 如果金牌数相等则比较银牌数，银牌数多者显示在前。
(3) 如果金牌和银牌数都相等，则比较铜牌数，铜牌数多者显示在前。
(4) 如果金、银、铜数量均相等，则按照班级编号从小到大排列后显示。
(5) 需要按照班级编号、金牌数、银牌数、铜牌数、奖牌总数的顺序显示每个班级的奖牌情况。
已知X星学校的班级编号为一个四位正整数，且班级编号具有唯一性。
输入
单组输入。
第1行输入一个正整数N，表示班级的总数量，N<=9000。
接下来N行，每1行包含四个正整数，分别表示班级编号、金牌数、银牌数和铜牌数。金牌数、银牌数和铜牌数均小于100。两两之间用英文空格隔开。
输出
显示按照规则排序之后的奖牌榜，每一行都包含班级编号、金牌数、银牌数、铜牌数和奖牌总数，两两之间用英文空格隔开。
思路
使用sort函数结合lambda函数即可完成解题。
代码
n, t, box = int(input()), 0, []
while t < n:
t += 1
a, b, c, d = map(int, input().split())
box.append((a, b, c, d))
box.sort(key=lambda x: [-x[1], -x[2], -x[3], x[0]])
for a, b, c, d in box:
print(a, b, c, d, b + c + d)