Topic information

"Correct answer" is the most gratifying reply given by the automatic question judgment system. This question belongs to PAT's "correct answer" distribution - as long as the read string meets the following conditions, the system will output "correct answer", otherwise it will output "wrong answer".

The conditions for getting "correct answer" are:

The string must contain only three characters: P, A and T, and cannot contain other characters;
Any string shaped like (1) xPATx can get "correct answer", where x is either an empty string or A string composed of only the letter A;
(2) If aPbTc is correct, aPbATca is also correct, where a, b and c are either empty strings or strings composed of only the letter A.
Now please write an automatic referee program for PAT to determine which strings can get the "correct answer".

Input format:

Each test input contains 1 test case.
Line 1 gives a positive integer n (≤10)，Is the number of strings to be detected.
Next, each string occupies one line, and the length of the string does not exceed 100,
And does not contain spaces.

Examples are as follows

10
PAT
PAAT
AAPATAA
AAPAATAAAA
xPATx
PT
Whatever
APAAATAA
APT
APATTAA

Output format:

The detection result of each string occupies one line,
If the string can get "correct answer",
Then output YES，Otherwise output NO. 

Examples are as follows

YES
YES
YES
YES
NO
NO
NO
NO
NO
NO

analysis

First of all, thank you for your support for the analysis of my first two exercises,
Your support is my motivation!!!

Back to the topic: first, simulate the topic and let it be fate. Don't blame yourself for doing it well
 Reading question: locate the question type as string simulation question

Additional knowledge complements the dividing line----------------------------

In computer science, time complexity, also known as time complexity, is a function that qualitatively describes the running time of the algorithm.

Time complexity analysis:
Remember to click ☞ in the second question PAT class B 1002 write this number
We analyzed the data range and running time
Leading role in our thinking
Don't talk nonsense and go straight to dry goods

Data range

The maximum value of n is 10, and the maximum value of each string length is 100
That is to say, under the limit of the subject data range, it is necessary to access 10 * 100 = 1000 characters to traverse the 10 strings with each length of 100

Running time

The time limit is 400ms, i.e. 0.4s
according to Y total data range and time complexity sharing

When the time limit is 1~2 Seconds,
C++The number of operations in the code is controlled at 10^7∼10^8 For the best.
0 in this question.4s Control the number of operations to 10^6 I'm sure there's no problem
 It can be pushed to traverse all characters up to 1000 times(1000*1000=10^6)

=="Rest assured that various cycles will not appear
TLE(Time Limit Exceeded)

Q1: why consider the maximum data range and the longest running time? (the answer is at the end of the text)

----------------------------Additional knowledge sharing end line

analysis

(1).Condition 1 is well understood, but it is obvious that to solve condition 3, condition 2 must be solved first
 Namely give xPATx It is the judgment of the correct answer.
(2)complete xPATx After determining the correct answer, the aPbTc Yes, write the reasoning aPbATca It is also the correct expression
 The reasoning of the expression is as follows:
from aPbTc If it is correct, it will be consistent XPATx Structure of=>(b='A'And a=c)=>aPATc
 Again aPbATca correct(guess:Every additional one b(Namely'A')Then in c Add 1 string after a)
To sum up, it is bold to speculate:
from aPbATca correct=> aPbbATcaa correct
 from aPbbTcaa correct=> aPbbbTcaaa correct
 from aPbbbTcaaa correct=>............

Test the accuracy of speculation

The example shows that all four cases are correct and consistent with our reasoning

Condition 2 = >
Set string length before 'p' = P_length
------Substring length after'T '= T_length
------And know P from the meaning of the question_ length =T_ length
Correct string length
=(P_length +"PAT" length + T_length)
=(P_length *2)+3)

Condition 3 = >
Setting: A_mnum='P 'to'T' number of 'A',
------'length of substring before p' = P_length,
Correct string length
=(P_length + (A_mnum)*P_length)
=(P_length(A_mnum+1)) + 'P' to'T '

code

#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
	//num[0] records the quantity of 'P', num[1] records the quantity of 'A', and num[2] records the quantity of'T ' 
		int num[3]={0};
		//Set the judgment conditions judge and judge 1 of the two layers and the position of the recording character 'p' and't '
		int jugde=0,judge1=0,p_idx,t_idx;
		string temp;
		cin>>temp;
		for(int i=0;i<temp.length();i++){
			if(temp[i]!='P' && temp[i]!='A' && temp[i]!='T'){
				judge=1;
			}else{
				if(temp[i]=='P'){
					p_idx=i;
					num[0]++; 
					//Ensure that the correct string has only one 'P'
					if(num[0]>1)judge=1;
				}
				else if(temp[i]=='A')num[1]++;
				else if(temp[i]=='T'){
					t_idx=i;
					num[2]++;
					//Ensure that the correct string has only one'T '
					if(num[2]>1)judge=1;
				}
			}
		} 
	//According to the above analysis, it is obvious that we can calculate the length of the correct string according to the derivation results

	//This definition represents the length from 'P' to'T '(including' P 'and'T')
		int PT_length=t_idx-p_idx+1
		if(!judge && (PT_length-1)>=2){
			//Condition 2 Judgment
			 if(temp.length()==(p_idx*2+3))judge1=1;
			//Condition 3 judgment
			 else if(temp.length()==((PT_length-1)*p_idx)+PT_length)judge1=1;
		} 
		if(judge)cout<<"NO"<<endl;
		else{
			if(judge1)cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
		}
	}
	return 0;
} 

answer:

A1:
Because PAT is generally determined by boundary data (such as n=0 and N = 10 in this question)
This is very unfriendly to friends who want to get full marks. In order to reduce such points, we will not be wrong if we consider all the data given by the questioner!!!