Python - PAT

头图：https://cdn.naraku.cn/imgs/Python_PAT0.jpg
PAT (Basic Level) Practice

题号前带x的为部分测试点超时。

1001 害死人不偿命的(3n+1)猜想

题目

卡拉兹(Callatz)猜想：对任何一个正整数 n，如果它是偶数，那么把它砍掉一半；如果它是奇数，那么把 3n+1砍掉一半。这样一直反复砍下去，最后一定在某一步得到 n=1。卡拉兹在 1950 年的世界数学家大会上公布了这个猜想，传说当时耶鲁大学师生齐动员，拼命想证明这个貌似很傻很天真的命题，结果闹得学生们无心学业，一心只证 3n+1，以至于有人说这是一个阴谋，卡拉兹是在蓄意延缓美国数学界教学与科研的进展……
我们今天的题目不是证明卡拉兹猜想，而是对给定的任一不超过 1000 的正整数 n，简单地数一下，需要多少步（砍几下）才能得到 n=1 ？
输入样例：

每个测试输入包含 1 个测试用例，即给出正整数 n 的值。

3

输出样例：

输出从 n 计算到 1 需要的步数。

5

代码

count = 0
n = int(input())
while n!=1:
    n = n/2 if n%2==0 else (3*n+1)/2
    count+=1
print(count)

1002 写出这个数

题目

读入一个正整数 n，计算其各位数字之和，用汉语拼音写出和的每一位数字。
输入样例：

每个测试输入包含 1 个测试用例，即给出自然数 n 的值。这里保证 n 小于 10。

1234567890987654321123456789

输出样例：

在一行内输出 n 的各位数字之和的每一位，拼音数字间有 1 空格，但一行中最后一个拼音数字后没有空格。

yi san wu

代码

mapping = {
    0: "ling",
    1: "yi",
    2: "er",
    3: "san",
    4: "si",
    5: "wu",
    6: "liu",
    7: "qi",
    8: "ba",
    9: "jiu",
}
s = 0
num_str = ""
nums = input()  # 用str存储,便于遍历且不会超出整数范围
for num in nums:
    s += int(num)
while s>0:
    n = s%10  # 取余得个位
    s //= 10  # /会返回浮点型
    num_str = mapping[n] + " " + num_str
print(num_str[:-1])

总结

• 除法/会返回浮点数，//则会根据除数和被除数决定，其中一个是浮点数则返回浮点数，否则返回向下取整的整数。

  1003 我要通过！

  题目

  “答案正确”是自动判题系统给出的最令人欢喜的回复。本题属于 PAT 的“答案正确”大派送 —— 只要读入的字符串满足下列条件，系统就输出“答案正确”，否则输出“答案错误”。
  得到“答案正确”的条件是：

1. 字符串中必须仅有 P、 A、 T这三种字符，不可以包含其它字符；
2. 任意形如 xPATx 的字符串都可以获得“答案正确”，其中 x 或者是空字符串，或者是仅由字母 A 组成的字符串；
3. 如果 aPbTc 是正确的，那么 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字符串，或者是仅由字母 A 组成的字符串。

现在就请你为 PAT 写一个自动裁判程序，判定哪些字符串是可以获得“答案正确”的。
输入样例：

每个测试输入包含 1 个测试用例。第 1 行给出一个正整数 n (<10)，是需要检测的字符串个数。接下来每个字符串占一行，字符串长度不超过 100，且不包含空格。

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA

输出样例：

每个字符串的检测结果占一行，如果该字符串可以获得“答案正确”，则输出 YES，否则输出 NO。

YES
YES
YES
YES
NO
NO
NO
NO

代码

strs = []
flag = []
def judge(s):
    char = ['P','A','T','p','a','t']
    for c in s:
        if c not in char:  # 判断有没有其它字符
            return "NO"
  # 记录PT下标,并匹配abc
    p = s.find("P") if "P" in s else s.find("p")
    t = s.find("T") if "T" in s else s.find("t")
    a = s[:p]
    b = s[p+1:t]
    c = s[t+1:]
    if b == "":
        return "NO"
    if c != a*len(b):
        return "NO"
    return "YES"
n = int(input())
while n:
    value = input()
    strs.append(value)
    n -= 1
for s in strs:
    flag.append(judge(s))
for f in flag:
    print(f)

总结

• 思路：有形如xPyTx的字符串，x是空或仅由A组成的字符串，y是仅由A组成的字符串。以PT为分割线,P前段为a，P T之间为b，T之后为c，则若它是正确答案，有c=a*len(b)

  1004 成绩排名

  题目

  读入n（>0）名学生的姓名、学号、成绩，分别输出成绩最高和成绩最低学生的姓名和学号。
  输入样例：

  对每个测试用例输出 2 行，第 1 行是成绩最高学生的姓名和学号，第 2 行是成绩最低学生的姓名和学号，字符串间有 1 空格。

3
Joe Math990112 89
Mike CS991301 100
Mary EE990830 95

输出样例：

Mike CS991301
Joe Math990112

代码

n = int(input())
dic = {}
k = []
while n:
    msg = input().split()
    dic[int(msg[2])] = msg[0] + " " + msg[1]  # 以成绩为key,姓名学号为value存入字典
    n -= 1
for key in dic.keys():  # 把key存入列表,目的是使用max和min函数得到最大最小值
    k.append(key)
print(dic[max(k)])  # 以最大最小值为key输出字典中的value
print(dic[min(k)])

总结

