1040 有几个PAT c++_综合

一级标题 1040 有几个PAT c++

今天做一题通过率0.27的PAT
每次扫描到A，用这个A组成的PAT刚好是A前面的P数量乘以A后面T的数量
然后相加
心情可谓是一言难尽
在这里插入图片描述
前三个测试点都过后两个测试点超时。
如果不超时算法应该没问题。
去搜了一下别人写的，是真简单；
自己写的结果

//自己写的代码超时，后两个测试点
#include<iostream>
using namespace std;
#include<string>
#include<vector>
int main()
{
    string str1;cin >> str1;int pos1 = str1.find('P');int pos2 = str1.rfind('T');string str2 = str1.substr(pos1, pos2 - pos1+1);vector<char>str;//cout << str2 << endl;for (int i = 0; i < str2.size(); i++){
    str.push_back(str2[i]);}int sum = 0;for (int i = 0; i < str.size(); i++){
    if (str[i] == 'A'){
    int count1 = 0;int count2 = 0;for (int j = 0; j < i; j++){
    if (str[j] == 'P'){
    count1++;}}for (int j = i+1; j < str.size(); j++){
    if (str[j] == 'T'){
    count2++;}}//cout << count1 << " " << count2 << endl;vector<char>::iterator pos1 = str.begin() + i;str.erase(pos1);//把当前A删除，计算下一个//str[i] = 'Q';sum += (count1 * count2) % 1000000007;}}cout << sum;return 0;
}

后来看别人写的

#include<iostream>
using namespace std;
int main(){
    string str;cin>>str;int count=0;int countP=0,countT=0;int Len=str.size();//PAT数量等于字符数组之中每个A左边的P的数量与右遍的T的数量的乘积for(int i=0;i<Len;i++){
    if(str[i]=='T'){
    countT++;}}	for(int i=0;i<Len;i++){
    if(str[i]=='P'){
    countP++;}if(str[i]=='T'){
    countT--;}if(str[i]=='A'){
    //cout<<countP<<" "<<countT<<endl;count=(count+countP*countT)%1000000007 ;}	}cout<<count;return 0;
}

在这里插入图片描述