第一题：错别字

签到题

1. 题目描述

小王在抄会议记录，但他手比较抖，有一些单词出现了错误，现在让你统计他抄的记录中所有不同情况错误出现的次数，共有三种情况：

• 连续抄错一个单词的次数
• 连续抄错两个单词的次数
• 连续抄错三个及以上单词的次数

这里抄错的定义是：只要两个单词不是完全一致，包括缺少/增加字母、改变字母大小写，都算是抄错。
注意：小王只会抄错，不会漏抄或者多抄（说人话就是两个字符串单词的个数是相等的）。

输入输出样例：

Input:
17
Hello everyone let us discuss the problem and I believe you are smart enough to solve it
HELLO everyone lat is discus the probelm and i beelieve u r smart through two solve it
Output:
2 1 2

输入表示会议记录一共有17个单词，单词之间由空格分隔，接下来是原文和小王的记录，
输出表示连续抄错一个单词的有2次，连续抄错两个单词的有1次，连续抄错三个及以上单词的有2次。

如果用一个表示是否抄错的数组表示，即为 （1表示该单词抄错了）

[1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0]

一下就能看出来答案。

2. 解法

两趟遍历，（也可以优化为一趟遍历）

# -*- encoding: utf-8 -*-

"""
@Author : Soarkey
@Date   : 2021/3/30
@Desc   : 错别字
"""

if __name__ == '__main__':
    while True:
        try:
            n = int(input())
            s1 = input().split(' ')
            s2 = input().split(' ')

            error = [0] * (n + 1)  # 多加1位保证最后一个是错误的情况能被cover住
            for i in range(n):
                if s1[i] != s2[i]:
                    error[i] = 1

            print(error)

            one_error = 0
            two_error = 0
            more_than_two_error = 0

            k = 0  # 表示连续k个错误
            for i in range(n + 1):
                if error[i] == 1:
                    k += 1
                else:
                    if k == 1:
                        one_error += 1
                    if k == 2:
                        two_error += 1
                    if k >= 3:
                        more_than_two_error += 1
                    k = 0

            print(f'{one_error} {two_error} {more_than_two_error}')

        except EOFError:
            break

第二题：乌龟快跑

1.题目描述

给定一个n*n的有向图，共有m条有向边，边的权值代表了该条边上的兔子数量，乌龟要从起始点s爬到终点t，但是只允许走x步（即经过x条边），题目数据保证满足约束条件的情况下一定存在从起点到终点的路径。

乌龟经过每一条边都会被该条边上的兔子（数量为该边权值）嘲讽，请问这个玻璃心乌龟该走哪条路，能够最小化受到的嘲讽，输出该条路径上兔子最多的边的兔子数量。

（说人话就是从能到达终点的路径中找到最短的路径，输出该条路径上边的最大权值）

输入输出样例

Input:
5 6 1 5 2
1 5 100
1 2 10
2 5 5
1 3 3
3 4 2
4 5 1
Output:
10

输入第一行为n,m,s,t,x，接下来的m行为有向边的(起点,终点,权值)该输入构成的图为：

可以看出从起点2到终点5的满足步长为2的路径有红色和蓝色两条边，其中最短的路径为红色路径，该路径上最大的权值为10。

2. 解法

图论问题，用dfs遍历

# -*- encoding: utf-8 -*-

"""
@Author : Soarkey
@Date   : 2021/3/30
@Desc   : 乌龟兔子
"""

if __name__ == '__main__':
    while True:
        try:
            n, m, s, t, x = tuple(map(lambda x: int(x), input().split()))
            graph = [[0 for j in range(n + 1)] for i in range(n + 1)]
            for _ in range(m):
                a, b, v = tuple(map(lambda x: int(x), input().split()))
                graph[a][b] = v
            # print(graph)
            path = []
            vis = [False for i in range(n + 1)]
            rabbits = []
            min_rabbits = 9999999

            def dfs(i, depth):
                global vis, t, x, graph, min_rabbits, rabbits
                if i == t:
                    # 找到
                    # print(rabbits)
                    min_rabbits = min(min_rabbits, max(rabbits))
                    return
                if depth >= x:
                    # 超过步长
                    return

                for j in range(len(graph[i])):
                    if not vis[j] and graph[i][j] > 0:
                        vis[j] = True
                        rabbits.append(graph[i][j])
                        dfs(j, depth + 1)
                        rabbits.pop()
                        vis[j] = False

            dfs(s, 0)
            print(min_rabbits)

        except EOFError:
            break