w这套题，重点在于题意理解和模拟，每道题在输入输出上都需要写一定的代码进行处理。算法上考察了KMP和DP，DP难度不大，KMP如果不会的话用模拟也能拿一定的分数。

---

一、页式存储

题目描述

操作系统的页式存储管理中，当主存满并且需要的存储页不在主存中，需要对主存中的页面进行置换，其中有一个非常重要的算法，即LRU置换算法。

LRU (Least Recently Used)缓存算法理一种常用于管理缓存的策略，其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。实现简单的LRU缓存算法,支持查询、插入、删除操作。

最久未被使用定义：查询、插入和删除操作均为一次访问操作，每个元素均有一个最后一次被访问时间,按照最后一次被访问时间排序，时间最早的即为最久未使用。插入操作：当缓存中已经存在，则刷新值，不存在，则插入，如果超过上限，则淘汰最久未被使用的元素。

输入描述

第一行两个数N和K，分别表示缓存内最多可以存放页数，以及操作序列中的总操作数。其中N∈[1,100]，K∈[1,10000]。

第二至第K+1行，每行两个输入，两个输入用空格分隔。第一个输入是一个字符chichi​：A表示插入，Q表示查询，D表示删除。第二个输入是一个整数aiai​，表示一个页面的编号。其中aiai​∈[1,100000]。

输出描述

输出一行，表示缓存内各页面的编号，按照LRU优先级。

输入

2 5
A 103
A 102
A 102
Q 103
A 101

输出

101 103

解释

缓存大小为2，依次进行插入103、102，重复插入102，查询一次103，插入101时，最久未使用的元素为102，所以淘汰102。

题目描述

【题目类型：模拟】

纯模拟题，注意边界条件即可

代码：

n, k = map(int, input().split())
data = []for _ in range(k):temp_in = input().split()o, a = temp_in[0], int(temp_in[1])if o == 'A':if a in data:data.pop(data.index(a))data.insert(0, a)if len(data) > n:data = data[:n]elif o == 'Q':if a in data:data.pop(data.index(a))data.insert(0, a)else:if a in data:data.pop(data.index(a))ans = ""
for d in data:ans += str(d) + " "
if len(ans)>0:print(ans[:-1])
else:print("")

二、字符串匹配

题目描述

我们要对汇编程序进行语法解析，已知存在种字符串解析语法，其中的语法元素如下

N：用于匹配单个数字(0-9)

A：用于匹配单个字母(a-z，A-Z)

n()：用于表示一个分组，分组中至少有一个N语法元素或者A语法元素，n为个数值,表示匹配n次，1<=n<=200

输入给定的解析语法和字符串，要求从中找到第一个满足解析语法的字符串。

输入描述

输入两行数据，第一行是给定的解析语法，第二行是目标字符串。

输出描述

输出匹配的子字符串内容，如果没有匹配中任何字符串，输出!（英文感叹号）

样例一

输入

2(AN)
BA3A3ABB

输出

A3A3

样例二

输入

2(A2(N))
A3322A33P20BB

输出

A33P20

题目分析

【题目类型：括号栈解析、KMP匹配】

这道题是个很经典的字符串匹配类型的题目，主要考察2个要点，1）利用栈解析括号；2）利用KMP实现模板串和主串的匹配。

在测试中，如果没有练习过KMP很难一次想出完美的代码，可以使用暴力枚举的方式进行匹配，也能通过大部分的用例。用栈来解析括号必须要学会，不然遇到这种问题就会比较棘手了。

1）栈解析括号：基本思想是利用栈的后进先出，遇到左括号【(】，就把之前解析到的字符串和数字入栈，后面的循环其实就是在解括号内部的字符串，直到遇到右括号【)】，pop出栈尾元素，与当前解析到的（）中的字符串合并即可。

2）KMP匹配：核心思想是减少对已经匹配过的模板串前缀内容重复匹配。这里的关键是构造了一个next数组，用于记录模板串当前位置如果匹配失败，我们应该回退到什么位置重新匹配。举个例子：目标串是[a, b, a, b, a, b, c]，i表示索引，如果模板串是[a, b, a, b, c]，j表示索引，我们在i=4，j=4处匹配失败，这时候，无需将 i 回退到1，j回退到，我们可以保持i不变，将j回退到2，因为主串[2, 3]位置的ab 和模板串[0, 1]位置的ab是匹配的。下面代码中的KMP程序可以当做模板记忆，核心难点在于理解如何构造next记忆回退的位置，以及在匹配中如何利用next数组。

【注意】这类题目在处理之前，要对输入进行去空格操作，防止出现意外错误。

代码：

