【PAT乙级】7-3 自定义判题程序 (20 分)(2021秋季场)

题目介绍:

在每次允许插入、删除、修改一个字符的前提下,用最少的动作把一个字符串变成另一个字符串,是一道著名的可以用动态规划解决的问题。但判题的麻烦之处在于,虽然最小代价是唯一的,但变换方法却是不唯一的。例如把 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.
6
8
02330001100022100
8
11113330000001113300
6
022100000012200
5
033310000000200
6
0 2 2 1 000000 1 2 2 00
6
012200000022100

输出样例:

WA
WA
AC
WA
WA
AC

AC代码:

不得不说这道模拟题很容易丢分,但是在理清思路后去做也没有这么难,AC代码如下,注释很详细

#include <bits/stdc++.h>
using 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<t;kk++)
	{
		int n, j=0, f=0, cnt=0;//n:读取操作总数,j:用于模拟当前处理的字符位置,f:记录明显的错误,一旦变为1则代表WA了,cnt:记录当前已经操作了多少次
		cin >> n;
		string c;//模拟被生成的字符串
		getchar();//消除换行
		getline(cin,s);
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='0')//该字符不变,加入字符串c,j指向下一位,cnt不变
			{
				c+=a[j];
				j++;
			}
			else if(s[i]=='1')//该字符删除,j直接指向下一位,操作步骤cnt++
			{
				j++;
                cnt++;
			}
			else if(s[i]=='2')//该字符改变,我们此处认为'^'为万能字符,后续进行判断时直接代表该字符正确
			{				  //j指向下一位,操作步骤cnt++
				c+='^';
				j++;
                cnt++;
			}
			else if(s[i]=='3')//直接添加,cnt++,j仍然指向原位
			{
				c+='^';
                cnt++;
			}
			else f=1;//出现了0,1,2,3以外的字符,对该组数据直接判WA
		}

		if(c.size()!=b.size()||cnt!=n)//目标字符串与原字符串字数个数不等,或实际操作数与读入不同
			f=1;
		
		for(int i=0;i<b.size();i++)//遍历对比两字符数组
		{
			if(c[i]==b[i]||c[i]=='^') continue;//字符相同或被标记为万能字符,判断下一个
			else f=1;//出现错误,直接判WA
		}
		
		if(f==0)
		{
			k[kk]=n;
			if(n<minn) minn=n;//记录操作数的最小值
		}
		else
			k[kk]=-1;//记录错误
	}

	for(int i=0;i<t;i++)
	{
		if(k[i]==minn) cout<<"AC"<<endl;//恰好等于最小值的为AC
		else cout<<"WA"<<endl;//否则为WA
	}
       
    system("pause");
	return 0;
}

上一篇:js history对象 手机物理返回键


下一篇:2021 多校 牛客 第九场