• 因为题目保证成绩不会相同，所以以成绩为key,姓名学号为value的字典形式保存学生信息。此处列表的作用是用于存储key并得到最大最小的key，从而得到输出的value。

  1005 继续(3n+1)猜想

  题目

  卡拉兹(Callatz)猜想已经在1001中给出了描述。在这个题目里，情况稍微有些复杂。
  当我们验证卡拉兹猜想的时候，为了避免重复计算，可以记录下递推过程中遇到的每一个数。例如对 n=3 进行验证的时候，我们需要计算 3、5、8、4、2、1，则当我们对 n=5、8、4、2 进行验证的时候，就可以直接判定卡拉兹猜想的真伪，而不需要重复计算，因为这 4 个数已经在验证3的时候遇到过了，我们称 5、8、4、2 是被 3“覆盖”的数。我们称一个数列中的某个数 n为“关键数”，如果 n 不能被数列中的其他数字所覆盖。
  现在给定一系列待验证的数字，我们只需要验证其中的几个关键数，就可以不必再重复验证余下的数字。你的任务就是找出这些关键数字，并按从大到小的顺序输出它们。
  输入样例：

  每个测试输入包含 1 个测试用例，第 1 行给出一个正整数 K (<100)，第 2 行给出 K 个互不相同的待验证的正整数 n(1<n≤100)的值，数字间用空格隔开。

6
3 5 6 7 8 11

输出样例：

每个测试用例的输出占一行，按从大到小的顺序输出关键数字。数字间用 1 个空格隔开，但一行中最后一个数字后没有空格。

7 6

代码

n = input()
nums = list(map(int,input().split()))  # 转换成list
mark = nums[:]
for num in nums:
    k = num
    while k>1:
        k = k/2 if k%2==0 else (3*k+1)/2  # 找出k所覆盖的数并从列表中删除
        if k in mark:
            mark.remove(k)
mark.sort(reverse=True)
for i in range(len(mark)-1):
    print(mark[i],end=' ')
print(mark[-1], end='')

总结

1. map/filter函数在python2中返回列表，在python3中返回map/filter迭代器，且在经过一次for循环遍历后，再次访问会返回空列表。
   原因：由于Python中“没有指针，但是所有对象均为指针”，完成一次遍历后指针会移到最后一个元素上了。也就是说，D是一个map object，print(list(D))或者for循环打印D中的元素，都会导致迭代器从头走到尾（可以类比list[0]到list[n]）。 而迭代器是一个单向的容器，走到尾部之后，不会自动再回到开始位置。 所以，对Map对象进行一次for循环之后，Map就相当于“空”了。
   参考：Python3 循环遍历map
   
   • reverse()反转列表，无返回值；
   • sort()列表排序，无返回值；
   • sorted()列表排序，返回一个列表。

     1006 换个格式输出整数

     题目

     让我们用字母 B 来表示“百”、字母 S 表示“十”，用 12...n 来表示不为零的个位数字 n（<10），换个格式来输出任一个不超过 3 位的正整数。例如 `234` 应该被输出为 `BBSSS1234`，因为它有 2 个“百”、3 个“十”、以及个位的 4。
     输入样例 1：

     每个测试输入包含 1 个测试用例，给出正整数 n（<1000）。

234

输出样例 1：

每个测试用例的输出占一行，用规定的格式输出n。

BBSSS1234

输入样例 2：

23

输出样例 2：

SS123

代码

num = int(input())
n = num % 10  # 个位
s = num % 100 //10  # 十位
b = num // 100  # 百位
strs = b*'B' + s*'S'
for i in range(1, n+1):
    strs += str(i)
print(strs)

1007 素数对猜想

题目

定义d为：d=p+1−p，其中p是第i个素数。显然有d=1，且对于n>1有d是偶数。“素数对猜想”认为“存在无穷多对相邻且差为2的素数”。
现给定任意正整数N(<10)，请计算不超过N的满足猜想的素数对的个数。（素数：在大于1的自然数中,除了1和它本身以外不再有其他因数）
输入样例:

输入在一行给出正整数N。

20

输出样例:

在一行中输出不超过N的满足猜想的素数对的个数。

4

代码

运行

n = int(input())
nums = []
for i in range(2,n+1):
    for j in range(2,i):  # 如果在for循环中含有break时则直接终止循环，并不会执行else子句
        if(i%j == 0):
            break
    else:
        nums.append(i)
a = nums[:-1]  # 取nums中0~n-1位
b = nums[1:]   # 取nums中1~n位
c = [abs(a[i] - b[i]) for i in range(len(a))]  # ab相减即nums相邻数相减,然后取绝对值并存入c中
count = c.count(2)
print(count)

优化

原理：

• 从p=2开始,将2加入素数列表,并将所有2的倍数标记为0
• 向后依次取标记为1的数，先将其加入素数列表,然后将其所有倍数标记为0

n = int(input())
nums = []
flag = [1] * (n + 2)
p = 2
while (p <= n):
    nums.append(p)  # 将p加入素数列表,并将所有p的倍数标记为0
    for i in range(2 * p, n + 1, p):
        flag[i] = 0
    while True:  # 向后依次取标记为1的数
        p += 1
        if (flag[p] == 1):
            break
a = nums[:-1]  # 取nums中0~n-1位
b = nums[1:]   # 取nums中1~n位
c = [abs(a[i] - b[i]) for i in range(len(a))]  # ab相减即nums相邻数相减,然后取绝对值并存入c中
count = c.count(2)
print(count)

总结

• for-else语句
• 素数筛选优化

  1008 数组元素循环右移问题

  题目

  一个数组A中存有N（>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（≥0）个位置，即将A中的数据由(A A…A)变换为(A…A AA…A)（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？
  输入样例:

  每个输入包含一个测试用例，第1行输入N（1≤N≤100）和 M（≥0）；第2行输入N个整数，之间用空格分隔。