# 对于字符串问题，strip()去空格很必要，不然会出现奇怪的错误
template = input().strip()
content = input().strip()def expand_template(t):result = ""num = 0stack = []  # 后进先出，用来处理括号for ch in t:if ch.isdigit():num = num*10 + int(ch)  # 记录数字elif ch == '(':stack.append((num, result))num = 0     # 重置数字result = "" # 重置当前字符串elif ch == ')':pre_num, pre_result = stack.pop()result = pre_result + result*pre_numelse:result += chreturn resultdef judge(r, s):def N(s):return s.isdigit()def A(s):return s.isalpha()if r == 'A':return A(s)return N(s)# KMP匹配O(len(template))
def KMP_match(template, content):template = expand_template(template)if len(template) < len(template):return "!"def calc_next(template):# 计算用于存储匹配失败时的回撤位置的数组 nextnext = [0]*len(template)j = 0for i in range(1,len(template)):while j > 0 and template[j] != template[i]:j = next[j-1]if template[i] == template[j]:j += 1next[i] = jreturn next# KMP 算法next = calc_next(template)i = 0j = 0while i < len(content):if judge(template[j], content[i]):i += 1j += 1if j == len(template):return content[i-len(template):i]elif j == 0:i += 1else:j = next[j-1]return "!"print(KMP_match(template, content))

三、安装接口板

题目描述

柜式路由器需要配备接口板才可以工作,接口板用于接入用户业务，且接口板转发能力的和不能大于路由器整机的转发能力。当前某客户订购了2台设备和num块接口板。请计算是否存在一种安装方法，使用户选购的接口板，刚好能装到两台设备上，且每台设备配置的口板的转发能力之和,刚好和整机的转发能力相等。

1、设备整机转发能力的单位是Gbps,Gbps是设备单位时间内传输的比特数，代表千兆比特/秒。为了简化问题,规定值为整数,范围为[1,2000]。

2、客户订购的接口板数量num,值的范围[1,200]。

3、接口板容量的单位也是Gbps，比如10 10 40 40 100，代表选购了5块接口板,转发能力分别是10Gbps, 10Gbps, 40Gbps, 40Gbps, 100Gbps，接口板转发能力的范围一般为特定枚举值，为了简化问题，规定值为正整数。

输入描述

第一行是目标设备的转发能力。第二行是客户订购的接口板数量num 。第三行是订购的包含num个接口板的转发能力的列表。

输出描述

如果存在满足要求的安装方法，请分两行输出两台设备配置的接口板的转发能力的列表，且要求每台设备的单板，按转发能力从小到大排列。两台设备的单板，第一个单板转发能力小的优先输出。如果第一个单板转发能力相同，那单板数多的优先输出。如果不存在对应的安装方案，则返回-1。用例保证在满足前面条件的情况下，不会有多种不同的结果。

样例一

输入

100
5
40 10 10 40 100

输出

10 10 40 40
100

样例二

输入

100
3
10 10 20

输出

-1

题目分析

【题目类型：动态规划】

首先输入的接口板的能力之和必须是目标设别转发能力的2倍，不然就不可能有解。

其次我们构造一个二维的动态规划DP[i][j]，表示用前i个转接板，能力之和为j的一种组合方式，用01串表示，每个位置对应一个0或1，0表示不用这块板子，1表示用该板子。对于DP[i][j]，我们实际上存在多种方式，但是我们的目的是为了枚举 j 所以只需要保留一种方式即可。

如此从第一位开始计算，对于第i位，我们有2种新增的方式，使用该位，或不使用该位，即：DP[i][j] = DP[i-1][j]+0、DP[i][j+a[i]] = DP[i-1][j]+1，当j等于目标能力时，就是找到了解。

代码：

target = int(input())
n = int(input())
arr = [int(i) for i in input().split()]def calc():if arr[0] == target:return [1]DP = [{} for _ in range(n)]DP[0] = {0:[0], arr[0]:[1]}for i in range(1, n):KEY = DP[i-1].keys()for k in KEY:if k + arr[i] == target:return DP[i-1][k] + [1]DP[i][k] = DP[i-1][k] + [0]DP[i][k + arr[i]] = DP[i-1][k] + [1]return -1def buildPrint(ansList):for _ in range(n-len(ansList)):ansList.append(0)ans_line1 = sorted([arr[i] for i in range(len(ansList)) if ansList[i]])ans_line2 = sorted([arr[i] for i in range(len(ansList)) if not ansList[i]])if ans_line1[0] < ans_line2[0] or (ans_line1[0] == ans_line2[0] and len(ans_line1) > len(ans_line2)):line = ""for a in ans_line1:line += str(a) + " "print(line[:-1])line = ""for a in ans_line2:line += str(a) + " "print(line[:-1])else:line = ""for a in ans_line2:line += str(a) + " "print(line[:-1])line = ""for a in ans_line1:line += str(a) + " "print(line[:-1])if 2*target != sum(arr):print(-1)
else:ans = calc()if ans == -1:print(ans)else:buildPrint(ans)