蓝桥杯2024年第十五届省赛真题-魔法巡游（Python）

前言

本文参考了FJ_EYoungOneC的文章思路，并且修改了该文章的某些理解上的偏差。

一、题目

题目来源：dotcpp

题目描述

在蓝桥王国中，两位魔法使者，小蓝与小桥，肩负着维护时空秩序的使命。他们每人分别持有 N 个符文石，这些石头被赋予了强大的力量，每一块上都刻有一个介于 1 到 109 之间的数字符号。小蓝的符文石集合标记为 s1, s2, . . . , sN，小桥的则为 t1, t2, . . . , tN。

两位魔法使者的任务是通过使用符文石，在各个时空结点间巡游。每次巡游遵循这样一条法则：当小蓝使用了符文石 si 到达新的结点后，小桥必须选用一个序号更大的符文石（即某个 tj 满足 j > i）前往下一个结点。同理，小桥抵达之后，小蓝需要选择一个序号 k > j 的符文石 sk 继续他们的巡游。为了成功地穿梭时空，两个连续使用的符文石上的数字符号必须有共鸣，这种共鸣只有当数字符号中至少包含一个特定的元素——星火（数字 0）、水波（数字 2）或者风语（数字 4）时，才会发生。例如，符号序列 126, 552, 24, 4 中的每对连续符文都包含了至少一个共鸣元素，则它们是一系列成功的巡游；而如果是 15, 51, 5，则不成立，因为它们之间的共鸣元素不包含星火、水波或风语中的任意一个。

小蓝总是先启程，使用他的符文石开启巡游。

你的任务是计算这对魔法使者能够执行的最长时空巡游序列的长度。这样的序列形式为 si1, ti2, si3, ti4, . . .，其中序列索引满足 i1 < i2 < i3 < i4 < . . .，并且序列中每一对相邻的符文石都至少包含一个共鸣元素。

输入格式

输入的第一行包含一个整数 N，表示每位魔法使者持有的符文石数量。第二行包含 N 个整数 s1, s2, · · · , sN ，相邻整数之间使用一个空格分隔，表示小蓝的符文石上刻有的数字符号。第三行包含 N 个整数 t1, t2, · · · , tN ，相邻整数之间使用一个空格分隔，表示小桥的符文石上刻有的数字符号。

输出格式

输出一行包含一个整数，表示小蓝和小桥在遵守所有规则的情况下，最多能进行多少次时空巡游。

样例输入

5
126 393 581 42 44
204 990 240 46 52

样例输出

4

提示

【样例说明】

小蓝和小桥可以选择以下符文石序列进行巡游：

s1(126) → t3(240) → s4(42) → t5(52)

这里，数字 2 作为共鸣元素连接了 s1 和 t3、s4 和 t5，数字 2、4 作为共鸣元素连接了 t3 和 s4。

【评测用例规模与约定】对于 30% 的评测用例，1 ≤ N ≤ 103，1 ≤ si, ti ≤ 105。对于所有评测用例，1 ≤ N ≤ 105，1 ≤ si, ti ≤ 109。

二、思路

①题目大概意思是：

给定两个数字序列（当然理解为字符串更好操作）

L1：a1,a2,a3……an

L2：b1,b2,b3……bn

从两个序列中按次序选出一串数，使这串数长度最长。

②这串数要满足的条件：

③算法思想：

按照常规思路枚举开始位置（从L1中选择）复杂度为O(n²），会超时。既然选数有个顺序，那选出来的数的长度必然就有依赖（递推）关系→DP。

DP的初态如何确定？

1. 向L1和L2末尾添加一项“024”（楼主是作为字符串处理的），那么选出的数字串最后一个数必然来自L1的“024”或者L2的“024”。
2. DP从后往前递推长度。

三、代码

import sys


data = sys.stdin.read().split()
n = int(data[0])
L1 = []
for i in range(1,n+1):
    L1.append(data[i])
L1.append("024")
L2 = []
for i in range(n+1,n+n+1):
    L2.append(data[i])
L2.append("024")

pL1 = n # 记录L1中上一个数位满足要求的数的下标
pL2 = n
len_L1 = [0 for i in range(n+1)] # L1中以L1[i]开始的符合题意的子序列最大长度
len_L2 = [0 for i in range(n+1)] # L2中以L2[i]开始的符合题意的子序列最大长度
len_L1[n] = len_L2[n] = 1 # 初态

index = n-1
while index>=0:
    if '0' in L1[index] or '2' in L1[index] or '4' in L1[index]:
        len_L1[index] = max(len_L1[index],len_L2[pL2]+1)
    if '0' in L2[index] or '2' in L2[index] or '4' in L2[index]:
        len_L2[index] = max(len_L2[index],len_L1[pL1]+1)

    # 注意，先更新len_L1,len_L2再更新pL1,pL2
    if '0' in L1[index] or '2' in L1[index] or '4' in L1[index]:
        pL1 = index
    if '0' in L2[index] or '2' in L2[index] or '4' in L2[index]:
        pL2 = index
    
    index -= 1

print(max(len_L1)-1)

tips：代码中先更新len_L1,len_L2再更新pL1,pL2的原因是避免下图中的情况：

作者：罄竹_