【2022天梯赛模拟赛】 题解

2022天梯赛题解，主python，能261分

前几天不是刚模拟赛完吗，这次模拟赛pythonL1很多超时是我没想到的，快正赛了，赶紧把模拟赛题从头到尾过一遍，看一下没拿满分的问题出在哪里…
折腾了一天终于能做的都做了理解了，为了加深记忆这边自己稍微记录一下，愿共勉。

L1-1:自动编程

输出语句是每个程序员首先要掌握的语句。Python 的输出语句很简单，只要写一个 print(X) 即可，其中 X 是需要输出的内容。

本题就请你写一个自动编程机，对任何一个要输出的整数 N，给出输出这个整数的 Python 语句。

输入格式：
输入给出一个不超过 10
5
的正整数。

输出格式：
在一行中打印输出这个整数的 Python 语句，其中不包含任何空格。

思路：python的f字符串直接输出就行，签到题

a = input()
print(f"print({a})")

L1-2 太神奇了

“告诉大家一个神奇的消息，太神奇了：明年全世界所有的人都同岁，全部都等于2022。明年的日子很特别，大概每1000年才会有一次。明年你的周岁年龄+你的出生年，每个人都是2022年。例如：你明年57加上1965年生的，加起来就是2022年。特别奇怪，连中外专家都无法解释！你计算一下，看看是不是2022。真是千年等一回呀！真准！转朋友圈，让大伙都算一下吧！”

据说这个“电子包浆”贴每年都会出现。本题就请你根据发贴人提到的周岁年龄和出生年，判断其发贴的时候是哪一年。

输入格式：
输入在第一行中给出两个正整数，即周岁年龄和出生年，其中年龄在 (0, 200) 区间内，出生年在 (1900, 2022) 区间内。

输出格式：
在一行中输出发贴年份。

输入样例：
57 1965
输出样例：
2021
样例说明
因为贴子里说“明年全世界所有的人都同岁”，所以发贴是在今年，即 2021 年。

思路：输入的两个数字a,b，输出a + b - 1即可

a, b = map(int, input().split())
print(a + b - 1)

L1-3 洛希极限

洛希极限（Roche limit）是一个天体自身的引力与第二个天体造成的潮汐力相等时的距离。当两个天体的距离少于洛希极限，天体就会倾向碎散，继而成为第二个天体的环。它以首位计算这个极限的人爱德华·洛希命名。（摘自百度百科）

大天体密度与小天体的密度的比值开 3 次方后，再乘以大天体的半径以及一个倍数（流体对应的倍数是 2.455，刚体对应的倍数是 1.26），就是洛希极限的值。例如木星与地球的密度比值开 3 次方是 0.622，如果假设地球是流体，那么洛希极限就是 0.622×2.455=1.52701 倍木星半径；但地球是刚体，对应的洛希极限是 0.622×1.26=0.78372 倍木星半径，这个距离比木星半径小，即只有当地球位于木星内部的时候才会被撕碎，换言之，就是地球不可能被撕碎。

本题就请你判断一个小天体会不会被一个大天体撕碎。

输入格式：
输入在一行中给出 3 个数字，依次为：大天体密度与小天体的密度的比值开 3 次方后计算出的值（≤1）、小天体的属性（0 表示流体、1 表示刚体）、两个天体的距离与大天体半径的比值（>1 但不超过 10）。

输出格式：
在一行中首先输出小天体的洛希极限与大天体半径的比值（输出小数点后2位）；随后空一格；最后输出 ^_ 如果小天体不会被撕碎，否则输出 T_T。

输入样例 1：
0.622 0 1.4
输出样例 1：
1.53 T_T
输入样例 2：
0.622 1 1.4
输出样例 2：
0.78 ^_

思路：阅读理解题，按照题意写即可。（当时胡写着也过了，所有符号挨个试一遍

from decimal import Decimal

a, b, c = map(eval, input().split())
if b == 1:
    d = 1.26
