本文共 1352 字,大约阅读时间需要 4 分钟。
题目介绍:
在每次允许插入、删除、修改一个字符的前提下,用最少的动作把一个字符串变成另一个字符串,是一道著名的可以用动态规划解决的问题。但判题的麻烦之处在于,虽然最小代价是唯一的,但变换方法却是不唯一的。例如把 PAT
变成 PTA
最少需要 2 步,可以保持第 1 个字母不变,修改后面 2 个字母,也可以保持第 1、2 个字母不变,在 A
前面插入 T
,后面删除 T
。由于拼题 A 系统的默认判题程序只能通过比对输出文件来判断对错,对这种正确答案输出不唯一的题目就不能处理了,需要出题者额外编写一个自定义判题程序来解决问题。
本题就请你编写这个自定义判题程序,读入两个字符串和用户程序产生的输出结果,判断他们的程序输出是否正确。
输入格式:
输入首先在前两行分别给出两个不超过 1000 个字符、以回车结束的非空字符串,第 1 行对应初始字符串,第 2 行对应目标字符串。
随后一行给出一个正整数 N(≤100),为需要判断的提交数。
接下来是 N 个提交的输出结果,每个结果占 2 行:第 1 行给出一个整数 K(不超出 32 位 int 的范围),为用户输出的动作数;第 2 行顺次描述对初始字符串的每个字符所做的操作:
- 如果这个字符不变,则在对应位置输出 0
- 如果这个字符被删除,则在对应位置输出 1
- 如果这个字符被改变,则在对应位置输出 2
- 如果这个字符前面或者后面插入了一个字符,则在插入的位置输出 3
注意我们要求用户提交的行首尾和数字间均无空格,所以如果有多余空格应判为错误。
题目保证这个操作序列不为空。
输出格式:
对每个正确的提交,在一行中输出 AC
;否则输出 WA
。
注意:这里并不要求你会用动态规划求出最优解。所以对“正确提交”的判断,并不以动态规划求出的最优解为根据! 对于用户输出的 K,如果其操作序列的确给出了 K 步操作并可以完成字符串的变换,则称为一个“可行解”。所谓“正确提交”,是指所有提交的可行解中的最优解。
输入样例:
This is a test.Tom is a cat.68023300011000221008111133300000011133006022100000012200503331000000020060 2 2 1 000000 1 2 2 006012200000022100
输出样例:
WAWAACWAWAAC
AC代码:
不得不说这道模拟题很容易丢分,但是在理清思路后去做也没有这么难,AC代码如下,注释很详细
#includeusing namespace std;int main(){ int t, k[11000];//t:所需测评数量,k[]:存放每组答案的判题结果 string a, b, s;//分别存放原字符串, int minn=9999999;//存放最小正确答案,初始值 getline(cin,a); getline(cin,b);//务必使用getline读入 cin >> t; for(int kk=0;kk > n; string c;//模拟被生成的字符串 getchar();//消除换行 getline(cin,s); for(int i=0;i
转载地址:https://blog.csdn.net/m0_57835344/article/details/120296607 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!