写在前面

第1题-操场护队演练

题目内容

体育课把学员排成一列，做追逐与护挡。列里每个人有一个互不相同的代号，站位不按代号大小。

追逐者每轮指向当前列中的某一站，护挡者同一轮也指向一站。两人都按从左往右第  站起算。

指向落在同一站时，这一轮扑空，没有人离列。两站不同，而且追逐者的站号仍在当前人数之内，则该站学员离列，其右侧的人依次左移，列中不留空档。追逐者的站号小于  或大于当前人数时，这一轮没有人离列。护挡者的站号小于  或大于当前人数时，护挡不算数；只要追逐者的站号仍然有效，该站学员仍要离列。

某一轮结束后，列上人数小于等于 ，练习立刻失败，后面的轮次不再进行。全部轮次做完后人数仍大于 ，练习成功。

解题思路

用数组按从左到右保存学员代号。每一轮读入护挡站号  和追逐站号 ，都从  开始数。

1. 人数已经小于等于  时立刻停止，后面的轮次不再看。
2.  小于  或大于当前人数时，这一轮没有人离列。
3.  越界，或者  与  不同时，删掉当前第  个代号，右侧的人左移一格。
4.  与  都落在列内且相等时，这一轮扑空。
5. 全部有效轮次结束后，人数仍大于  就输出 ，并把代号按数值升序写出。否则输出 ，代号保持当时从左到右的顺序。

复杂度分析

• 时间复杂度：。轮次本身扫一遍，真正离列最多  次，每次在数组里删除是 。
• 空间复杂度：。保存当前队列；若边读边模拟，额外空间可以降到 。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

# 操场护队演练：按当前站号模拟离列，人数不超过 1 时立刻失败defdrill(codes, rounds):# 从左到右保留代号。rounds 的每一项是 (护挡站号, 追逐站号)    line = list(codes)for guard, attack in rounds:        length = len(line)# 上一轮已经把人数打到 1 或更少，后面的轮次作废if length <= 1:break# 追逐站号不在 1 到当前人数之间，这一轮没有人离列if attack < 1or attack > length:continue# 护挡无效，或者两站不同：追逐仍然有效，删掉这一站if guard < 1or guard > length or guard != attack:            line.pop(attack - 1)if len(line) <= 1:# 失败时保持当时从左到右的顺序return"bai", line# 成功时按代号数值升序return"sheng", sorted(line)defmain():# 第一行人数，第二行代号，第三行轮数，之后每行先护挡再追逐    people = int(input())    codes = list(map(int, input().split()))    rounds_count = int(input())    rounds = []for _ in range(rounds_count):        guard, attack = map(int, input().split())        rounds.append((guard, attack))    tag, left = drill(codes, rounds)    print(tag)    print(" ".join(str(item) for item in left))if __name__ == "__main__":    main()

第2题-双廊同序展数

题目内容

美术馆有东廊、西廊两条参观路线。每件展品用一个小写拉丁字母当编号，同一条廊里编号可以重复，重复只表示编号相同，仍然是不同的展品。

从每条廊里按从左到右的原有先后挑出若干件，挑出的编号序列必须完全一样。可以跳过不选的展品，但不能把已选展品的左右次序对调。在这个限制下，最多能挑出多少件。只报件数。

解题思路

两条廊都是编号序列，允许跳过，不允许对调先后。要的是最长公共子序列的长度，用动态规划即可。

1. 令  表示东廊前  件、西廊前  件最多能挑出的件数。
2. 若第  件和第  件编号相同，。
3. 若编号不同，，也就是丢掉其中一边的当前展品。
4. 某一边件数为  时，对应前缀都是 。答案是 。
5. ，只用两行滚动数组保存上一件东廊的结果。

复杂度分析

• 时间复杂度：。每一对前缀只转移一次。
• 空间复杂度：。滚动数组只保留一行。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

# 双廊同序展数：两条编号序列的最长公共子序列长度defsame_order(east, west):# east、west 都按从左到右保存。dp 滚动后，prev[j] 是东廊前若干件、西廊前 j 件的最优件数    rows = len(east)    cols = len(west)    prev = [0] * (cols + 1)for i in range(1, rows + 1):        curr = [0] * (cols + 1)for j in range(1, cols + 1):if east[i - 1] == west[j - 1]:# 两边当前这件编号相同，可以一起收下                curr[j] = prev[j - 1] + 1else:# 编号不同，丢掉东廊这一件或丢掉西廊这一件                curr[j] = prev[j] if prev[j] > curr[j - 1] else curr[j - 1]        prev = currreturn prev[cols]defmain():# 件数为 0 时，对应的那一行是空行，读进来后不要再切分    east_count = int(input())    east_line = input()    east = east_line.split() if east_count else []    west_count = int(input())    west_line = input()    west = west_line.split() if west_count else []    print(same_order(east, west))if __name__ == "__main__":    main()