else:
    d = 2.455
ans1 = a * d
if a / c * d <= 1:
    print(f"{Decimal(ans1).quantize(Decimal('0.00'))} ^_^")
else:
    print(f"{Decimal(ans1).quantize(Decimal('0.00'))} T_T")

L1-4 吃鱼还是吃肉

国家给出了 8 岁男宝宝的标准身高为 130 厘米、标准体重为 27 公斤；8 岁女宝宝的标准身高为 129 厘米、标准体重为 25 公斤。

现在你要根据小宝宝的身高体重，给出补充营养的建议。

输入格式：
输入在第一行给出一个不超过 10 的正整数 N，随后 N 行，每行给出一位宝宝的身体数据：

性别 身高 体重
其中性别是 1 表示男生，0 表示女生。身高和体重都是不超过 200 的正整数。

输出格式：
对于每一位宝宝，在一行中给出你的建议：

如果太矮了，输出：duo chi yu!（多吃鱼）；
如果太瘦了，输出：duo chi rou!（多吃肉）；
如果正标准，输出：wan mei!（完美）；
如果太高了，输出：ni li hai!（你厉害）；
如果太胖了，输出：shao chi rou!（少吃肉）。
先评价身高，再评价体重。两句话之间要有 1 个空格。

输入样例：
4
0 130 23
1 129 27
1 130 30
0 128 27
输出样例：
ni li hai! duo chi rou!
duo chi yu! wan mei!
wan mei! shao chi rou!
duo chi yu! shao chi rou!

思路：if else分支，读懂题写就完事儿了，签到题

n = int(input())
for i in range(n):
    a, b, c = map(int, input().split())
    if a == 1:
        h = 130
        w = 27
    else:
        h = 129
        w = 25
    if b < h:
        print("duo chi yu!", end=' ')
    elif b > h:
        print("ni li hai!", end=' ')
    else:
        print("wan mei!", end=' ')
    if c < w:
        print("duo chi rou!")
    elif c > w:
        print("shao chi rou!")
    else:
        print("wan mei!")

L1-5 不变初心数

不变初心数是指这样一种特别的数，它分别乘 2、3、4、5、6、7、8、9 时，所得乘积各位数之和却不变。例如 18 就是这样的数：18 的 2 倍是 36，3+6=9；18 的 3 倍是 54，5+4=9；…… 18 的 9 倍是 162，1+6+2=9。对于 18 而言，9 就是它的初心。本题要求你判断任一个给定的数是否有不变的初心。

输入格式：
输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一个不超过 10
5
的正整数。

输出格式：
对每个给定的数字，如果它有不变的初心，就在一行中输出它的初心；否则输出 NO。

输入样例：
4
18
256
99792
88672
输出样例：
9
NO
36
NO

思路：字符串形式输入，作为可迭代对象，遍历目标乘积数组，判断是否满足题意即可

n = int(input())
for i in range(n):
    number = input()
    __sum = set()
    numbers = [int(number) * j for j in (2, 3, 4, 5, 6, 7, 8, 9)]
    for num in numbers:
        _sum = 0
        for item in str(num):
            _sum += int(item)
        __sum.add(_sum)
        if len(__sum) > 1:
            print("NO")
            break
    else:
        print(_sum)

L1-6 字母串

英语老师要求学生按照如下规则写一串字母：

如果写了某个大写字母，下一个就必须写同个字母的小写，或者写字母表中下一个字母的大写；
如果写了某个小写字母，下一个就必须写同个字母的大写，或者写字母表中前一个字母的小写；
当然也可以什么都不写，就结束这个字母串。
例如 aAaABCDdcbBC 就是一个合法的字母串；而 dEFfeFGhI 就是非法的。注意 a 没有前一个字母， Z 也没有下一个字母。

现在面对全班学生交上来的作业，老师请你写个程序自动批改。

