1003.我要通過(guò)!

判斷規(guī)則

這道題一共有三個(gè)規(guī)則:

  1. 字符串中必須僅有P, A, T這三種字符桶略,不可以包含其它字符;
  2. 任意形如 xPATx 的字符串都可以獲得“答案正確”诲宇,其中 x 或者是空字符串际歼,或者是僅由字母 A 組成的字符>串;
  3. 如果 aPbTc 是正確的姑蓝,那么 aPbATca 也是正確的鹅心,其中 a, b, c 均或者是空字符串,或者是僅由字母 A 組>成的字符串纺荧。

我們先假設(shè)一個(gè)組合—— xPATy旭愧, x, y表示的是x, y個(gè)A的組合,比如:2PAT2 代表的是 AAPATAA宙暇。
有了這個(gè)組合输枯,接下來(lái)分析就很方便了。


  1. 要滿(mǎn)足1客给,意味著x用押,y=0,就這么簡(jiǎn)單靶剑。
  2. 要滿(mǎn)足2蜻拨,意味著x=y池充,就可以了,1是2的一種特殊情況缎讼,為了方便收夸,我們直接把組合改為xPATx好了。
  3. 它是從已有的滿(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;
}
···
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末姑荷,一起剝皮案震驚了整個(gè)濱河市盒延,隨后出現(xiàn)的幾起案子缩擂,更是在濱河造成了極大的恐慌,老刑警劉巖添寺,帶你破解...
    沈念sama閱讀 211,423評(píng)論 6 491
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件胯盯,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡计露,警方通過(guò)查閱死者的電腦和手機(jī)博脑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,147評(píng)論 2 385
  • 文/潘曉璐 我一進(jìn)店門(mén),熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)票罐,“玉大人叉趣,你說(shuō)我怎么就攤上這事「醚海” “怎么了君账?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,019評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)沈善。 經(jīng)常有香客問(wèn)我乡数,道長(zhǎng),這世上最難降的妖魔是什么闻牡? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,443評(píng)論 1 283
  • 正文 為了忘掉前任净赴,我火速辦了婚禮,結(jié)果婚禮上罩润,老公的妹妹穿的比我還像新娘玖翅。我一直安慰自己,他們只是感情好割以,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,535評(píng)論 6 385
  • 文/花漫 我一把揭開(kāi)白布金度。 她就那樣靜靜地躺著,像睡著了一般严沥。 火紅的嫁衣襯著肌膚如雪猜极。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 49,798評(píng)論 1 290
  • 那天消玄,我揣著相機(jī)與錄音跟伏,去河邊找鬼。 笑死翩瓜,一個(gè)胖子當(dāng)著我的面吹牛受扳,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播兔跌,決...
    沈念sama閱讀 38,941評(píng)論 3 407
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼勘高,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了?” 一聲冷哼從身側(cè)響起华望,我...
    開(kāi)封第一講書(shū)人閱讀 37,704評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤层亿,失蹤者是張志新(化名)和其女友劉穎,沒(méi)想到半個(gè)月后立美,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體匿又,經(jīng)...
    沈念sama閱讀 44,152評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,494評(píng)論 2 327
  • 正文 我和宋清朗相戀三年建蹄,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了碌更。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 38,629評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡洞慎,死狀恐怖痛单,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情劲腿,我是刑警寧澤旭绒,帶...
    沈念sama閱讀 34,295評(píng)論 4 329
  • 正文 年R本政府宣布,位于F島的核電站焦人,受9級(jí)特大地震影響挥吵,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜花椭,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,901評(píng)論 3 313
  • 文/蒙蒙 一忽匈、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧矿辽,春花似錦丹允、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,742評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至宾娜,卻和暖如春批狐,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背碳默。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 31,978評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工贾陷, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人嘱根。 一個(gè)月前我還...
    沈念sama閱讀 46,333評(píng)論 2 360
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像巷懈,于是被迫代替她去往敵國(guó)和親该抒。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,499評(píng)論 2 348

推薦閱讀更多精彩內(nèi)容