第3题-九格纸盖章

题目内容

手工课上，甲、乙轮流往一张九格纸盖章。甲先盖，章记作 ；乙后盖，章记作 ；还没盖的格子是 。九格排成三行三列。

谁先让自己的章在同一行、同一列或同一条斜向上凑满三格，这一局立刻结束，对方不能再盖。每一格最多盖一次。两人每一步都挑对自己最终更有利的空格：优先让自己获胜，其次接受平局，最后才接受失败。

现在给出若干张已经盖过一部分的纸，判断每张按上面的规则收到结束时的结果。这些章必须能由「甲先手、一人一步、有人凑满就停」得到；否则这张纸无效。某人刚好用新盖的一章凑满三格，是正常收场，要报出胜负，不算无效。

解题思路

先确认这张纸能不能由「甲先盖、一人一步、有人凑满就停」走到，再对还没结束的纸做双方最优搜索。

1. 八条线是三行、三列和两条斜向。某一条线上三格都是同一个人，这个人就已经凑满。
2. 甲先手，所以乙的章数不能超过甲，甲最多只比乙多一枚。超出这个范围的纸无效。
3. 两人都已经凑满，无效：先凑满的一方会让对局停下，对方来不及再凑出自己的线。
4. 甲凑满时，甲的章数必须正好比乙多一枚，说明最后一盖是甲。乙凑满时，两边章数必须相同，说明最后一盖是乙。
5. 还要能指出「收场的那一枚」：把它揭掉之后，这个人不再有任何一条凑满的线。一行和一列共用这一枚时仍然合法；不存在这样一枚时，这些线不可能在同一次盖章里一起完成。
6. 已经合法收场的，直接报  或 。九格盖满且谁都没凑满，报 。
7. 否则轮到章数较少的一方；两边一样多时轮到甲。每一手都选对自己更好的空格：甲的偏好是自己胜、平局、乙胜；乙的偏好是自己胜、平局、甲胜。盖下去若刚好凑满，递归入口立刻返回，不再往下盖。

复杂度分析

• 时间复杂度：每张纸最多再盖  步，每步的空格不超过剩余格数。，全部纸都可以搜完。
• 空间复杂度：递归深度不超过 ，另外只用常数张九格。

代码实现

python代码(C++和JAVA代码见在线OJ网址)

# 九格对戳终局：先判断章序是否可能出现，再按双方最优盖章推到结束LINES = (    (0, 1, 2),    (3, 4, 5),    (6, 7, 8),    (0, 3, 6),    (1, 4, 7),    (2, 5, 8),    (0, 4, 8),    (2, 4, 6),)defhas_line(grid, stamp):# 横、竖、两条斜向，只要有一条三格都是同一人的章for a, b, c in LINES:if grid[a] == stamp and grid[b] == stamp and grid[c] == stamp:returnTruereturnFalsedefcould_just_finish(grid, stamp):# 存在一枚章，拿掉之后这人不再凑满。说明最后一盖可以正好完成for index in range(9):if grid[index] != stamp:continue        grid[index] = 0        still = has_line(grid, stamp)        grid[index] = stampifnot still:returnTruereturnFalsedefbetter(turn, old, new):# 甲希望结果靠近 1，乙希望结果靠近 2，平局夹在中间if turn == 1:        rank = {1: 2, 0: 1, 2: 0}else:        rank = {2: 2, 0: 1, 1: 0}if old isNoneor rank[new] > rank[old]:return newreturn olddefsearch(grid, turn):if has_line(grid, 1):return1if has_line(grid, 2):return2if0notin grid:return0    best = Nonefor index in range(9):if grid[index] != 0:continue        grid[index] = turn# 盖完换对方；递归里若刚凑满，会在入口直接返回        best = better(turn, best, search(grid, 3 - turn))        grid[index] = 0return bestdefjudge(grid):    first = grid.count(1)    second = grid.count(2)# 甲先手，乙的章数不能更多，甲最多只比乙多一枚if second > first or first > second + 1:return-1    first_done = has_line(grid, 1)    second_done = has_line(grid, 2)# 两人不能都已经凑满，因为先凑满的那一方会让对局停下if first_done and second_done:return-1# 甲凑满时，最后一盖必须是甲；乙凑满时，最后一盖必须是乙if first_done and first != second + 1:return-1if second_done and first != second:return-1if first_done andnot could_just_finish(grid, 1):return-1if second_done andnot could_just_finish(grid, 2):return-1if first_done:return1if second_done:return2if first + second == 9:return0    turn = 1if first == second else2return search(grid, turn)defmain():# 每张纸单独一行九个数，答案按输入顺序排在同一行    sheet_count = int(input())    answers = []for _ in range(sheet_count):        cells = list(map(int, input().split()))        answers.append(str(judge(cells)))    print(" ".join(answers))if __name__ == "__main__":    main()