福
福

雨辰枫司的小栈

2024天梯赛题目与个人题解（python）

  • ~24.11K 字
  • 条评论
  1. 1. L1-1 编程解决一切
  2. 2. L1-2 再进去几个人
  3. 3. L1-3 帮助色盲
  4. 4. L1-4 四项全能
  5. 5. L1-5 别再来这么多猫娘了！
  6. 6. L1-6 兰州牛肉面
  7. 7. L1-7 整数的持续性
  8. 8. L1-8 九宫格
  9. 9. L2-1 鱼与熊掌
  10. 10. L2-2 懂蛇语
  11. 11. L2-3 满树的遍历
  12. 12. L2-4 吉利矩阵
  13. 13. L3-1 夺宝大赛
  14. 14. L3-2 工业园区建设
  15. 15. L3-3 攀岩

L1-1 编程解决一切

题目

描述

编程解决一切 —— 本题非常简单，就请你直接在屏幕上输出这句话：Problem? The Solution: Programming.。

输入格式：
在一行中输出 Problem? The Solution: Programming.。

输入样例：

1
无

输出样例：

1
Problem? The Solution: Programming.

个人题解：

啊这，print就完了。 
1
print("Problem? The Solution: Programming.")

L1-2 再进去几个人

题目

描述

数学家、生物学家和物理学家坐在街头咖啡屋里，看着人们从街对面的一间房子走进走出。他们先看到两个人进去。时光流逝。他们又看到三个人出来。

物理学家:“测量不够准确。”

生物学家:“他们进行了繁殖。”

数学家:“如果现在再进去一个人，那房子就空了。”

下面就请你写个程序，根据进去和出来的人数，帮数学家算出来，再进去几个人，那房子就空了。

输入格式：
输入在一行中给出 2 个不超过 100 的正整数 A 和 B，其中 A 是进去的人数，B 是出来的人数。题目保证 B 比 A 要大。

输出格式：
在一行中输出使得房子变空的、需要再进去的人数。

输入样例：

1
4 7

输出样例：

1
3

个人题解：

看样例似乎就是 B - A

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

L1-3 帮助色盲

题目

描述

在古老的红绿灯面前，红绿色盲患者无法分辨当前亮起的灯是红色还是绿色，有些聪明人通过路口的策略是这样的：当红灯或绿灯亮起时，灯的颜色无法判断，但前方两米内有同向行走的人，就跟着前面那人行动，人家走就跟着走，人家停就跟着停；如果当前是黄灯，那么很快就要变成红灯了，于是应该停下来。麻烦的是，当灯的颜色无法判断时，前方两米内没有人……

本题就请你写一个程序，通过产生不同的提示音来帮助红绿色盲患者判断当前交通灯的颜色；但当患者可以自行判断的时候（例如黄灯或者前方两米内有人），就不做多余的打扰。具体要求的功能为：当前交通灯为红灯或绿灯时，检测其前方两米内是否有同向行走的人 —— 如果有，则患者自己可以判断，程序就不做提示；如果没有，则根据灯的颜色给出不同的提示音。黄灯也不需要给出提示。

输入格式：

输入在一行中给出两个数字 A 和 B，其间以空格分隔。其中 A 是当前交通灯的颜色，取值为 0 表示红灯、1 表示绿灯、2 表示黄灯；B 是前方行人的状态，取值为 0 表示前方两米内没有同向行走的人、1 表示有。

输出格式：

根据输入的状态在第一行中输出提示音：dudu 表示前方为绿灯，可以继续前进；biii 表示前方为红灯，应该止步；- 表示不做提示。在第二行输出患者应该执行的动作：move 表示继续前进、stop 表示止步。

输入样例1：

1
0 0

输出样例1：

1
2
biii
stop

输入样例2：

1
1 1

输出样例2：

1
2
-
move

个人题解：

根据题目写条件，模拟就完了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
a, b = map(int,input().split())

# 如果不为黄灯
if a != 2:
    # 当前面有人
    if b:
        print("-")
        # 其他行人不是色盲（不是）
        if a == 0:
            print("stop")
        else:
            print("move")
    # 当前面没人
    else:
        # 为红灯
        if a == 0:
            print("biii")
            print("stop")
        # 为绿灯
        else:
            print("dudu")
            print("move")
# 为黄灯
else:
    print("-")
    print("stop")

L1-4 四项全能

题目

描述

新浪微博上有一个帖子给出了一道题：全班有 50 人，有 30 人会游泳，有 35 人会篮球，有 42 人会唱歌，有 46 人会骑车，至少有（ ）人四项都会。

发帖人不会做这道题，但是回帖有会做的：每一个才艺是一个技能点，一共是 30 + 35 + 42 + 46 = 153 个技能点，50 个人假设平均分配，每人都会 3 个技能那也只有 150，所以至少有 3 人会四个技能。

本题就请你写个程序来自动解决这类问题：给定全班总人数为 n，其中有 m 项技能，分别有 、、、 个人会，问至少有多少人 m 项都会。

输入格式：

输入在第一行中给出 2 个正整数：（） 和 （），分别对应全班人数和技能总数。随后一行给出 个不超过 的正整数，其中第 个整数对应会第 项技能的人数。

输出格式：

