記錄：PAT basic level 1003

2021.7.28

• 題目
• 了解
• 連結
• 代碼解讀（個人水準限制）

題目

“答案正确”是自動判題系統給出的最令人歡喜的回複。本題屬于 PAT 的“答案正确”大派送 —— 隻要讀入的字元串滿足下列條件，系統就輸出“答案正确”，否則輸出“答案錯誤”。

得到“答案正确”的條件是：

字元串中必須僅有 P、 A、 T這三種字元，不可以包含其它字元；

任意形如 xPATx 的字元串都可以獲得“答案正确”，其中 x 或者是空字元串，或者是僅由字母 A 組成的字元串；

如果 aPbTc 是正确的，那麼 aPbATca 也是正确的，其中 a、 b、 c 均或者是空字元串，或者是僅由字母 A 組成的字元串。

現在就請你為 PAT 寫一個自動裁判程式，判定哪些字元串是可以獲得“答案正确”的。

輸入格式：

每個測試輸入包含 1 個測試用例。第 1 行給出一個正整數 n (<10)，是需要檢測的字元串個數。接下來每個字元串占一行，字元串長度不超過 100，且不包含空格。

輸出格式：

每個字元串的檢測結果占一行，如果該字元串可以獲得“答案正确”，則輸出 YES，否則輸出 NO。

了解

一開始對題目隻是以為對字元串數組的應用掌握程度，于是在string與對其中字元的讀取統計下功夫，最後送出發現全是錯誤。無奈隻能求助于前輩的經驗，結果在忽然的一篇部落格中獲得答案—其中的詳細解答就不再贅述，下附部落格連結可直接觀看。

連結

link

代碼解讀（個人水準限制）

本人因為學習程度問題也是第一次遇見

map<char, int> m;

，整個代碼的核心就在于這個容器，map實用性感覺非常高，如讀者有餘力可以進行觀看學習，在此則不附上連結。

for(int j = 0; j < s.size(); j++) {
            m[s[j]]++;
            if (s[j] == 'P') p = j;
            if (s[j] == 'T') t = j;
        }
           

此處

m[s[j]]++

是通過循環

s[j]

從前向後不斷讀取字元，以此存入

m

對象中，且存儲時自加以計數。

if (s[j] == 'P') p = j;

語句中，得出‘P’在字元串中的索引并以‘p’來存儲，下句’T’同理。

m['P'] == 1 && m['A'] != 0 && m['T'] == 1 && m.size() == 3 
&& t-p != 1 && p * (t-p-1) == s.length()-t-1)
           

擔心長度影響閱讀，自己加了個回車。這句真的太美太優雅了，以作者初學者身份真的大受震撼。

m['P'] == 1

是對

m

對象中存儲的‘P’進行判定—是否存在且隻有一個，後‘T’‘A’同理；

m.size() == 3

是判定容器中是否有且隻有此三個要求字元；

t-p != 1

要求‘P’與‘T’不能相鄰，即在兩者之間必須擁有一個空隙來存放一個‘A’；

p * (t-p-1) == s.length()-t-1)

通過對題目的分析，要‘P’之前的‘A’個數乘‘P’和‘T’之間的‘A‘的個數等于’T‘之後的’A‘個數。

p

即是’P‘之前的個數，

t-p-1

則是中間的個數，

s.length()-t-1

則是結果即後面的’A’個數。

真希望自己什麼時候也能有這種思路，這種代碼。