演算法筆記刷題6 ( PAT1003我要通過 )

題目本體

“答案正確”是自動判題系統給出的最令人歡喜的回復，本題屬于 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

這個鬼題真的沒什么好說的，想不到居然卡了我一兩個月，，，還是太naive了，最后是參照csdn上大佬的思路寫出來的https://blog.csdn.net/oShuaiFeng/article/details/80622269

三點要求：

只能有且必須有P/A/T三種字母，而且P/T有且只能各有一個，
P必須在T前面，
統計P...T結構前A，P...T結構中A，P...T結構后A，分別記為above, mid, last，三者滿足above*mid=last的關系（不用判斷PT之間有沒有A，首先PT不能通過編譯，其次沒A乘法不成立，

放代碼

可能我代碼也不咋規范吧，放c跑一直答案錯誤，放c++一遍就過去了，

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 10010
void PATselect();
int main()
{
	int num;
	scanf("%d",&num); 
	for(int i=0;i<num;i++){
		PATselect();
	}
	return 0;
	
 } 
void PATselect(){
	char str[110];
	scanf("%s",str);
	int P,A,T,WR,other,above,mid,last;
	P=A=T=WR=other=above=mid=last=0; 
	for(int i=0;str[i]!='\0';i++){
		if(str[i]=='A'){
			A++;
			if(P==0)above++;
			if(P>0&&T==0)mid++;
			if(T>0)last++; 
		}
		else if(str[i]=='P')P++;
		else if(str[i]=='T'){
			if(P==0)WR=1;
			T++; 
		}
		else other++;	
	}
	last=last-above*mid;
	if(P==1&&A!=0&&T==1&&other==0&&WR==0&&last==0)
	printf("YES\n");
	else 
	printf("NO\n");	
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/30663.html

標籤：C++

上一篇：關于使用ffmpeg的一些牢騷

下一篇：聚合型別與POD型別