1003 我要通過！| PAT (Basic Level) Practice

1003 我要通過！ （20 分）

“答案正确”是自動判題系統給出的最令人歡喜的回複。本題屬于 PAT 的“答案正确”大派送 —— 隻要讀入的字元串滿足下列條件，系統就輸出“答案正确”，否則輸出“答案錯誤”。

得到“答案正确”的條件是：

字元串中必須僅有P、 A、 T這三種字元，不可以包含其它字元；

任意形如 xPATx 的字元串都可以獲得“答案正确”，其中 x 或者是空字元串，或者是僅由字母 A 組成的字元串；

如果 aPbTc 是正确的，那麼* aPbATca* 也是正确的，其中 a、 b、 c 均或者是空字元串，或者是僅由字母 A 組成的字元串。

現在就請你為 PAT 寫一個自動裁判程式，判定哪些字元串是可以獲得“答案正确”的。

輸入格式：

每個測試輸入包含 1 個測試用例。第 1 行給出一個正整數 n (<10)，是需要檢測的字元串個數。接下來每個字元串占一行，字元串長度不超過 100，且不包含空格。

輸出格式：

每個字元串的檢測結果占一行，如果該字元串可以獲得“答案正确”，則輸出* YES，否則輸出NO*。

輸入樣例：

8
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
           

輸出樣例：

YES
YES
YES
YES
NO
NO
NO
NO
           

問題分析

問題分析啟發自參考資料

條件1：

字元串中隻有PAT三種字元

條件2：形如AAPATAA或者AAAAPATAAAA的都是對的，反正就是中間一個PAT，兩遍要麼沒有A，要麼A個數相同

條件3：若aPbTc成立，則aPbATca成立

根據條件三，有：

由于PAT成立，故PAAT成立，故PAAAT成立，....，故PA...T成立

由于APATA成立，故APAATAA成立，故APAAATAAA成立，...，故AP[n個A]T[n個A]成立

由于AAPATAA成立，故AAPAATAAAA成立，故AAPAAATAAAAAA成立，...，故AAP[n個A]T[n * 2個A]成立

是以，形如PA......T的一定是成立的

形如[n個A]P[m個A]T[n * m個A]也是成立的

歸納如下

隻能有一個P和T且P必須在T前面；

其他字元，要麼是A要麼是空格；

P前面的A字元個數x，P和T之間的A字元個數y，T後面A字元個數z，三者滿足x*y=z。

代碼

#include<iostream>
#include<string>
#include<vector>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<string>str(n);//存放n個字元串，vector動态生成str[n]
	vector<bool>result(n);//存放n個字元串的結果,vector動态生成result[n]
	getchar();                 //輸
	for (int i = 0; i < n; i++)//入
		getline(cin, str[i]);  //一行
	for (int k = 0; k < n; k++)//判斷每個字元串
	{
		bool flag = true;     //是否通過的标志
		int p = -1;           //P的位置
		int t = -1;           //T的位置
		for (int i = 0; i < str[k].size(); i++)
		{//周遊該字元串
			if (str[k][i] == 'A')
				continue;
			else if (str[k][i] == 'P')
			{//事實證明下面7行隻需要 p=i;
				if (p == -1)//如果P還未使用
					p = i;//記錄P的位置
				else//如果P已經用過了
				{
					flag = false;//失敗
					break;//退出周遊
				}
			}
			else if (str[k][i] == 'T')
			{//事實證明下面7行隻需要 t=i;
				if (t == -1)//如果t還未使用
					t = i;//記錄T的位置
				else//如果t已經用過了
				{
					flag = false;//失敗
					break;//退出周遊
				}
			}
			else//如果有其他字元
			{
				flag = false;//記錄
				break;//退出周遊
			}
		}
		if (flag)
		{//如果該字元串隻有P、A、T三個字元串且P、T隻有一個
			if (t - p >= 2)//如果 T 在 P 的右邊2個或更後的位置
			{
				int b = t - p - 1;//b 記錄PT之間A的數量
				int c = str[k].size() - t - 1;//c 記錄 T 之後 A 的數量
				int a = p;//a 記錄P之前 A 的數量
				if (a * b != c)
					flag = false;
			}
			else
				flag = false;
		}
		result[k] = flag;//記錄該字元串的結果
	}
	for (int i = 0; i < n; i++)
	{
		if (result[i])
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}
           

參考資料

1、java-1003 我要通過！ by. aptx1048576

2、1003. 我要通過！(20) by.小羊哈利