输出至少有多少人 m 项都会。

输入样例：

1
2
50 4
30 35 42 46

输出样例：

1
3

个人题解：

就是一个计算问题，假设项人全部都会，人数为 ，剩下的人肯定是会第 项的，所以至少有 人全都会。当时没考虑到会有0人的情况看了半天不知道哪里错了。

1
2
3
4
5
6
7
n, m = map(int,input().split())

ability = list(map(int,input().split()))

## 假设前(m - 1)项全部人都会，剩下的人数就是第n项会的人
ans = sum(ability) - (m - 1) * n
print(ans if ans > 0 else 0)

L1-5 别再来这么多猫娘了！

题目

描述

以 GPT 技术为核心的人工智能系统出现后迅速引领了行业的变革，不仅用于大量的语言工作（如邮件编写或文章生成等工作），还被应用在一些较特殊的领域——例如去年就有同学尝试使用 ChatGPT 作弊并被当场逮捕（全校被取消成绩）。相信聪明的你一定不会犯一样的错误！

言归正传，对于 GPT 类的 AI，一个使用方式受到不少年轻用户的欢迎——将 AI 变成猫娘：

部分公司使用 AI 进行网络营销，网友同样乐于使用“变猫娘”的方式进行反击。注意：图中内容与题目无关，如无法看到图片不影响解题。

当然，由于训练数据里并不区分道德或伦理倾向，因此如果不加审查，AI 会生成大量的、不一定符合社会公序良俗的内容。尽管关于这个问题仍有争论，但至少在比赛中，我们还是期望 AI 能用于对人类更有帮助的方向上，少来一点猫娘。

因此你的工作是实现一个审查内容的代码，用于对 AI 生成的内容的初步审定。更具体地说，你会得到一段由大小写字母、数字、空格及 ASCII 码范围内的标点符号的文字，以及若干个违禁词以及警告阈值，你需要首先检查内容里有多少违禁词，如果少于阈值个，则简单地将违禁词替换为<censored>；如果大于等于阈值个，则直接输出一段警告并输出有几个违禁词。

输入格式：

输入第一行是一个正整数 ，表示违禁词的数量。接下来的 行，每行一个长度不超过 10 的、只包含大小写字母、数字及 ASCII 码范围内的标点符号的单词，表示应当屏蔽的违禁词。

然后的一行是一个非负整数 ，表示违禁词的阈值。

最后是一行不超过 5000 个字符的字符串，表示需要检查的文字。

从左到右处理文本，违禁词则按照输入顺序依次处理；对于有重叠的情况，无论计数还是替换，查找完成后从违禁词末尾继续处理。

输出格式：

如果违禁词数量小于阈值，则输出替换后的文本；否则先输出一行一个数字，表示违禁词的数量，然后输出He Xie Ni Quan Jia!。

输入样例1：

1
2
3
4
5
6
7
8
5
MaoNiang
SeQing
BaoLi
WeiGui
BuHeShi
4
BianCheng MaoNiang ba! WeiGui De Hua Ye Keyi Shuo! BuYao BaoLi NeiRong.

输出样例1：

1
BianCheng <censored> ba! <censored> De Hua Ye Keyi Shuo! BuYao <censored> NeiRong.

输入样例2：

1
2
3
4
5
6
7
8
5
MaoNiang
SeQing
BaoLi
WeiGui
BuHeShi
3
BianCheng MaoNiang ba! WeiGui De Hua Ye Keyi Shuo! BuYao BaoLi NeiRong.

输出样例2：

1
2
3
He Xie Ni Quan Jia!

输入样例3：

1
<censored>A<censored>B

输出样例3：

1
<censored>A<censored>B

输入样例4：

1
2
3
4
5
2
AB
BB
3
AAABBB

输出样例4：

1
AA<censored><censored>

输入样例5：

1
2
3
4
5
2
BB
AB
3
AAABBB

输出样例5：

1
AAA<censored>B

个人题解：

😀 猫娘，快变( •ᴗ• )。 查找替换的模拟题，但有两个测试点超时，当时以为是违禁词是替换词的子串（没想到还猜对了，可惜当时没有想到合适的方法），这里就先放着当时的代码吧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 4 10 超时
n = int(input())

# 存放违禁词的数组
strArr = []
while n:
    n -= 1
    strArr.append(input())

k = int(input())
s = input()
# 违禁词的数量
error_word = 0

for word in strArr:
    index = 0
    word_len = len(word)
    error_word_arr = []
    while index != -1:
        index = s.find(word)
        if index != -1:
            # 拼接字符串
            s = s[:index] + "<censored>" + s[index + word_len:]
            error_word += 1

if error_word < k:
    print(s)
else:
    print(error_word)
    print("He Xie Ni Quan Jia!")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n = int(input())

# 存放违禁词的数组
strArr = []
while n:
    n -= 1
    strArr.append(input())

k = int(input())
s = input()
# 违禁词的数量
error_word = 0
# 待替换的字符串
temp_error_word = "(*-*)"

for word in strArr:
    index = 0
    word_len = len(word)
    error_word_arr = []
    while index != -1:
        index = s.find(word)
        if index != -1:
            # 拼接字符串
            s = s[:index] + temp_error_word + s[index + word_len:]
            error_word += 1