6 2
1 2 3 4 5 6

输出样例:

在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

5 6 1 2 3 4

代码

n,m = map(int,input().split())
m = m%n  # 将m取余n，可得移动的步数。当m=0或n的倍数,即无需移动。
nums = input().split()
for i in range(n-1):
    print(nums[i-m],end=" ")
print(nums[(n-1)-m],end="")

总结

因为Python支持负值索引，所以可以逐个遍历打印，无需使用另外的数组。

1009 说反话

题目

给定一句英语，要求你编写程序，将句中所有单词的顺序颠倒输出。
输入样例：

测试输入包含一个测试用例，在一行内给出总长度不超过 80 的字符串。字符串由若干单词和若干空格组成，其中单词是由英文字母（大小写有区分）组成的字符串，单词之间用 1 个空格分开，输入保证句子末尾没有多余的空格

Hello World Here I Come

输出样例：

每个测试用例的输出占一行，输出倒序后的句子。

Come I Here World Hello

代码

s = input().split()
s.reverse()  # 列表反转
for i in range(len(s)-1):
    print(s[i],end=" ")
print(s[-1],end="")

1010 一元多项式求导

题目

设计函数求一元多项式的导数。（注：x（n为整数）的一阶导数为nx-1 ）
输入样例:

以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过 1000 的整数）。数字间以空格分隔。

3 4 -5 2 6 1 -2 0

输出样例:

以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。注意“零多项式”的指数和系数都是 0，但是表示为 0 0。

12 3 -10 1 6 0

代码

nums = list(map(int, input().split()))
s = []
i = 0
# x^n => x=x*n, n-=1
while i < len(nums):
    x = nums[i]*nums[i+1]
    n = nums[i+1]-1
    i += 2
    if n==-1:  # 即原本的nums[i+1]=0,为常数项，所以不用添加进列表
        continue
    s.append(x)
    s.append(n)
if len(s)==0:  # 零多项式
    print('0 0')
else:
    for i in range(len(s)-1):
        print(s[i], end=" ")
    print(s[len(s)-1], end="")

1011 A+B 和 C

题目

给定区间 [−2,2] 内的 3 个整数 A、B 和 C，请判断 A+B 是否大于 C。
输入样例：

输入第 1 行给出正整数 T (≤10)，是测试用例的个数。随后给出 T 组测试用例，每组占一行，顺序给出 A、B 和C。整数间以空格分隔。

4
1 2 3
2 3 4
2147483647 0 2147483646
0 -2147483648 -2147483647

输出样例：

对每组测试用例，在一行中输出 Case #X: true 如果 A+B>C，否则输出 Case #X: false，其中 X 是测试用例的编号（从 1 开始）。

Case #1: false
Case #2: true
Case #3: true
Case #4: false

代码

n = int(input())
cases = ['false'] * n
for i in range(n):
    nums = list(map(int, input().split()))
    if nums[0]+nums[1]>nums[2]:
        cases[i] = 'true'
for i,case in enumerate(cases):
    print(f"Case #{i+1}: {case}")

1012 数字分类

题目

给定一系列正整数，请按要求对数字进行分类，并输出以下 5 个数字：

• A1 = 能被 5 整除的数字中所有偶数的和；
• A2 = 将被 5 除后余 1 的数字按给出顺序进行交错求和，即计算 n1−n2+n3−n4⋯；
• A3 = 被 5 除后余 2 的数字的个数；
• A4 = 被 5 除后余 3 的数字的平均数，精确到小数点后 1 位；
• A5 = 被 5 除后余 4 的数字中最大数字。

输入样例 1：

每个输入包含 1 个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N，随后给出N 个不超过 1000 的待分类的正整数。数字间以空格分隔。

13 1 2 3 4 5 6 7 8 9 10 20 16 18

输出样例 1：

对给定的 N个正整数，按题目要求计算 A1~A5 并在一行中顺序输出。数字间以空格分隔，但行末不得有多余空格。若其中某一类数字不存在，则在相应位置输出 N。

30 11 2 9.7 9

输入样例 2：

8 1 2 4 5 6 7 9 16

输出样例 2：

N 11 2 N 9

代码

nums = list(map(int, input().split()))[1:]  # 这里第一个输入的是数字总数,不能加入计算
A1 = list(filter(lambda n:n%5==0 and n%2==0, nums))  # 被5整除的数字中偶数的和
A2 = list(filter(lambda n:n%5==1, nums))  # 被5除后余1的数,交错求和 n1-n2+n3-n4...
A3 = list(filter(lambda n:n%5==2, nums))  # 被5除后余2的数的个数
A4 = list(filter(lambda n:n%5==3, nums))  # 被5除后余3的数的平均数,精确小数点后1位
A5 = list(filter(lambda n:n%5==4, nums))  # 被5除后余4的数中的最大数
out = []
out.append(sum(A1)) if A1 else out.append('N')
if A2:
    flag = 1
    temp = 0
    for num in A2:
        temp += num*flag
        flag = -flag
    out.append(temp)
else:
    out.append("N")
out.append(len(A3)) if A3 else out.append('N')
out.append(round(sum(A4)/len(A4),1)) if A4 else out.append('N')
out.append(max(A5)) if A5 else out.append('N')
for o in out[:-1]:
    print(o,end=' ')
print(out[-1])

总结

round(), 保留小数点后几位

1013 数素数

题目

令 P表示第 i 个素数。现任给两个正整数M ≤ N ≤10，请输出 P 到 P 的所有素数。
输入样例：
输入在一行中给出 M 和 N，其间以空格分隔。

