1003 我要通過！（20分）
1003 我要通過！ (20 分)
“答案正確”是自動判題系統給出的最令人歡喜的回復，本題屬于 PAT 的“答案正確”大派送 —— 只要讀入的字串滿足下列條件，系統就輸出“答案正確”，否則輸出“答案錯誤”，
得到“答案正確”的條件是：
-
字串中必須僅有
P、A、T這三種字符，不可以包含其它字符； -
任意形如
xPATx的字串都可以獲得“答案正確”，其中x或者是空字串，或者是僅由字母A組成的字串； -
如果
aPbTc是正確的，那么aPbATca也是正確的，其中a、b、c均或者是空字串，或者是僅由字母A組成的字串，
現在就請你為 PAT 寫一個自動裁判程式，判定哪些字串是可以獲得“答案正確”的，
輸入格式：
每個測驗輸入包含 1 個測驗用例，第 1 行給出一個正整數 n (<10)，是需要檢測的字串個數，接下來每個字串占一行，字串長度不超過 100，且不包含空格，
輸出格式：
每個字串的檢測結果占一行，如果該字串可以獲得“答案正確”，則輸出 YES，否則輸出 NO，
輸入樣例：
9
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
輸出樣例：
YES
YES
YES
YES
NO
NO
NO
NO
NO
分析：該題是一個字串判斷，處于記憶體大小考慮，本次采用依次讀取字符處理的方式，題目的判斷在三個條件之中，下面依次分析分析題目給出的三個條件：
第一個條件要求字串中必須含有P、A、T三個字符，因此可以采取在輸入字符時注意判斷字符，若字符為P、A、T之一，則將對應的計數整數加一，若出現了其他字符，則將字符標識歸零，
第二個條件為"xPATx"格式，x代表多個A字串或空字串，在PAT兩端x字串相同，可以單純將前后兩部分看作相同數目A組成的字串，令兩端字串長度同時為a(a>=0),因此整體中三部分A字串可以看作a*1=a的形式，
第三個條件為"如果 aPbTc 是正確的，那么 aPbATca 也是正確的"，本一條件主要規范了對字串的化簡，具體判斷還是由前兩條條件所規定，因此主要注意該條件中對字串的化簡，這里需要注意字串整體可以多次簡化求解，即"AAPAAAATTAAAAAA"一次簡化為"AAPAATAAAA"不能確定結果，再次簡化后得出的字串"AAPATAA"即可符合第二個條件，因此源字串"答案正確"，與第二個條件相似，所有的a、b、c都可以看作零個或多個A所組成的字串，因此可以看出PT前后兩部分(令前中后各部分A字串長度分別為a、b、c)完全符合a*b=c的公式，
綜合上述各條件分析，可以看出判斷字串可以從字符種類、統計三部分字串長度并據a*b=c公式判斷，但同時需要注意PT間的A字串長度必須大于等于零，且PT順序必須是P位于T前，因此在判斷時需要加上這些條件，綜合所有分析便可以得出以下代碼：
?
#include<cstdio>
#include <iostream>
using namespace std;
?
void solve() {
int x;
char c;
cin >> x;
getchar();
for (int i = 0; i < x; i++) {
int begin = 0, mid = 0, end = 0;
int P, A, T;
P = A = T = 0; //P、A、T三個字母的個數
int rp = 1; // 三部分A的標識，用以劃分三個部分
int cnd = 1; // 字串內是否只含有P、A、T三個字母的標識
int flag = 1; //字母順序識別符號
for (char s; s = getchar(), s != '\n';) {
s == 'P' ? P++, rp = 2 : s == 'A' ? A++ : s == 'T' ? T++, rp = 3 : cnd = 0;//判斷輸入字符種類，從而改變對應資料
if ((T >= 1) && (P == 0)) //判斷P、T的前后順序，若T出現在P前面則將識別符號歸零
flag = 0;
switch (rp) {
case 1:begin++; break; // 前
case 2:if (s != 'P') mid++; break; // 中
case 3:if (s != 'T') end++; break; // 后
}
}
//總和判斷，包括字符種類只有P、A、T，P、T只能出現一次，begin*mid=end乘法的滿足，P、T的字符順序，類似APT格式P前有A但PT間不存在A而能滿足乘法的情況
if (P == 1 && A && T == 1 && begin * mid == end && cnd&&flag&&mid)
printf("YES\n");
else // 否則
printf("NO\n");
}
}
int main() {
solve(); // 默默不說話的函式，
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/285762.html
標籤：其他
下一篇：資料結構基礎知識