if error_word < k:
    #  将字符串替换回来
    print(s.replace(temp_error_word,"<censored>"))
else:
    print(error_word)
    print("He Xie Ni Quan Jia!")

L1-6 兰州牛肉面

题目

描述

兰州牛肉面是历史悠久的美食，根据牛肉面的宽窄、配料的种类，可以细分为上百个不同的品种。你进到兰州的任何一家牛肉面馆，只说：“来一碗牛肉面！”就好像进到加州的咖啡馆说“来一杯咖啡”一样，会被店主人当成外星人……

本题的任务是，请你写程序帮助一家牛肉面馆的老板统计一下，他们一天卖出各种品种的牛肉面有多少碗，营业额一共有多少。

输入格式：

输入第一行给出一个正整数 （），为牛肉面的种类数量。这里为了简单起见，我们把不同种类的牛肉面从 1 到 编号，以后就用编号代替牛肉面品种的名称。第二行给出 个价格，第 个价格对应第 种牛肉面一碗的单价。这里的价格是 区间内的实数，以元为单位，精确到分。

随后是一天内客人买面的记录，每条记录占一行，格式为：

1
品种编号 碗数

其中碗数保证是正整数。当对应的品种编号为0时，表示输入结束。这个记录不算在内。

输出格式：

首先输出 行，第 行输出第 种牛肉面卖出了多少碗。最后一行输出当天的总营业额，仍然是以元为单位，精确到分。题目保证总营业额不超过 。

输入样例：

1
2
3
4
5
6
7
8
9
5
4.00 8.50 3.20 12.00 14.10
3 5
5 2
1 1
2 3
2 2
1 9
0 0

输出样例：

1
2
3
4
5
6
10
5
5
0
2
126.70

个人题解：

根据题目要求进行计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
n = int(input())
# 价格数组
priceArr = list(map(float,input().split()))
# 出售编号与碗数 { 编号: 碗数 }
sell = {}

id, num = map(int, input().split())
while id != 0:
    sell[id] = sell.get(id,0) + num
    id, num = map(int, input().split())

sum_ = 0
for i in range(n):
    sum_ += sell.get(i + 1, 0) * priceArr[i]
    print(sell.get(i + 1, 0))

print(f"{sum_:.2f}")

L1-7 整数的持续性

题目

描述

从任一给定的正整数出发，将其每一位数字相乘，记得到的乘积为。以此类推，令为​的各位数字的乘积，直到最后得到一个个位数，则就称为的持续性。例如的持续性就是，因为我们从开始，得到，随后得到、、，最后得到，一共用了步。

本题就请你编写程序，找出任一给定区间内持续性最长的整数。

输入格式：

输入在一行中给出两个正整数和（且），为给定区间的两个端点。

输出格式：

首先在第一行输出区间内整数最长的持续性。随后在第二行中输出持续性最长的整数。如果这样的整数不唯一，则按照递增序输出，数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

1
500 700

输出样例：

1
2
5
679 688 697

个人题解：

这就是一个持续性函数的编写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
a,b = map(int, input().split())

def getWeight(num):
    # 转成字符串好处理
    num = str(num)
    if len(num) == 1:
        return 0
    weight = 1
    for i in num:
        weight *= int(i)
    return getWeight(weight) + 1

max_weight = -1
ans = []

for i in range(a, b + 1):
    weight = getWeight(i)
    if weight > max_weight:
        max_weight = weight
        ans = [i]
    elif weight == max_weight:
        ans.append(i)

print(max_weight)
print(" ".join(list(map(str,ans))))

L1-8 九宫格

描述

题目

九宫格是一款数字游戏，传说起源于河图洛书，现代数学中称之为三阶幻方。游戏规则是：将一个的正方形区域划分为个的正方形宫位，要求到这九个数字中的每个数字在每一行、每一列、每个宫位中都只能出现一次。

本题并不要求你写程序解决这个问题，只是对每个填好数字的九宫格，判断其是否满足游戏规则的要求。

输入格式：

输入首先在第一行给出一个正整数（），随后给出个填好数字的九宫格。每个九宫格分行给出，每行给出个数字，其间以空格分隔。

输出格式：

对每个给定的九宫格，判断其中的数字是否满足游戏规则的要求。满足则在一行中输出，否则输出。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
3
5 1 9 2 8 3 4 6 7
7 2 8 9 6 4 3 5 1
3 4 6 5 7 1 9 2 8
8 9 2 1 4 5 7 3 6
4 7 3 6 2 8 1 9 5
6 5 1 7 3 9 2 8 4
9 3 4 8 1 6 5 7 2
1 6 7 3 5 2 8 4 9
2 8 5 4 9 7 6 1 3
8 2 5 4 9 7 1 3 6
7 9 6 5 1 3 8 2 4
3 4 1 6 8 2 7 9 5
6 8 4 2 7 1 3 5 9
9 1 2 8 3 5 6 4 7
5 3 7 9 6 4 2 1 8
2 7 9 1 5 8 4 6 3
4 5 8 3 2 6 9 7 1
1 6 3 7 4 9 5 8 3
81 2 5 4 9 7 1 3 6
7 9 6 5 1 3 8 2 4
3 4 1 6 8 2 7 9 5
6 8 4 2 7 1 3 5 9
9 1 2 8 3 5 6 4 7
5 3 7 9 6 4 2 1 8
2 7 9 1 5 8 4 6 3
4 5 8 3 2 6 9 7 1
1 6 3 7 4 9 5 8 2