5 27

输出样例：

输出 P 到 P 的所有素数，每 10 个数字占 1 行，其间以空格分隔，但行末不得有多余空格。

11 13 17 19 23 29 31 37 41 43
47 53 59 61 67 71 73 79 83 89
97 101 103

代码

m,n = map(int,input().split())
nums = []
# 找出第1~第n个素数
i = 2
while len(nums)<n:
    for j in range(2, i):
        if(i%j == 0):
            break
    else:
        nums.append(i)
    i+=1
# 输出第m~第n个素数
nums_mn = nums[m-1:]
for i,num in enumerate(nums_mn[:-1]):
    if (i+1) % 10 == 0:
        print(num)
    else:
        print(num,end=" ")
print(nums_mn[-1])

优化

m,n = map(int,input().split())
nums = []
# 找出第1~第n个素数
nums = []
flag = [1] * 200000  # 此处小于200000时测试点4会非零返回
p = 2
while (len(nums)<n):
    nums.append(p)  # 将p加入素数列表,并将所有p的倍数标记为0
    for i in range(2 * p, 200000, p):
        flag[i] = 0
    while True:  # 向后依次取标记为1的数
        p += 1
        if (flag[p] == 1):
            break
# 输出第m~第n个素数
nums_mn = nums[m-1:]
for i,num in enumerate(nums_mn[:-1]):
    if (i+1) % 10 == 0:
        print(num)
    else:
        print(num,end=" ")
print(nums_mn[-1])

1014 福尔摩斯的约会

题目

大侦探福尔摩斯接到一张奇怪的字条：我们约会吧！ 3485djDkxh4hhGE 2984akDfkkkkggEdsb s&hgsfdk d&Hyscvnm。大侦探很快就明白了，字条上奇怪的乱码实际上就是约会的时间星期四 14:04，因为前面两字符串中第 1 对相同的大写英文字母（大小写有区分）是第 4 个字母 D，代表星期四；第 2 对相同的字符是 E ，那是第 5 个英文字母，代表一天里的第 14 个钟头（于是一天的 0 点到 23 点由数字 0 到 9、以及大写字母 A 到 N 表示）；后面两字符串第 1 对相同的英文字母 s 出现在第 4 个位置（从 0 开始计数）上，代表第 4 分钟。现给定两对字符串，请帮助福尔摩斯解码得到约会的时间。
输入样例：

输入在 4 行中分别给出 4 个非空、不包含空格、且长度不超过 60 的字符串。

3485djDkxh4hhGE 
2984akDfkkkkggEdsb 
s&hgsfdk 
d&Hyscvnm

输出样例：

在一行中输出约会的时间，格式为 DAY HH:MM，其中 DAY 是某星期的 3 字符缩写，即 MON 表示星期一，TUE 表示星期二，WED 表示星期三，THU 表示星期四，FRI 表示星期五，SAT 表示星期六，SUN 表示星期日。题目输入保证每个测试存在唯一解。

THU 14:04

代码

str1 = input()
str2 = input()
str3 = input()
str4 = input()
mark = []
week = ['MON','TUE','WED','THU','FRI','SAT','SUN']
# ord() 转换为Ascii码,A=65
for i in range(min(len(str1),len(str2))):
    if (str1[i] == str2[i]) and ('A'<=str1[i]<='G'):
        mark.append(ord(str1[i]) - 64)
        break
for j in range(i+1, min(len(str1),len(str2))):
    if (str1[j] == str2[j]) and ('A'<= str1[j] <='N'):
        mark.append(str(ord(str1[j]) - 55))
        break
    elif (str1[j] == str2[j]) and ('0' <= str1[j] <= '9'):
        mark.append('0' + str1[j])
        break
for i in range(min(len(str3),len(str4))):
    if str3[i] == str4[i] and str3[i].isalpha():
        if i<10:
            mark.append('0' + str(i))
        else:
            mark.append(str(i))
print(f"{week[mark[0]-1]} {mark[1]}:{mark[2]}")

总结

ord()转换为ASCII码

x1015 德才论

题目

宋代史学家司马光在《资治通鉴》中有一段著名的“德才论”：“是故才德全尽谓之圣人，才德兼亡谓之愚人，德胜才谓之君子，才胜德谓之小人。凡取人之术，苟不得圣人，君子而与之，与其得小人，不若得愚人。”
现给出一批考生的德才分数，请根据司马光的理论给出录取排名。
输入样例：

输入第一行给出 3 个正整数，分别为：N（≤10），即考生总数；L（≥60），为录取最低分数线，即德分和才分均不低于 L 的考生才有资格被考虑录取；H（<100），为优先录取线——德分和才分均不低于此线的被定义为“才德全尽”，此类考生按德才总分从高到低排序；才分不到但德分到线的一类考生属于“德胜才”，也按总分排序，但排在第一类考生之后；德才分均低于 H，但是德分不低于才分的考生属于“才德兼亡”但尚有“德胜才”者，按总分排序，但排在第二类考生之后；其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。随后 N 行，每行给出一位考生的信息，包括：准考证号 德分 才分，其中准考证号为 8 位整数，德才分为区间 [0, 100] 内的整数。数字间以空格分隔。

14 60 80
10000001 64 90
10000002 90 60
10000011 85 80
10000003 85 80
10000004 80 85
10000005 82 77
10000006 83 76
10000007 90 78
10000008 75 79
10000009 59 90
10000010 88 45
10000012 80 100
10000013 90 99
10000014 66 60

输出样例：

