判斷規(guī)則
這道題一共有三個(gè)規(guī)則:
- 字符串中必須僅有P, A, T這三種字符桶略,不可以包含其它字符;
- 任意形如 xPATx 的字符串都可以獲得“答案正確”诲宇,其中 x 或者是空字符串际歼,或者是僅由字母 A 組成的字符>串;
- 如果 aPbTc 是正確的姑蓝,那么 aPbATca 也是正確的鹅心,其中 a, b, c 均或者是空字符串,或者是僅由字母 A 組>成的字符串纺荧。
我們先假設(shè)一個(gè)組合—— xPATy旭愧, x, y表示的是x, y個(gè)A的組合,比如:2PAT2 代表的是 AAPATAA宙暇。
有了這個(gè)組合输枯,接下來(lái)分析就很方便了。
- 要滿(mǎn)足1客给,意味著x用押,y=0,就這么簡(jiǎn)單靶剑。
- 要滿(mǎn)足2蜻拨,意味著x=y池充,就可以了,1是2的一種特殊情況缎讼,為了方便收夸,我們直接把組合改為xPATx好了。
- 它是從已有的滿(mǎn)足的條件情況不斷迭代生成了血崭,由1和2我們知道滿(mǎn)足的組合為xPATx卧惜,然后我們要從這個(gè)組合衍生出3的組合。由規(guī)則夹纫,我們舉幾個(gè)例子:xPATx, xPAATxx, xPAAATxxx(APATA, APAATAA, APAAATAAA)咽瓷,當(dāng)然,x表示幾個(gè)A都是一樣的舰讹。
看出關(guān)系了嗎茅姜? 左邊A數(shù)量=中間A數(shù)量*右邊A數(shù)量,上面3個(gè)都是滿(mǎn)足這個(gè)公式的月匣。那么代碼里钻洒,我們就把三個(gè)位置A的數(shù)量記錄下來(lái),判斷是否滿(mǎn)足公式就行了锄开。
測(cè)試點(diǎn)
有兩個(gè)測(cè)試點(diǎn)是我自己做的時(shí)候卡了半天的:
PT
APATAA
大家寫(xiě)的時(shí)候注意一下
代碼
廢話不多說(shuō)素标,上代碼
/*
本題需要注意的有兩個(gè)測(cè)試點(diǎn): PT APATAA
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main() {
char str[100];
int n;
int isRight = 0; // 判斷是否正確的標(biāo)志
int str_len;
int i, j;
int num_A1, num_A2, num_A3; // 分別為P前面的A數(shù)量,中間數(shù)量萍悴,T后面的A數(shù)量
int temp;
scanf("%d", &n);
char *answer[n]; // 用來(lái)保存答案
for (i = 0; i < n; i++) {
scanf("%s", str);
num_A1 = num_A2 = num_A3 = 0;
str_len = strlen(str);
for (j = 0; j < str_len; j++) {
// 我們根據(jù)規(guī)則头遭,在遇到P之前。必須是A或者空字符退腥,一旦出現(xiàn)A或P之外的任岸,直接GG
if (str[j] != 'A' && str[j] != 'P') {
isRight = 0;
break;
}
// 開(kāi)始統(tǒng)計(jì)P前面A的數(shù)量了
if (str[j] == 'A') {
num_A1++;
}
// 遇到P了再榄,開(kāi)始判斷是否符合規(guī)則狡刘,如果這次不符合,就沒(méi)有下次了
if (str[j] == 'P') {
for (j; j < str_len; j++) {
// 統(tǒng)計(jì)中間A的數(shù)量
if (str[j] == 'A') {
num_A2++;
}
// 碰到T困鸥,說(shuō)明該結(jié)束了嗅蔬,就看T后面的A夠不夠了
if (str[j] == 'T') {
// A都沒(méi)有,直接GG
if (num_A2 == 0) break;
j += 1;
// 如果字符串到temp還不結(jié)束疾就,那就說(shuō)明符合規(guī)則的A數(shù)量字符后面還有東西澜术,這不是破壞了前面的陣型了嘛,GG
temp = j + num_A1 * num_A2;
if (str_len > temp) break;
// 統(tǒng)計(jì)T后面A的數(shù)量滿(mǎn)不滿(mǎn)足規(guī)則要求的數(shù)量
for (j; j < temp; j++) {
if (str[j] == 'A') {
num_A3++;
}
}
// 這就是我總結(jié)規(guī)則得出來(lái)的三個(gè)位置A的數(shù)量關(guān)系猬腰,滿(mǎn)足了就好了鸟废,而且一旦這個(gè)滿(mǎn)足,字符串也就到頭了
if (num_A3 == num_A1 * num_A2 && j == str_len) {
isRight = 1;
}
}
}
}
}
if (isRight == 0) {
answer[i] = "NO";
}
else {
answer[i] = "YES";
}
isRight = 0;
}
for (i = 0; i < n; i++) {
printf("%s\n", answer[i]);
}
return 0;
}
···