输出样例：

1
2
3
1
0
0

个人题解：

遍历就完了，主要是拆分成小网格比较麻烦，当时就列举了9个网格可还行😂。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
n = int(input())
N = 100005

def minMap(m):
    ans = [0] * N
    for i in range(3):
        for j in range(3):
            ans[m[i][j]] = 1
    return sum(ans[1:10]) == 9

def map9(m):
    for i in range(3):
        for j in range(3):
            nm = []
            for k in range(3):
                nm.append(m[k + (i * 3)][j * 3:(j + 1)*3])
        if not minMap(nm):
            return False
    for i in range(9):
        ans1 = [0] * N
        ans2 = [0] * N
        for j in range(9):
            ans1[m[i][j]] = 1
            ans2[m[j][i]] = 1
        if sum(ans1[1:10]) != 9 or sum(ans2[1:10]) != 9:
            return False
    return True

while n:
    n -= 1
    m = []
    for i in range(9):
        m.append(list(map(int,input().split())))
    print(1 if map9(m) else 0)

L2-1 鱼与熊掌

题目

描述

《孟子 · 告子上》有名言：“鱼，我所欲也，熊掌，亦我所欲也；二者不可得兼，舍鱼而取熊掌者也。”但这世界上还是有一些人可以做到鱼与熊掌兼得的。

给定个人对种物品的拥有关系。对其中任意一对物品种类（例如“鱼与熊掌”），请你统计有多少人能够兼得？

输入格式：

输入首先在第一行给出 2 个正整数，分别是：（）为总人数（所有人从 1 到 编号）、（）为物品种类的总数（所有物品种类从 到 编号）。

随后 行，第 行（）给出编号为 的人所拥有的物品种类清单，格式为：

1
K M[1] M[2] ... M[K]

其中（）是该人拥有的物品种类数量，后面的 M[*] 是物品种类的编号。题目保证每个人的物品种类清单中都没有重复给出的种类。最后是查询信息：首先在一行中给出查询总量（），随后行，每行给出一对物品种类编号，其间以空格分隔。题目保证物品种类编号都是合法存在的。

输出格式：

对每一次查询，在一行中输出两种物品兼得的人数。

输入样例：

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

输出样例：

1
2
3
2
0
3

个人题解：

将每种物品的拥有者放入一个集合，算出两个集合的交集，即为答案。（python的集合超时，试过用排序也超时了），是我哪里做的不好吗。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
## 2 3 4 测试点超时
n, m = map(int,input().split())

arr = {}
for i in range(n):
    l = list(map(int, input().split()))
    for j in range(1, l[0] + 1):
        if arr.get(l[j], False):
            arr[l[j]].append(i)
        else:
            arr[l[j]] = [i]

k = int(input())
while k:
    k -= 1
    a,b = map(int,input().split())
    print(len(set(arr[a]).intersection(arr[b])))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
## 同样 2 3 4 测试点超时
n, m = map(int,input().split())

arr = {}
for i in range(m):
    arr[i] = []

for i in range(n):
    l = list(map(int, input().split()))
    for j in range(1, l[0] + 1):
        arr[l[j]].append(i)

for i in range(m):
    if arr.get(i, False):
        arr[i].sort()

k = int(input())
while k:
    k -= 1
    a,b = map(int,input().split())
    l1,l2 = arr[a],arr[b]
    i,j,ans = 0,0,0
    len_l1,len_l2 = len(l1),len(l2)
    while i < len_l1 and j < len_l2:
        if l1[i] == l2[j]:
            i += 1
            j += 1
            ans += 1
        elif l1[i] > l2[j]:
            j += 1
        else:
            i += 1
    print(ans)

L2-2 懂蛇语

题目

描述

在《一年一度喜剧大赛》第二季中有一部作品叫《警察和我之蛇我其谁》，其中“毒蛇帮”内部用了一种加密语言，称为“蛇语”。蛇语的规则是，在说一句话 A 时，首先提取 A 的每个字的首字母，然后把整句话替换为另一句话 B，B 中每个字的首字母与 A 中提取出的字母依次相同。例如二当家说“九点下班哈”，对应首字母缩写是 JDXBH，他们解释为实际想说的是“京东新百货”……

本题就请你写一个蛇语的自动翻译工具，将输入的蛇语转换为实际要表达的句子。

输入格式：

输入第一行给出一个正整数（），为蛇语词典中句子的个数。随后 行，每行用汉语拼音给出一句话。每句话由小写英文字母和空格组成，每个字的拼音由不超过 6 个小写英文字母组成，两个字的拼音之间用空格分隔。题目保证每句话总长度不超过 50 个字符，用回车结尾。注意：回车不算句中字符。

随后在一行中给出一个正整数 （），为查询次数。后面跟 行，每行用汉语拼音给出需要查询的一句话，格式同上。

输出格式：