输入格式：
输入在第一行给出一个不超过 100 的正整数 N。随后 N 行，每行给出一位学生的作业，即仅由英文字母组成的非空字母串，长度不超过 2×10
6
。

输出格式：
对每位学生的作业，如果正确就在一行中输出 Y，否则输出 N。

输入样例：
2
aAaABCDdcbBC
dEFfeFGhI
输出样例：
Y
N

思路：接收输入后，从第一位判断至倒数第二位，一直没问题即可，否则直接判错并break。python最后一个点超时，相同代码改C++后满分。

#include 

using namespace std;

int main() {
    int num;
    cin >> num;
    string arr[1000];
    bool ans[1000] = {0};
    for (int i = 0; i < num; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < num; i++) {
        if (arr[i].length() == 0 or arr[i].length() == 1) {
            continue;
        }
        for (int j = 0; j < arr[i].length() - 1; j++) {
            // upper
            if (isupper(arr[i][j])) {
                if (arr[i][j + 1] == char(tolower(arr[i][j]))) {
                    continue;
                } else if (arr[i][j + 1] == char(toupper(arr[i][j]) + 1) && (arr[i][j] != 'Z' && arr[i][j] != 'z')) {
                    continue;
                }
            } else {
                if (arr[i][j + 1] == char(toupper(arr[i][j]))) {
                    continue;
                } else if (arr[i][j + 1] == char(tolower(arr[i][j]) - 1) && (arr[i][j] != 'a' && arr[i][j] != 'A')) {
                    continue;
                }
            }
            ans[i] = true;
            break;
        }
    }
    for (int i = 0; i < num; i++) {
        if (ans[i]) {
            cout << "N" << endl;
        } else {
            cout << "Y" << endl;
        }
    }
    return 0;
}

L1-7 矩阵列平移

给定一个 n×n 的整数矩阵。对任一给定的正整数 k

输入格式：
输入第一行给出 3 个正整数：n（<100）、k（

接下来 n 行，每行给出 n 个不超过 100 的正整数，为矩阵元素的值。数字间以空格分隔。

输出格式：
在一行中输出平移后第 1 到 n 行元素的和。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
7 2 99
11 87 23 67 20 75 89
37 94 27 91 63 50 11
44 38 50 26 40 26 24
73 85 63 28 62 18 68
15 83 27 97 88 25 43
23 78 98 20 30 81 99
77 36 48 59 25 34 22
输出样例：
440 399 369 421 302 386 428
样例解读

需要平移的是第 2、4、6 列。给定 k=2，应该将这三列顺次整体向下平移 1、2、1 位（如果有更多列，就应该按照 1、2、1、2 …… 这个规律顺次向下平移），顶端的空位用 99 来填充。平移后的矩阵变成：

11 99 23 99 20 99 89
37 87 27 99 63 75 11
44 94 50 67 40 50 24
73 38 63 91 62 26 68
15 85 27 26 88 18 43
23 83 98 28 30 25 99
77 78 48 97 25 81 22

思路：初始化col（列）数组和ks（平移行数）数组，之后对于第i个要平移的列，平移ks[i]个位置即可。

n, k, x = map(int, input().split())
arr = []
cols = []
count = 0
while True:
    if 2 * count + 1 >= n:
        break
    cols.append(2 * count + 1)
    count += 1
ks = []
count = 1
for i in range(len(cols)):
    if k == 1:
        ks.append(count)
        continue
    ks.append(count)
    count += 1
    if count > k:
        count = 1
for i in range(n):
    arr.append(list(map(int, input().split())))
for i in range(len(cols)):
    for j in range(n - 1, ks[i] - 1, -1):
        arr[j][cols[i]] = arr[j - ks[i]][cols[i]]
    for j in range(ks[i]):
        arr[j][cols[i]] = x
for i in range(n):
    print(sum(arr[i]), end='')
    if i != n - 1:
        print('', end=' ')

L1-8 均是素数

在给定的区间 [m,n] 内，是否存在素数 p、q、r（p