输出第一行首先给出达到最低分数线的考生人数 M，随后 M 行，每行按照输入格式输出一位考生的信息，考生按输入中说明的规则从高到低排序。当某类考生中有多人总分相同时，按其德分降序排列；若德分也并列，则按准考证号的升序输出。

12
10000013 90 99
10000012 80 100
10000003 85 80
10000011 85 80
10000004 80 85
10000007 90 78
10000006 83 76
10000005 82 77
10000002 90 60
10000014 66 60
10000008 75 79
10000001 64 90

代码

注：测试点2/3/4运行超时，据说是Python性能问题？

"""
N 考生总数
L 录取最低分数线
H 优先录取线
1. 德分和才分均不低于H -> 【才德全尽】,此类考生按德才总分从高到低排序
2. 才分不到但德分到H ->【德胜才】，也按总分排序，但排在第一类考生之后
3. 德才分均低于H，但是德分不低于才分 -> 【才德兼亡】,但尚有【德胜才】者，按总分排序
4. 其他达到最低线 L 的考生也按总分排序，但排在第三类考生之后。
考生总数 录取最低分数线 优先录取线
准考证号 德分 才分
...
"""
# def rank(s):  # 排序方式
#     scores = s[1]+s[2]
#     return scores, s[1], -s[0]  # 德才总分,德分,学号.因为分数降序,而同分学号从低到高,所以学号取负
n,l,h = map(int, input().split())
l1,l2,l3,l4 = [],[],[],[]
while n:
    student = list(map(int,input().split()))
    if student[1]>=l and student[2]>=l:  # 德才均及格
        if student[1]>=h and student[2]>=h:
            l1.append(student)
        elif student[1]>=h:  # 前面判断了才分,这里可以不作判断
            l2.append(student)
        elif student[1]>=student[2]:
            l3.append(student)
        else:
            l4.append(student)
    n -= 1
print(len(l1)+len(l2)+len(l3)+len(l4))
for lis in (l1,l2,l3,l4):
    # lis.sort(key=rank,reverse=True)
    lis.sort(key=lambda s:(s[1]+s[2],s[1],-s[0]), reverse=True) # 将排序修改成lambda表达式返回元组
    for li in lis:
        print(f'{li[0]} {li[1]} {li[2]}')

总结

sort()，排序可以通过key参数传入一个函数来进行排序，且这个函数可返回多个值，排序时当第1个值相同时，会根据第2个值排序，以此类推；另外key若传入的是lambda表达式，返回多个值时需包装成元组来返回，如lis.sort(key=lambda s:(s[1]+s[2],s[1],-s[0]))

1016 部分A+B

题目

正整数 A 的“D（为 1 位整数）部分”定义为由 A 中所有 D 组成的新整数 P。例如：给定 A=3862767，D=6，则A的“6 部分”P 是 66，因为 A 中有 2 个 6。
现给定 A、D、B、D，请编写程序计算 P+P。
输入样例 1：

输入在一行中依次给出 A、D、B、D，中间以空格分隔，其中 0<A,B<10。

3862767 6 13530293 3

输出样例 1：

在一行中输出 P+P的值。

399

输入样例 2：

3862767 1 13530293 8

输出样例2：

0

代码

A,DA,B,DB = input().split()
pA,pB = '0','0'
for i in A:
    if i == DA:
        pA+=i
for i in B:
    if i == DB:
        pB+=i
print(int(pA)+int(pB))

1017 A除以B

题目

本题要求计算 A/B，其中 A 是不超过 1000 位的正整数，B*是 1 位正整数。你需要输出商数 Q 和余数 R，使得 A=B×Q+R 成立。
输入样例：

输入在一行中依次给出 A 和 B，中间以 1 空格分隔。

123456789050987654321 7

输出样例：

在一行中依次输出 Q 和 R，中间以 1 空格分隔。

17636684150141093474 3

代码

A,B = input().split()
q = int(A) // int(B)
r = int(A) % int(B)
print(q,r)

x1018 锤子剪刀布

题目

大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：

现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。
输入样例：

输入第 1 行给出正整数 N（≤10），即双方交锋的次数。随后 N 行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C 代表“锤子”、J 代表“剪刀”、B 代表“布”，第 1 个字母代表甲方，第 2 个代表乙方，中间有 1 个空格。

10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J

输出样例：

输出第 1、2 行分别给出甲、乙的胜、平、负次数，数字间以 1 个空格分隔。第 3 行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有 1 个空格。如果解不唯一，则输出按字母序最小的解。

5 3 2
2 3 5
B B

代码

注：测试点5运行超时，可能还是Python性能问题？

n = int(input())
count= [0,0,0]  # 记录甲胜平负,且甲输=乙胜
win1,win2 = [],[]  # 记录甲乙胜利手势
out = []
while n:
    p1,p2 = input().split()
    if p1==p2:  # 平局
        count[1] += 1
    elif (p1,p2) in [('C','J'), ('J','B'), ('B','C')]:  # 甲胜
        count[0] += 1
        win1.append(p1)  # 记录甲胜手势
    else:  # 乙胜
        count[2] += 1  # 甲负+1
        win2.append(p2)  # 记录乙胜手势
    n -= 1
for lst in [win1,win2]:
    if lst.count('B') >= lst.count('C') and  lst.count('B') >= lst.count('J'):
        out.append("B")
    elif  lst.count('C') >= lst.count('B') and  lst.count('C') >= lst.count('J'):
        out.append("C")
    else:
        out.append("J")
print(f'{count[0]} {count[1]} {count[2]}')  # 甲胜平负
print(f'{count[2]} {count[1]} {count[0]}')  # 乙胜平负
print(f'{out[0]} {out[1]}')