对每一句查询，在一行中输出其对应的句子。如果句子不唯一，则按整句的字母序输出，句子间用 | 分隔。如果查不到，则将输入的句子原样输出。

注意：输出句子时，必须保持句中所有字符不变，包括空格。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
yong yuan de shen
yong yuan de she
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
yi  dian dian
ni hui shuo she yu a
yong yuan de sha
7
jiu dian xia ban ha
shao ye wu ya he shui you dian duo
liu wan bu yao ci dao
ni hai shi su yan a
yao diao deng
sha ye ting bu jian
y y d s

输出样例：

1
2
3
4
5
6
7
jing dong xin bai huo
she yu wo ye hui shuo yi dian dian
liang wei bu yao chong dong
ni hui shuo she yu a
yi  dian dian
sha ye ting bu jian
yong yuan de sha|yong yuan de she|yong yuan de shen

个人题解：

一存一查，按照字典查到的数据排序输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
n = int(input())
# 存蛇语的对象 { 蛇语: 对应的数组 }
work = {}

def get_snake_work(s):
    snake_work = ""
    for i in s.split():
        snake_work += i[0]
    return snake_work

while n:
    n -= 1
    s = input()
    snake_work = get_snake_work(s)
    if work.get(snake_work,False):
        work[snake_work].append(s)
    else:
        work[snake_work] = [s]

m = int(input())
while m:
    m -= 1
    s = input()
    snake_work = get_snake_work(s)
    if work.get(snake_work, False):
        work[snake_work].sort()
        print("|".join(work[snake_work]))
    else:
        print(s)

L2-3 满树的遍历

题目

描述

一棵“阶满树”是指树中所有非叶结点的度都是 的树。给定一棵树，你需要判断其是否为 阶满树，并输出其前序遍历序列。

注：树中结点的度是其拥有的子树的个数，而树的度是树内各结点的度的最大值。

输入格式：

输入首先在第一行给出一个正整数 （），是树中结点的个数。于是设所有结点从 到 编号。随后 行，第 行（）给出第 个结点的父结点编号。根结点没有父结点，则对应的父结点编号为 0。题目保证给出的是一棵合法多叉树，只有唯一根结点。

输出格式：

首先在一行中输出该树的度。如果输入的树是阶满树，则加个空格后输出yes，否则输出no。最后在第二行输出该树的前序遍历序列，数字间以 1 个空格分隔，行首尾不得有多余空格。

注意：兄弟结点按编号升序访问。

输入样例1：

1
2
3
4
5
6
7
8
7
6
5
5
6
6
0
5

输出样例1：

1
2
3 yes
6 1 4 5 2 3 7

输入样例2：

1
2
3
4
5
6
7
8
7
6
5
5
6
6
0
4

输出样例2：

1
2
3 no
6 1 4 7 5 2 3

个人题解：

根据题目进行模拟即可，由根节点知道为多少，然后深搜遍历每一个节点判断其度是不是为。最后是正常的先序遍历，因为节点是由低到高加入的，所以不需要排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
n = int(input())
## 树
tree = {}

for i in range(1, n + 1):
    father_node = int(input())
    if tree.get(father_node, False):
        tree[father_node].append(i)
    else:
        tree[father_node] = [i]

# tree[0]是根节点数组，tree[0][0]就是root
root = tree[0][0]
# 根节点至少有k个节点，由此得到k，可能k为0，所以没有子节点
k = len(tree.get(root, []))

def isKTree(node):
    # 如果节点没有子树就返回False
    if not tree.get(node, False):
        return True
    # 如果度不为k就返回False
    if len(tree[node]) != k:
        return False
    # 遍历子树
    for i in tree[node]:
        if not isKTree(i):
            return False
    return True

print(k, "yes" if isKTree(root) else "no")

# 先序遍历
flag = True
def printNode(node):
    global flag
    if flag:
        flag = False
    else:
        print(" ",end="")
    print(node,end="")

def precedent(node):
    # 先根
    printNode(node)
    # 在节点
    if tree.get(node, False):
        for i in tree[node]:
            precedent(i)

precedent(root)

L2-4 吉利矩阵

题目

描述

所有元素为非负整数，且各行各列的元素和都等于 的 方阵称为“吉利矩阵”，因为这样的矩阵一共有 种。

本题就请你统计一下，把 换成任何一个 区间内的正整数 L，把矩阵阶数换成任何一个 区间内的正整数 ，满足条件“所有元素为非负整数，且各行各列的元素和都等于 的 方阵一共有多少种？

输入格式：

输入在一行中给出 个正整数 和 ，意义如题面所述。数字间以空格分隔。

输出格式：

在一行中输出满足题目要求条件的方阵的个数。

输入样例：

1
7 3

输出样例：

1
666

个人题解：

剪枝什么的不会啦，还超时，不如打表来的快。 （看我空间换时间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# 4 超时 (9 4 耗时 81.80609345436096s 时机已到、今日起兵！打表去 ~)
l, n = map(int, input().split())
ans = 0
r_ = [0] * 10
l_ = [0] * 10