输入格式：
输入给出区间的两个端点 0

输出格式：
在一行中输出满足条件的素数三元组的个数。

输入样例：
1 35
输出样例：
10
样例解读

满足条件的 10 组解为：

2, 3, 5
2, 3, 7
2, 3, 13
2, 3, 17
2, 5, 7
2, 5, 13
2, 5, 19
2, 5, 31
2, 7, 23
2, 13, 17

思路：写个判素数的函数，首先得到区间内全部素数，之后三个for循环暴力破解即可。python超时7分，相同思路改写C++代码满分。

#include 
#include 

using namespace std;

bool isPrime(int num) {
    if (num == 1)
        return false;
    if (num == 2)
        return true;
    for (int i = 2; i <= sqrt(num); i++) {
        if (num % i == 0)
            return false;
    }
    return true;
}

int main() {
    int m, n, arr[1001], count = 0, ans = 0;
    cin >> m >> n;
    for (int i = m; i <= n; i++){
        if(isPrime(i))
            arr[count++] = i;
    }
    for (int i = 0; i < count; i++){
        for (int j = i + 1; j < count; j++){
            for (int k = j + 1; k < count; k++){
                if ((isPrime(arr[i] * arr[j] + arr[k])) && (isPrime(arr[i] * arr[k] + arr[j])) && (isPrime(arr[k] * arr[j] + arr[i])))
                    ans ++;
            }
        }
    }
    cout << ans;
    return 0;
}

L2-1 盲盒包装流水线

众所周知，PAT 有 9 枚徽章，分别对应青铜、白银、黄金、白金、钻石、大师、王者、大圣、天神这 9 个段位，只有成绩非常优秀的考生才有资格获得刻有自己名字的徽章。现在，PAT 制作了徽章的小型纪念版，要制成盲盒给大家玩了！

下图是一条盲盒包装流水线的示意图。首先徽章通过进货口被压入货栈里，空盒在履带上从左向右传送。每次从货栈里d出一枚徽章，进入打包机，装入一只空盒，打包后继续向右边传送。当货栈为空时，打包机会暂停，等待下一批徽章压入货栈。

每只盒子都有一个编号，小拼姐姐手里有进入流水线的空盒编号顺序表，也有每一批送往货栈的徽章顺序表，这样她其实可以知道每只盒子里装了哪种徽章。有些小朋友收到了盲盒，就想在拆封前问无所不知的小拼姐姐，盒子里的徽章是哪一种。但是因为盲盒总量有 10
5
这么多，小拼姐姐可记不住每只盒子里装的是什么，于是你就被请来写个程序帮小拼姐姐回复这种信息。

输入格式：
输入第一行给出 2 个正整数，分别为盲盒总量 N（≤10
5
）和货栈容量 S（≤100）。接下来一行给出 N 只盒子的编号，编号由 5 位数字组成，给出的顺序是空盒进入传送带的顺序。随后 N/S（保证是整数）行，每行给出一批 S 枚徽章的类型，为 1-9 的数字，给出的顺序是从进货口入栈的顺序。

再下面给出一个正整数 K（≤10
4
），为查询次数。随后 K 行，每行给出一个 5 位编号。

输出格式：
对每个查询编号，在一行中输出该盒子中装的徽章类型。如果编号是错误的，则在一行中输出 Wrong Number。

输入样例：
10 5
00132 10093 92001 23333 66666 88888 09009 34658 82750 69251
1 2 3 4 5
9 8 7 6 1
5
66666
88888
69251
55555
10093
输出样例：
1
1
9
Wrong Number
4

思路：使用字典映射编号即可。