1019 数字黑洞

题目

给定任一个各位数字不完全相同的 4 位正整数，如果我们先把 4 个数字按非递增排序，再按非递减排序，然后用第 1 个数字减第 2 个数字，将得到一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的 6174，这个神奇的数字也叫 Kaprekar 常数。
例如，我们从6767开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
... ...

现给定任意 4 位正整数，请编写程序演示到达黑洞的过程。
输入样例 1：

输入给出一个 (0,104) 区间内的正整数 N。

6767

输出样例 1：

如果 N 的 4 位数字全相等，则在一行内输出 N - N = 0000；否则将计算的每一步在一行内输出，直到 6174 作为差出现，输出格式见样例。注意每个数字按 4 位数格式输出。

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174

输入样例 2：

2222

输出样例 2：

2222 - 2222 = 0000

代码

def hole(num):
    x = ''.join(sorted(num,reverse=True))
    y = x[::-1]  # 反转
    z = str(int(x) - int(y))
    if len(z) < 4:  # 补0
        z = (4-len(z)) * '0' + z
    print(f'{x} - {y} = {z}')
    if z == '6174':
        return
    else:  # 递归执行
        hole(z)
num = input()
if len(num) < 4:  # 不足4位前面补0
    num = (4-len(num)) * '0' + num
if num[0]==num[1]==num[2]==num[3]:  # 4位相等
    print(f'{num} - {num} = 0000')
else:
    hole(num)

总结

• 字符串s不能直接使用s.sort()进行排序，会抛出AttributeError属性错误。但可以用sorted(s)来将其排序并返回一个列表，再通过''.join()将返回的列表添加到一个空字符串中，这样即可将某个字符串进行排序。

s = '9527'
s = ''.join(sorted(s))
print(s)  # '2579'

1020 月饼

题目

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。
注：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3 种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45 亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15 万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。
输入样例：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N 表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D 表示市场最大需求量。随后一行给出 N 个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N 个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

3 20
18 15 10
75 72 45

输出样例：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

94.50

代码

n,d = map(int, input().split())
goods = list(map(float, input().split()))
price = list(map(float, input().split()))
unit_price = {i:price[i]/goods[i] for i in range(n)}  # 单价
sort_price = sorted(unit_price, key=lambda i:unit_price[i], reverse=True)  # 单价排序
profit = 0
for i in sort_price:
    if d >= goods[i]:  # 当前需求量>库存量 -> 全都要
        profit += price[i]
        d -= goods[i]
    else:  # 当前需求量<库存量
        profit += d * unit_price[i]  # 当前需求量*对应单价
        break
print(f"{profit:.2f}")

总结

贪心算法：物品可以分割为任意大小，可选用贪心策略3: 选取单位价值最大的物品。 先计算出每种月饼的单价，再根据单价进行降序排序，最后从高到低进行销售，此时收益最大。

1021 个位数统计

题目

