題解

對于字符串中每個A而言，若其前面有m個P，后面有n個T，可以得到對于當前的A，能夠組成m*n種情況的PAT。

因此找到A的位置，用A左邊P的個數(shù)*A右邊T的個數(shù)即可。

題解1：我的解法 C++

時間復雜度O(n)

當前位置左邊P的個數(shù)、當前位置左邊T的個數(shù)存儲方式如下：

#include<iostream> #include<string> #define SIZE 100000 using namespace std; int main() {string str;cin >> str;int len = str.length();//存儲累計字母個數(shù) 避免重復計算int countP[SIZE] = { 0 };//當前位置左邊P的個數(shù)int countT[SIZE] = { 0 };//當前位置左邊T的個數(shù)int PP = 0;//P的累計個數(shù)int TT = 0;//T的累計個數(shù)for (int i = 0; i < len; i++) {countP[i] = PP;countT[i] = TT;if (str[i] == 'P') {PP++;}else if (str[i] == 'T') {TT++;}}int total = 0;int P = 0;int T = 0;for (int i = 0; i < len; i++) {if (str[i] == 'A') {total += countP[i] * (TT - countT[i]);//當前位置 左邊P的個數(shù)*右邊T的個數(shù)total %= 1000000007;}}cout << total;system("pause"); }

題解2：別人的解法

其實思路差不多，但是寫起來很簡潔！

#include <bits/stdc++.h> using namespace std;int main(int argc, char const *argv[]){string s;cin >> s;int T = 0, P = 0;for (int i = 0; i < s.length(); ++i){if(s[i]=='T') T++;}long long res = 0;for (int i = 0; i < s.length(); ++i){if(s[i]=='P') P++;if(s[i]=='T') T--;if(s[i]=='A') res += P*T;}cout << res%1000000007 << endl;return 0; }

總結

以上是生活随笔為你收集整理的【PAT甲级 排列组合】1093 Count PAT's (25 分) C++ 全部AC的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。