# x: 横轴索引，y: 纵轴索引
def dfs(x, y):
    global ans
    # 如果超出边界，就将结果加一并返回
    if x > n or y > n:
        ans += 1
        return
    # 如果当前值已超出范围，之后都会超出，直接返回
    if l_[x] > l or r_[y] > l:
        return
    # 遍历所有情况，因为和要等于L，所以最大值为L
    for i in range(l + 1):
        if x == n and r_[y] + i != l:
            continue
        if y == n and l_[x] + i != l:
            continue
        if l_[x] + i <= l and r_[y] + i <= l:
            # 将当前位置的值加上i
            l_[x] += i
            r_[y] += i
            # 递归
            dfs(x + (y // n), y % n + 1)
            # 回溯
            l_[x] -= i
            r_[y] -= i

import time
start_time = time.time()
dfs(1,1)
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
l, n = map(str, input().split())
map_ = {
    "22": 3,
    "23": 21,
    "24": 282,
    "32": 4,
    "33": 55,
    "34": 2008,
    "42": 5,
    "43": 120,
    "44": 10147,
    "52": 6,
    "53": 231,
    "54": 40176,
    "62": 7,
    "63": 406,
    "64": 132724,
    "72": 8,
    "73": 666,
    "74": 381424,
    "82": 9,
    "83": 1035,
    "84": 981541,
    "92": 10,
    "93": 1540,
    "94": 2309384
}
print(map_[l+n])

L3-1 夺宝大赛

题目

描述

夺宝大赛的地图是一个由 个方格子组成的长方形，主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里，同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格（“相邻”是指两个方格有一条公共边）所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时，必将发生火拼，造成参与火拼的所有队伍无法继续比赛。大赛规定：最先到达大本营并能活着夺宝的队伍获得胜利。

假设所有队伍都将以最快速度冲向大本营，请你判断哪个队伍将获得最后的胜利。

输入格式：

输入首先在第一行给出两个正整数 和 （），随后 行，每行给出 个数字，表示地图上对应方格的状态： 表示方格可通过； 表示该方格有障碍物，不可通行； 表示该方格是大本营。题目保证只有 1 个大本营。

接下来是参赛队伍信息。首先在一行中给出正整数 （），随后 k 行，第 （）行给出编号为 的参赛队的初始落脚点的坐标，格式为 x y。这里规定地图左上角坐标为 1 1，右下角坐标为 n m，其中 n 为列数，m 为行数。注意参赛队只能在地图范围内移动，不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。

输出格式：

在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量，数字间以 1 个空格分隔，行首尾不得有多余空格。若没有队伍能获胜，则在一行中输出 No winner.

输入样例1：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
1 5
7 1
1 1
5 5
3 1
3 5
1 4

输出样例1：

1
7 6

样例 1 说明：

七支队伍到达大本营的时间顺次为：7、不可能、5、3、3、5、6，其中队伍 4 和 5 火拼了，队伍 3 和 6 火拼了，队伍 7 比队伍 1 早到，所以获胜。

输入样例 2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5

输出样例2：

1
No winner.

个人题解：

一眼看到感觉难度应该挺高的，题目又是小作文，立马摆了。后来有人告诉我bfs就可以解决，仔细一看发现这题是个多源最短路问题。（深搜不知道哪里有问题）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
64
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
## 广搜
# 最大 y 和 x
maxy,maxx = map(int,input().split())

# 地图
map_ = []
# 最大权值
MAX_WIGHT = 1000005

# 输入地图
for i in range(maxy):
    map_.append(list(map(int,input().split())))

# boss 为大本营位置
boss = [0, 0]
# 移动方向
move = [[0,1],[0,-1],[1,0],[-1,0]]

# 将所有能走的点赋值为 MAX_WIGHT， 不能走的为 -1，为之后搜索做准备
for i in range(maxy):
    for j in range(maxx):
        if map_[i][j] == 1:
            map_[i][j] = MAX_WIGHT
        elif map_[i][j] == 2:
            boss[0], boss[1] = i, j
            map_[i][j] = MAX_WIGHT
        elif map_[i][j] == 0:
            map_[i][j] == -1

# 广搜队列
queue = [[boss[0],boss[1]]]
# 当前权值
weight = 0

# 广搜的模板
while len(queue):
    queue_len = len(queue)
    for i in range(queue_len):
        qh = queue.pop(0)
        if map_[qh[0]][qh[1]] == MAX_WIGHT:
            map_[qh[0]][qh[1]] = weight
            for j in range(4):
                nx = qh[1] + move[j][0]
                ny = qh[0] + move[j][1]
                if 0 <= ny < maxy and 0 <= nx < maxx:
                    queue.append([ny,nx])
    # 每搜一层权值加1
    weight += 1

k = int(input())
# 存入队伍的数组
list_ = []

# 将队伍存入数组，{id，weight}
for i in range(1, k + 1):
    lx,ly = map(int,input().split())
    list_.append({
        "id": i,
        "weight": map_[ly - 1][lx - 1]
    })

# 打印胜利者
def print_win(index):
    if list_[index]["weight"] != MAX_WIGHT:
        print(list_[index]["id"], list_[index]["weight"])
    else:
        print("No winner.")

# 按权值排序
list_.sort(key=lambda a:a["weight"])

# 如果只有一个人，打印就完了，没人抢
if len(list_) == 1:
    print_win(0)
# 如果权值不相等，直接打印第一个
elif list_[0]["weight"] != list_[1]["weight"]:
    print_win(0)
else:
    flag = False
    for i in range(1,k - 1):
        # 如果当前节点与前后节点都不同，则没人抢的第一个人
        if list_[i]["weight"] != list_[i - 1]["weight"] and list_[i]["weight"] != list_[i + 1]["weight"]:
            flag = True
            print_win(i)
            break
    # 如果没有找到，则判断最后一个节点
    if not flag and list_[k - 1]["weight"] != list_[k - 2]["weight"]:
        print_win(k - 1)
    # 都没有就没有了
    elif not flag:
        print("No winner.")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
# 深搜 3 4 报错
# 最大 y 和 x
maxy,maxx = map(int,input().split())

# 地图
map_ = []
# 最大权值
MAX_WIGHT = 1000005

# 输入地图
for i in range(maxy):
    map_.append(list(map(int,input().split())))

# boss 为大本营位置
boss = [0, 0]
# 移动方向
move = [[0,1],[0,-1],[1,0],[-1,0]]

# 将所有能走的点赋值为 MAX_WIGHT， 不能走的为 -1，为之后搜索做准备
for i in range(maxy):
    for j in range(maxx):
        if map_[i][j] == 1:
            map_[i][j] = MAX_WIGHT
        elif map_[i][j] == 2:
            boss[0], boss[1] = i, j
            map_[i][j] = MAX_WIGHT
        elif map_[i][j] == 0:
            map_[i][j] == -1

# 深搜模板
def dfs(y, x, weight):
    if not 0 <= y < maxy or not 0 <= x < maxx:
        return
    if map_[y][x] == -1:
        return
    elif map_[y][x] > weight:
        map_[y][x] = weight
        for p in range(4):
            nx = x + move[p][0]
            ny = y + move[p][1]
            dfs(ny,nx,weight + 1)

dfs(boss[0], boss[1], 0)

k = int(input())
# 存入队伍的数组
list_ = []

# 将队伍存入数组，{id，weight}
for i in range(1, k + 1):
    lx,ly = map(int,input().split())
    list_.append({
        "id": i,
        "weight": map_[ly - 1][lx - 1]
    })

# 打印胜利者
def print_win(index):
    if list_[index]["weight"] != MAX_WIGHT:
        print(list_[index]["id"], list_[index]["weight"])
    else:
        print("No winner.")

# 按权值排序
list_.sort(key=lambda a:a["weight"])

# 如果只有一个人，打印就完了，没人抢
if len(list_) == 1:
    print_win(0)
# 如果权值不相等，直接打印第一个
elif list_[0]["weight"] != list_[1]["weight"]:
    print_win(0)
else:
    flag = False
    for i in range(1,k - 1):
        # 如果当前节点与前后节点都不同，则没人抢的第一个人
        if list_[i]["weight"] != list_[i - 1]["weight"] and list_[i]["weight"] != list_[i + 1]["weight"]:
            flag = True
            print_win(i)
            break
    # 如果没有找到，则判断最后一个节点
    if not flag and list_[k - 1]["weight"] != list_[k - 2]["weight"]:
        print_win(k - 1)
    # 都没有就没有了
    elif not flag:
        print("No winner.")

L3-2 工业园区建设

题目

描述

某工业园区要进行建设，共有 块工业用地排成一条直线，其中上面已经有若干块用地建设起了工厂，其他地方为空地。

现在工业园区计划在空地上建设至多 个新工厂以及一个仓库，希望在完成计划后，仓库离最近的 个工厂的距离之和尽可能小。

两块用地的距离等于他们的编号的差；即 1 号用地与 2 号用地的距离为 1。一个空地上只能建设一个工厂，仓库可以跟工厂建在一起。

输入格式：

数据的第一行是一个正整数 T，表示数据的组数。

每组数据的输入第一行为三个整数 ，表示有 块用地，最多可以新建 个新工厂，仓库离最近的 个工厂距离之和需要尽可能小。

接下来的一行是一个只由 , 组成的长度为 的字符串 ，第 个字符 为 表示第 块地块为空地， 表示第 块地块上已建工厂。地块编号从 开始。

数据约定：

设为对应的已建工厂的地块数量，则有。给定的数据有

输出格式：

输出 个整数，表示仓库建在第 块用地时，离最近的 个工厂的最小的距离之和是多少。

输入样例：

1
2
3
4
5
6
7
3
5 1 3
10110
10 3 5
1001001010
2 1 2
10

输出样例：

1
2
3
3 2 2 2 3
10 7 6 7 6 6 6 6 7 10
1 1

个人题解：

什么？不会做？暴力，爽 ~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
# 4 6 7 超时
t = int(input())

while t:
    t -= 1
    n, m, k = map(int,input().split())
    ls = input()
    len_ls = len(ls)
    flag = True
    for i in range(len_ls):
        temp_m = m  # 记录一下要建工厂用的个数，只要没有就建
        cur = 0 # 当前计算工厂个数
        a, b = i, i + 1 # 移动的指针
        sum_ = 0    # 记录一下距离和
        while cur != k:
            if a >= 0:  # 左指针可移动
                if ls[a] == '1':    # 有工厂
                    sum_ += i - a
                    cur += 1
                elif temp_m > 0:    # 没有工厂，且还有剩余，给大伙造一个
                    temp_m -= 1
                    sum_ += i - a
                    cur += 1
                a -= 1
            if cur == k: break
            if b < len_ls:  # 右指针可移动，其余步骤与左指针相同
                if ls[b] == '1':
                    sum_ += b - i
                    cur += 1
                elif temp_m > 0:
                    temp_m -= 1
                    sum_ += b - i
                    cur += 1
                b += 1
        if flag:
            flag = False
        else:
            print(" ", end="")
        print(sum_, end="")
    print()

L3-3 攀岩

题目

描述

九条可怜最近接触到了攀岩这项运动。作为一名运动量接近为零的家里蹲，相比于动手攀岩，可怜显然更加享受攀岩运动中动脑的部分，即对攀岩路线的规划。

为了只动脑，可怜设计了一个简易的攀岩机器人来帮她动手。这个机器人由一个核心（大小可以忽略不计）和三个长度至多为 r 的可伸缩机械臂组成，如下图所示：

一面攀岩墙可以看成一个二维的无穷平面，上面有个不同位置的岩点。在攀岩开始时，机器人的两个机械臂需要分别抓住岩点和，而其核心和第三个机械臂可以在任意位置。攀岩的目标是让机器人有两支机械臂同时抓握住岩点。

在攀岩过程中，机器人需要保证每时每刻都有两支机械臂抓握住两个不同的岩点。在满足这点的情况下，机器人可以在机械臂长度允许的情况下进行如下移动：

  1. 连续地将核心的位置从当前位置移动到任意位置。

  2. 用第三条机械臂抓握住一个岩点（可以与某条其他机械臂抓住相同的岩点）。

  3. 让一条机械臂松开其抓握的岩点。注意，只有当另外两条机械臂已经抓握住不同岩点时，才能进行这项操作。

注： 我们假设岩点的大小是无穷小，不会影响机器人的移动，比如机械臂、核心轨迹都可以经过岩点。

下面是一个攀岩过程的例子，假设平面上有四个岩点，坐标分别是

，则下面展示了一个时，即机械臂长度至多为时的攀岩方案。

  1. 初始时，可怜将机器人的核心放在 处，第三根手臂随意地放在 处。

  2. 机器人的第三机械臂抓握住岩点 。

  3. 机器人的第二机械臂松开，并移动到 处。

  4. 机器人的核心移动至 ，此时第一机械臂的长度到达极限 。

  5. 机器人的第二机械臂抓握住岩点

  6. 机器人的第一机械臂松开，并抓握住岩点 ，完成攀岩目标。

显然，机器人的机械臂长度越短，对可怜的路径规划能力要求越高。但是这个机械臂的长度也不能太短，不然机器人可能无论如何都无法完成攀岩任务。比如在上述任务中，如果机械臂长度小于 ，那么机器人将无法同时抓握和，这意味着它连开始攀岩都无法做到，更别说完成攀岩任务了。

因此，为了在合理范围内尽可能地挑战自己的大脑，可怜希望你对于攀岩馆中的每一项攀岩任务，都帮她计算（在可能完成攀岩任务的前提下）机械臂的最短长度是多少。

输入格式：

第一行输入一个整数 ，表示攀岩馆内攀岩任务的数量。

每个任务的第一行都是一个整数 ，表示攀岩任务涉及的岩点数量。

接下来 n 行，每行两个整数，表示第 个岩点的坐标。输入保证 且同一个攀岩任务中的岩点坐标两两不同。

输入保证满足 的数据不超过 组。

输出格式：

对于每个攀岩任务输出一行一个浮点数，表示最短可能的机械臂长度。你的答案在绝对误差或者相对误差不超过 的情况下都会被视为正确。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
4
4
0 0
1 0
0 1
1 2
4
0 0
2 0
0 3
2 2
7
0 0
1 0
2 0
2 1
2 2
1 2
0 2
15
13 2
13 3
12 44
6 17
4 71
14 58
4 49
2 51
8 37
1 18
5 43
5 35
1 84
10 23
13 69

输出样例：

1
2
3
4
0.99999999498
1.41421355524
1.00000000498
10.13227667717

样例解释

第一组数据和题面中的攀岩任务一致，其最小机械臂长度为 1，而样例输出的答案在的误差范围内，故会被视为正确。

下面给出了一个机械臂长度为 1 时的攀岩方案。攀岩开始时，机器人的核心与岩点重叠，第三机械臂在长度为 0 的情况下抓住了这个岩点，且第一机械臂额外抓住了岩点。接着，第三机械臂松开岩点，并随着核心移动至点 。然后，第三机械臂伸出并抓握住岩点。最后，第二机械臂松开岩点并同样抓握住岩点，完成攀岩任务。

第二组数据中，最小机械臂长度为，下图展示了一个对应的攀岩方案。攀岩开始时，机器人的核心位于 且三个机械臂分别抓握住岩点，和 ​。随后，第二机械臂松开点并抓握住岩点完成攀岩任务。注意到此攀岩方案全程没有使用岩点，这也是被允许的：攀岩任务中不要求使用所有的岩点。

个人题解：

( 似乎是求三角形外心？？？ )

1
# 暂无
,