给定一个 k 位整数 N=d10+⋯+d10+d (0 ≤ d ≤ 9, i=0,⋯,k−1, d > 0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定 N=100311，则有 2 个 0，3 个 1，和 1 个 3。
输入样例：

每个输入包含 1 个测试用例，即一个不超过 1000 位的正整数 N。

100311

输出样例：

对 N 中每一种不同的个位数字，以 D:M 的格式在一行中输出该位数字 D 及其在 N 中出现的次数 M。要求按 D 的升序输出。

0:2
1:3
3:1

代码

num = input()
count = [0] * 10
for i in num:
    count[int(i)] += 1
for i,c in enumerate(count):
    if c:
        print(f'{i}:{c}')

1022 D进制的A+B

题目

输入两个非负 10 进制整数 A 和 B (≤230−1)，输出 A+B 的 D (1输入样例：

输入在一行中依次给出 3 个整数 A、B 和 D。

123 456 8

输出样例：

输出 A+B 的 D 进制数。

1103

代码

a,b,d = map(int, input().split())
n = a + b
nums = [0,1,2,3,4,5,6,7,8,9,'A','B','C','D','E','F']
out = []
while True:  # 不能while n直接跳出,因为可能会漏掉最后一个余数
    y = n % d  # 余
    n //= d    # 商
    out.append(y)
    if n==0:
        break
out.reverse()
for o in out:
    print(nums[o],end="")

1023 组个最小数

题目

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。
现给定数字，请编写程序输出能够组成的最小的数。
输入样例：

输入在一行中给出 10 个非负整数，顺序表示我们拥有数字 0、数字 1、……数字 9 的个数。整数间用一个空格分隔。10 个数字的总个数不超过 50，且至少拥有 1 个非 0 的数字。

2 2 0 0 0 3 0 0 1 0

输出样例：

在一行中输出能够组成的最小的数。

10015558

代码

count = input().split()
nums = []
for index,c in enumerate(count):
    nums += int(c) * str(index)  # 数量*下标(0~9)
for i in range(len(nums)):
    if nums[i]!='0':    # 将首位与第1位非0数交换
        nums[0],nums[i] = nums[i], nums[0]
        break
for n in nums:
    print(n,end="")

1024 科学计数法

题目

科学计数法是科学家用来表示很大或很小的数字的一种方便的方法，其满足正则表达式 [+-][1-9].[0-9]+E[+-][0-9]+，即数字的整数部分只有 1 位，小数部分至少有 1 位，该数字及其指数部分的正负号即使对正数也必定明确给出。
现以科学计数法的格式给出实数 A，请编写程序按普通数字表示法输出 A，并保证所有有效位都被保留。
输入样例 1：

每个输入包含 1 个测试用例，即一个以科学计数法表示的实数 A。该数字的存储长度不超过 9999 字节，且其指数的绝对值不超过 9999。

+1.23400E-03

输出样例 1：

对每个测试用例，在一行中按普通数字表示法输出 A，并保证所有有效位都被保留，包括末尾的 0。

0.00123400

输入样例 2：

-1.2E+10

输出样例 2：

-12000000000

代码

n,powe = input().split('E')
flag = '' if n[0]=='+' else '-'  # 正负
a,b = n[1:].split(".")  # 整数.小数
num = a + b
e = int(powe[1:]) # 指数大小,无+-号
b_len = len(b)    # 小数位数
if e == 0:
    out = f'{flag}{n[1:]}'  # 不直接使用n[:]的原因是正数不需输出+号
elif powe[0] == '+':
    if e-b_len < 0:
        out = f'{flag}{num[:(e+1)]}.{num[(e+1):]}'
    else:
        out = f'{flag}{num}{(e-b_len)*"0"}'
else:
    out = f'{flag}0.{(e-1)*"0"}{num}'
print(out)

x1025 反转链表

题目

给定一个常数 K 以及一个单链表 L，请编写程序将 L 中每 K 个结点反转。例如：给定 L 为 1→2→3→4→5→6，K 为 3，则输出应该为 3→2→1→6→5→4；如果 K 为 4，则输出应该为 4→3→2→1→5→6，即最后不到 K 个元素不反转。
输入样例：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出第 1 个结点的地址、结点总个数正整数 N (≤105)、以及正整数 K(≤N)，即要求反转的子链结点的个数。结点的地址是 5 位非负整数，NULL 地址用 −1 表示。接下来有 N 行，每行格式为：

Address Data Next

其中 Address 是结点地址，Data 是该结点保存的整数数据，Next 是下一结点的地址。

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

输出样例：

对每个测试用例，顺序输出反转后的链表，其上每个结点占一行，格式与输入相同。

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

代码

注：测试点5运行超时

start,n,k = input().split()
in_lines = []  # 暂时存放输入的列表
sort_lines = []  # 排序的列表
out_lines = []   # 输出的列表
for i in range(int(n)):
    line = input().split()
    if line[0] == start:
        sort_lines.append(line)  # 首位直接存入排序列表
    else:
        in_lines.append(line)
# 将存放输入的列表按顺序存入排序列表
while sort_lines[-1][2] != '-1':
    for li in in_lines:
        if li[0] == sort_lines[-1][2]:  # 排序
            sort_lines.append(li)
            break
# 从第0位开始,如果剩余结点满足k位,则反转后追加到输出列表;不满足则直接追加到输出列表后跳出
for i in range(0, int(n), int(k)):
    if len(sort_lines[i:i+int(k)]) >= int(k):
        temp = sort_lines[i:i+int(k)]
        temp.reverse()
        out_lines += temp
    else:
        out_lines += sort_lines[i:i+int(k)]
        break
# 将next指针指向下一结点的地址,并将最后一个结点的next记为-1
for i in range(len(out_lines)-1):
    out_lines[i][2] = out_lines[i+1][0]
out_lines[-1][2] = '-1'
# 输出
for line in out_lines:
    print(f'{line[0]} {line[1]} {line[2]}')

1026 程序运行时间

题目

要获得一个 C 语言程序的运行时间，常用的方法是调用头文件 time.h，其中提供了 clock() 函数，可以捕捉从程序开始运行到 clock() 被调用时所耗费的时间。这个时间单位是 clock tick，即“时钟打点”。同时还有一个常数 CLK_TCK，给出了机器时钟每秒所走的时钟打点数。于是为了获得一个函数 f 的运行时间，我们只要在调用 f 之前先调用 clock()，获得一个时钟打点数 C1；在 f 执行完成后再调用 clock()，获得另一个时钟打点数 C2；两次获得的时钟打点数之差 (C2-C1) 就是 f 运行所消耗的时钟打点数，再除以常数 CLK_TCK，就得到了以秒为单位的运行时间。这里不妨简单假设常数 CLK_TCK 为 100。现给定被测函数前后两次获得的时钟打点数，请你给出被测函数运行的时间。
输入样例：

输入在一行中顺序给出 2 个整数 C1 和 C2。注意两次获得的时钟打点数肯定不相同，即 C1 < C2，并且取值在 [0,107]。

123 4577973

输出样例：

在一行中输出被测函数运行的时间。运行时间必须按照 hh:mm:ss（即2位的 时:分:秒）格式输出；不足 1 秒的时间四舍五入到秒。

12:42:59

代码

CLK_TCK = 100
a,b = map(int, input().split())
time =round((b-a)/CLK_TCK)  # 取整
hh = time//3600
mm = time//60%60
ss = time%60
print('%02d:%02d:%02d' % (hh,mm,ss))  # 格式化,不足2位需补0

1027 打印沙漏

题目

本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个*，要求按下列格式打印

*****
 ***
  *
 ***
*****

所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。
输入样例:

输入在一行给出1个正整数N（≤1000）和一个符号，中间以空格分隔。

19 *

输出样例:

首先打印出由给定符号组成的最大的沙漏形状，最后在一行中输出剩下没用掉的符号数。

*****
 ***
  *
 ***
*****
2

代码

n,star = input().split()
out = [star]  # 将1颗星存入输出列表
n = int(n)-1  # 剩余数量
i = 3  # 下一层星数
while n>0:
    if (n - i*2)<=0:
        break
    else:
        n = n - i*2
    out.insert(0, i*star)  # 分别在头尾插入
    out.append(i*star)
    i += 2
for i in out:
    print("%s%s" % (" "*((len(out[0])-len(i))//2),i))  # (第1层长度-当前层长度)/2,即为空格数量
print(n)

1028 人口普查

题目

某城镇进行人口普查，得到了全体居民的生日。现请你写个程序，找出镇上最年长和最年轻的人。
这里确保每个输入的日期都是合法的，但不一定是合理的——假设已知镇上没有超过 200 岁的老人，而今天是 2014 年 9 月 6 日，所以超过 200 岁的生日和未出生的生日都是不合理的，应该被过滤掉。
输入样例：

输入在第一行给出正整数 N，取值在(0,105]；随后 N 行，每行给出 1 个人的姓名（由不超过 5 个英文字母组成的字符串）、以及按 yyyy/mm/dd（即年/月/日）格式给出的生日。题目保证最年长和最年轻的人没有并列。

5
John 2001/05/12
Tom 1814/09/06
Ann 2121/01/30
James 1814/09/05
Steve 1967/11/20

输出样例：

在一行中顺序输出有效生日的个数、最年长人和最年轻人的姓名，其间以空格分隔。

3 Tom John

代码

注：同样的代码，Python3最后一项超时，Python2反而不会超时。

# Python3
n = int(input())
count = 0
max_day = ['','2014/09/06']
min_day = ['','1814/09/06']
while n:
    person = input().split()
    if '1814/09/06' <= person[1] <= "2014/09/06":
        count += 1
        if person[1] < max_day[1]:
            max_day = person
        if person[1] > min_day[1]:
            min_day = person
    n -= 1
if count:
    print(f'{count} {max_day[0]} {min_day[0]}')
else:
    print("0")

优化

# Python2
n = int(raw_input())
count = 0
max_day = ['', '2014/09/06']
min_day = ['', '1814/09/06']
while n:
    person = raw_input().split()
    if '1814/09/06' <= person[1] <= '2014/09/06':
        count += 1
        if person[1] < max_day[1]:
            max_day = person
        if person[1] > min_day[1]:
            min_day = person
    n -= 1
if count:
    print count, max_day[0], min_day[0]
else:
    print '0'

1029 旧键盘

题目

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及实际被输入的文字，请你列出肯定坏掉的那些键。
输入样例：

输入在 2 行中分别给出应该输入的文字、以及实际输入的文字。每段文字是不超过 80 个字符的串，由字母 A-Z（包括大、小写）、数字 0-9、以及下划线 _（代表空格）组成。题目保证 2 个字符串均非空。

7_This_is_a_test
_hs_s_a_es

输出样例：

按照发现顺序，在一行中输出坏掉的键。其中英文字母只输出大写，每个坏键只输出一次。题目保证至少有 1 个坏键。

7TI

代码

str1 = input()  # 应该输入的文字
str2 = input()  # 实际输入的文字
no_exist = []
for s in str1:
    if s not in str2:
        s = s.upper() if s.isalpha() else s
        if s not in no_exist:
            no_exist.append(s)
for i in no_exist:
    print(i,end="")

1030 完美数列

题目

给定一个正整数数列，和正整数 p，设这个数列中的最大值是 M，最小值是 m，如果 M≤mp，则称这个数列是完美数列。
现在给定参数 p 和一些正整数，请你从中选择尽可能多的数构成一个完美数列。
输入样例：

输入第一行给出两个正整数 N 和 p，其中 N（≤10）是输入的正整数的个数，p（≤10）是给定的参数。第二行给出 N 个正整数，每个数不超过 10。

10 8
2 3 20 4 5 1 6 7 8 9

输出样例：

在一行中输出最多可以选择多少个数可以用它们组成一个完美数列。

8

代码

x = [int(i) for i in input().split()]
n = x[0]
p = x[1]
nums = input().split()
nums = sorted(map(int, nums))
count = 0
for i in range(n):
    while count + i < n:
        if nums[i] * p >= nums[i + count]:
            count += 1
        else:
            break
print(count)

1031 查验身份证

题目

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：
首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

Z：0 1 2 3 4 5 6 7 8 9 10
M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。
输入样例1：

输入第一行给出正整数N（≤100）是输入的身份证号码的个数。随后N行，每行给出1个18位身份证号码。

4
320124198808240056
12010X198901011234
110108196711301866
37070419881216001X

输出样例1：

按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出All passed。

12010X198901011234
110108196711301866
37070419881216001X

输入样例2：

2
320124198808240056
110108196711301862

输出样例2：

All passed

分析

题目要求通过计算身份证前17位数和权重加权求和，得到加权和再取余11得到z，再通过关系表得到M，最后判断M是否与身份证的第18位相等，且如果全部身份证都有效，需输出All passed。另外题目提示只检查前17位是否全为数字且最后1位校验码计算准确，因此只需遍历身份证的每一位，当存在非数字则可直接记为错误并输出；若全为数字，则计算并判断校验码的准确性即可。

代码

weight = [7, 9, 10, 5, 8, 4, 2, 1, 6, 3, 7, 9, 10, 5, 8, 4, 2]  # 权重
ZM = ['1','0','X','9','8','7','6','5','4','3','2']  # 记录ZM对应关系
error = 0
n = int(input())
for i in range(n):
    num = input()
    count = 0
    flag = 1  # 记录是否全为数字
    for index in range(17):
        if num[index].isdigit():  # 判断是否数字
            count += weight[index]*int(num[index])
        else:  # 存在非数字flag设为0
            print(num)
            error = 1
            flag = 0
            break
    if flag:
        count %= 11
        if num[-1] != ZM[count]: # 判断校验码有效性
            print(num)
            error = 1
if error==0:
    print("All passed")