n, s = map(int, input().split())
boxes = input().split()
setB = set(boxes)
names = []
di = {}
for i in range(n // s):
    numbers = input().split()[::-1]
    for j in range(s):
        di[boxes[i * s + j]] = numbers[j]
k = int(input())
for i in range(k):
    item = input()
    print(di.get(item, "Wrong Number"))

L2-2 点赞狂魔

L2-2 点赞狂魔 (25 分)
微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：
输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F
1
​
⋯F
K
​
”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，F
i
​
（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 10
7
编号。数字间以空格分隔。

输出格式：
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：
5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14
输出样例：
jack chris john

思路：字典形式存储，sort函数按照双键排序即可。

n = int(input())
msg = []
for i in range(n):
    data = input().split()
    num = len(set(data[2:]))
    msg.append({
        "name": data[0],
        "num": num,
        "avg": num / len(data[2:])
    })
msg.sort(key=lambda x: (x['num'], x['avg']), reverse=True)
for i in range(3):
    if i < len(msg):
        print(msg[i]['name'], end='')
    else:
        print('-', end='')
    if i != 2:
        print('', end=' ')

L2-3 浪漫侧影

L2-2 点赞狂魔 (25 分)
微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：
输入在第一行给出一个正整数N（≤100），是待统计的用户数。随后N行，每行列出一位用户的点赞标签。格式为“Name K F
1
​
⋯F
K
​
”，其中Name是不超过8个英文小写字母的非空用户名，1≤K≤1000，F i（i=1,⋯,K）是特性标签的编号，我们将所有特性标签从 1 到 10
编号。数字间以空格分隔。

输出格式：
统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike jenny -就表示只有2人。

输入样例：
5
bob 11 101 102 103 104 105 106 107 108 108 107 107
peter 8 1 2 3 4 3 2 5 1
chris 12 1 2 3 4 5 6 7 8 9 1 2 3
john 10 8 7 6 5 4 3 2 1 7 5
jack 9 6 7 8 9 10 11 12 13 14
输出样例：
jack chris john

思路：后序遍历的顺序反过来，按照中序遍历各元素的位置建树，并使用队列层序编列即可。

def bfs(tree):
    q = [(tree, 0)]
    global ans
    while True:
        if not q:
            return
        node, i = q.pop()
        if i == len(ans):
            ans.append([])
        ans[i].append(node['value'])
        if node['left'] is not None:
            q.insert(0, (node['left'], i + 1))
        if node['right'] is not None:
            q.insert(0, (node['right'], i + 1))



n = int(input())
mid = list(map(int, input().split()))
last = list(map(int, input().split()))[::-1]
tree = {
    "left": None,
    "value": None,
    "right": None
}
for item in last:
    if tree['value'] is None:
        tree['value'] = item
    else:
        temp = tree
        while True:
            if mid.index(item) < mid.index(temp['value']):
                if temp['left'] is None:
                    temp['left'] = {
                        "left": None,
                        "value": item,
                        "right": None
                    }
                    break
                else:
                    temp = temp['left']
            else:
                if temp['right'] is None:
                    temp['right'] = {
                        "left": None,
                        "value": item,
                        "right": None
                    }
                    break
                else:
                    temp = temp['right']
ans = []
bfs(tree)
print("R: ", end='')
for i, item in enumerate(ans):
    print(item[-1], end='')
    if i != len(ans) - 1:
        print(' ', end='')
print()
print("L: ", end='')
for i, item in enumerate(ans):
    print(item[0], end='')
    if i != len(ans) - 1:
        print(' ', end='')

L2-4 哲哲打游戏

哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N 个剧情点，通过游戏里不同的 *** 作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行 *** 作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏 *** 作，请你输出哲哲的游戏进度。

输入格式：
输入第一行是两个正整数 N 和 M (1≤N,M≤10
5
)，表示总共有 N 个剧情点，哲哲有 M 个游戏 *** 作。

接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是 K
i
​
，表示剧情点 i 通过一些 *** 作或选择能去往下面 K
i
​
个剧情点；接下来有 K
i
​
个数字，第 k 个数字表示做第 k 个 *** 作或选择可以去往的剧情点编号。

最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：

0 表示哲哲做出了某个 *** 作或选择，后面紧接着一个数字 j，表示哲哲在当前剧情点做出了第 j 个选择。我们保证哲哲的选择永远是合法的。
1 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j 个档位上。
2 表示哲哲进行了一次读取存档的 *** 作，后面紧接着是一个数字 j，表示读取了放在第 j 个位置的存档。
约定：所有 *** 作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100 个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即 ∑K
i
​
）不超过 10
6
。

输出格式：
对于每个 1（即存档） *** 作，在一行中输出存档的剧情点编号。

最后一行输出哲哲最后到达的剧情点编号。

输入样例：
10 11
3 2 3 4
1 6
3 4 7 5
1 3
1 9
2 3 5
3 1 8 5
1 9
2 8 10
0
1 1
0 3
0 1
1 2
0 2
0 2
2 2
0 3
0 1
1 1
0 2
输出样例：
1
3
9
10
样例解释：
简单给出样例中经过的剧情点顺序：

1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。

档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9 号剧情点。

思路：存储剧情点信息后，按照输出执行 *** 作即可。

n, m = map(int, input().split())
ways = []
saves = [0 for i in range(100)]
for i in range(n):
    ways.append(list(map(int, input().split()[1:])))
now = 0
for i in range(m):
    a, b = map(int, input().split())
    if a == 1:
        saves[b - 1] = now
        print(now + 1)
    elif a == 2:
        now = saves[b - 1]
    else:
        now = ways[now][b - 1] - 1
print(now + 1)

L3-1 直捣黄龙

本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式：
输入第一行给出2个正整数N（2 ≤ N ≤ 200，城镇总数）和K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后N-1行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有K行，每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由3个大写英文字母组成的字符串。

输出格式：
按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->…->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以1个空格分隔，行首尾不得有多余空格。

输入样例：
10 12 PAT DBY
DBY 100
PTA 20
PDS 90
PMS 40
TAP 50
ATP 200
LNN 80
LAO 30
LON 70
PAT PTA 10
PAT PMS 10
PAT ATP 20
PAT LNN 10
LNN LAO 10
LAO LON 10
LON DBY 10
PMS TAP 10
TAP DBY 10
DBY PDS 10
PDS PTA 10
DBY ATP 10
输出样例：
PAT->PTA->PDS->DBY
3 30 210

思路：迪杰斯特拉寻找最短路径，加上消灭敌人数以及城镇数的限制条件，并添加road数组，使用状态转移思想（递推）存储路径条数即可。

def Dijkstra(s, e, g, n):
    global c, d
    path = [None for i in range(n)]
    kill = [0 for i in range(n)]
    node = [0 for i in range(n)]
    dist = [1e9 for i in range(n)]
    visited = [False for i in range(n)]
    road = [0 for i in range(n)]
    dist[n - 1] = 0
    # 起始点
    visited[n - 1] = True
    for key, value in g[s].items():
        index = c[key]
        dist[index] = value
        kill[index] = p[c[key]]
        node[index] = 1
        path[index] = s
        road[index] = 1
    while True:
        Min, v = 1e9, c[s]
        for i in range(n):
            if not visited[i] and dist[i] < Min:
                Min = dist[i]
                v = i
        if v == c[e]:
            break
        visited[v] = True
        for i in range(n):
            temp1, temp2 = d[v], d[i]
            try:
                temp = g[temp1][temp2]
            except:
                continue
            if (not visited[i]) and g[temp1][temp2] + Min <= dist[i]:
                if g[temp1][temp2] + Min < dist[i]:
                    dist[i] = g[temp1][temp2] + Min
                    node[i] = node[v] + 1
                    kill[i] = kill[v] + p[i]
                    path[i] = d[v]
                    road[i] = road[v]
                else:
                    road[i] += road[v]
                    if node[v] + 1 >= node[i]:
                        if node[v] + 1 > node[i]:
                            kill[i] = kill[v] + p[i]
                            node[i] = node[v] + 1
                            path[i] = d[v]
                        else:
                            if kill[v] + p[i] > kill[i]:
                                kill[i] = kill[v] + p[i]
                                path[i] = d[v]
    find(path, e)
    print(e)
    print(road[c[e]], dist[c[e]], kill[c[e]])

def find(path, index):
    _temp = c[index]
    if path[_temp] is not None:
        find(path, path[_temp])
        print(path[_temp], end='->')

n, k, start, end = input().split()
n = int(n)
k = int(k)
# string映射到int
c = dict()
# int映射到string
d = dict()
p = []
c[start] = n - 1
d[n - 1] = start
for i in range(n - 1):
    a, b = input().split()
    c[a] = i
    d[i] = a
    p.append(int(b))
p.append(0)
graph = dict()
for i in range(k):
    a, b, e = input().split()
    try:
        graph[a][b] = int(e)
    except:
        graph[a] = dict()
        graph[a][b] = int(e)
    try:
        graph[b][a] = int(e)
    except:
        graph[b] = dict()
        graph[b][a] = int(e)
Dijkstra(start, end, graph, n)

L3-2 拼题A打卡奖励

拼题 A 的教超搞打卡活动，指定了 N 张打卡卷，第 i 张打卡卷需要 m
i
​
分钟做完，完成后可获得 c
i
​
枚奖励的金币。活动规定每张打卡卷最多只能做一次，并且不允许提前交卷。活动总时长为 M 分钟。请你算出最多可以赢得多少枚金币？

输入格式：
输入首先在第一行中给出两个正整数 N（≤10
3
） 和 M（≤365×24×60），分别对应打卡卷的数量和以“分钟”为单位的活动总时长（不超过一年）。随后一行给出 N 张打卡卷要花费的时间 m
i
​
（≤600），最后一行给出 N 张打卡卷对应的奖励金币数量 c
i
​
（≤30）。上述均为正整数，一行内的数字以空格分隔。

输出格式：
在一行中输出最多可以赢得的金币数量。

输入样例：
5 110
70 10 20 50 60
28 1 6 18 22
输出样例：
40
样例解释：
选择最后两张卷子，可以在 50+60=110 分钟内获得 18+22=40 枚金币。

思路：使用value/time，量化每张卷子的价值，过程中将time大于最长市场m的卷子value置为0。之后按照量化后的价值降序贪心即可。

n, m = map(int, input().split())
times = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
    if times[i] > m:
        c[i] = 0
if n == 1:
    print(c[0])
else:
    temp = [{"value": c[i] / times[i], "index": i} for i in range(n)]
    values = sorted(temp, key=lambda x: x['value'], reverse=True)
    ans = 0
    for i in range(n):
        temp = times[values[i]['index']]
        temp1 = c[values[i]['index']]
        for j in range(i + 1, n):
            temp += times[values[j]['index']]
            temp1 += c[values[j]['index']]
            if temp > m:
                temp -= times[values[j]['index']]
                temp1 -= c[values[j]['index']]
                continue
            if temp1 > ans:
                ans = temp1
            if temp == m:
                break
    print(ans)

L3-3 可怜的简单题

九条可怜去年出了一道题，导致一众参赛高手惨遭团灭。今年她出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:

最开始，数列 A 为空。

可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。

如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w 的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，继续增加 A 的长度。

现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。

输入格式：
输入一行两个整数 n,p (1≤n≤10
11
,n 12
)，p 是一个质数。

输出格式：
在一行中输出一个整数，表示答案对 p 取模的值。具体来说，假设答案的最简分数表示为
y
x
​
，你需要输出最小的非负整数 z 满足 y×z≡x mod p。

输入样例 1：
2 998244353
输出样例 1：
2
输入样例 2：
100000000 998244353
输出样例 2：
3056898

思路：数学题，不会，骗分开摆。

a, b = input().split()
print(a)