題目
The string APPAPT contains two PAT's as substrings. The first one is formed by the 2nd, the 4th, and the 6th characters, and the second one is formed by the 3rd, the 4th, and the 6th characters.
Now given any string, you are supposed to tell the number of PAT's contained in the string.
Input Specification:
Each input file contains one test case. For each case, there is only one line giving a string of no more than characters containing only P, A, or T.
Output Specification:
For each test case, print in one line the number of PAT's contained in the string. Since the result may be a huge number, you only have to output the result moded by 1000000007.
Sample Input:
APPAPT
Sample Output:
2
題目描述
這道題目描述的是稻扬，給予一個(gè)僅包含‘P’卸例、‘A’和‘T’三個(gè)字母的字符串，然后統(tǒng)計(jì)其中可以組成“PAT”串的子串的個(gè)數(shù)原茅。例如，題目例子：“APPAPT”裁着，有兩個(gè)可以組成“PAT”的子串持钉。（分別是第2，4第练，6個(gè)字符和第3阔馋，4，6個(gè)字符）
題目分析
??這道題目換個(gè)角度想就是一道排列組合的題目娇掏，假設(shè)字符串str[i]=='A'（第i位為“A”）呕寝，以第i位的A來組成的字符串“PAT”個(gè)數(shù) = 這個(gè)“A”的前面字符“P”的數(shù)量 * 這個(gè)“A”的前面字符“T”的數(shù)量。這道題則只需統(tǒng)計(jì)所有字符“A”前面的字符“P”與后面“T”字符的數(shù)量婴梧，然后相乘累加即可下梢。
??如果以常規(guī)方法，枚舉字符串里每個(gè)字符“A”塞蹭，然后再分別從頭以及從尾計(jì)算其“P”和“T”字符的個(gè)數(shù)孽江，其計(jì)算復(fù)雜度會(huì)達(dá)到，算法會(huì)超時(shí)番电。因此岗屏，需要利用字符串里的一些遞推關(guān)系，假設(shè)numP[i]為第i個(gè)字符前“P”字符的個(gè)數(shù)（包含本身），則：
因?yàn)閚umP[i-1]已經(jīng)包含了從字符串0~i-1位字符串“P”的數(shù)量这刷，只需要再看看當(dāng)前的字符是否為P即可婉烟。同理也只需以類似方法記錄字符后面“T”的數(shù)量；然后再從頭開始枚舉崭歧，遇到字符“A”再將其numP與numT相乘累加即可隅很。
#include<stdio.h>
#include<string.h>
char str[100010];
int numP[100010];
int main() {
int length, rightNumT;
long long result;
scanf("%s", str);
length = strlen(str);
result = 0;
memset(numP, 0, sizeof(numP));
for (int i = 0; i < length; i++) {
if (i != 0)
numP[i] = numP[i - 1];
if (str[i] == 'P')
numP[i]++;
}
rightNumT = 0;
for (int i = length - 1; i >= 0; i--) {
if (str[i] == 'T')
rightNumT++;
else if ( str[i] == 'A' )
result = (result + numP[i] * rightNumT) % 1000000007;
}
printf("%d\n", result);
return 0;
}
總結(jié)
???這道題因?yàn)槊總€(gè)“PAT”的組成需要字符‘A’，因此以字符‘A’作為中心率碾，計(jì)算前面‘P’和后面‘T’的個(gè)數(shù)相乘叔营；換個(gè)其他字符，例如我設(shè)置一個(gè)數(shù)組計(jì)算從該字符往后字符“A”與字符“T”的個(gè)數(shù)所宰，然后掃描數(shù)組绒尊，當(dāng)遇到字符“P”時(shí)，result += 后面字符“A”的個(gè)數(shù) * 后面字符“T”的個(gè)數(shù)仔粥，這樣也是可行的婴谱。
???該道題目是如何利用遞推關(guān)系，來快速統(tǒng)計(jì)相應(yīng)字符的個(gè)數(shù)躯泰。這里是設(shè)置一個(gè)數(shù)組來記錄從頭至當(dāng)前位置谭羔，某字符的個(gè)數(shù)，那么當(dāng)前位置i的個(gè)數(shù)就只需前一個(gè)i-1位置的個(gè)數(shù)（已經(jīng)有了從頭至i-1位的個(gè)數(shù)）麦向，再判斷當(dāng)前第i位是否也是該字符瘟裸，即可統(tǒng)計(jì)到從頭至今位置某特定字符的個(gè)數(shù)。
???在做該道題目的時(shí)候诵竭，一開始曾使用過利用兩個(gè)數(shù)組分別記錄前面“P”與后面“T”的個(gè)數(shù)话告，可是僅通過了部分測(cè)試點(diǎn)；也在網(wǎng)絡(luò)上看到也是通過兩個(gè)數(shù)組來解題卵慰，可以通過全部測(cè)試點(diǎn)沙郭。（還沒想到出錯(cuò)的原因）網(wǎng)絡(luò)上柳神有無需使用數(shù)組也可通過的版本，也還沒認(rèn)真了解過其過程裳朋。我最后是依據(jù)書本方法來通過該道題病线。
