1040 有几个PAT （25 分）

做这道题目，遇到了新的困难。解决之后有了新的收获，甚是欣喜！

刚开始我用三个vector数组存储P A T三个字符出现的位置，然后三层for循环，根据字符次序关系，

统计PAT出现的次数。这样提交后三个测试点超时。代码如下：

 #include <bits/stdc++.h>

 using namespace std;

 int num=;

 char str[];

 vector<int> p;

 vector<int>    a;

 vector<int>    t;

 int main()

 {

     scanf("%s",str);    //输入指定字符串

     int count=;

     for(int i=;i<strlen(str);i++)

     {

         if(str[i]=='P')

             p.push_back(i);

         else if(str[i]=='A')

             a.push_back(i);

         else

             t.push_back(i);

     }

     for(int i=;i<p.size();i++)

     {

         for(int j=;j<a.size();j++)

         {

             for(int k=;k<t.size();k++)

             {

                 if(p[i]<a[j]&&a[j]<t[k])

                     count++;

             }

         }

     }

     printf("%d",count%num);

     return ;

 }

后来改进为两层for循环，依旧超时！冥思苦想不得其解，不得已求助网上大神。

具体思想：要想知道构成多少个PAT，那么遍历字符串后对于每一个A，它前面的P的个数和它后面的

T的个数的乘积就是能构成PAT的个数。然后依次累加每个A的结果即可。

统计当前字符A的前面的P的个数简单容易

那么怎么统计当前字符A的后面的T的个数呢？

可以先遍历整个字符串统计整个字符串中T的个数。可以再下一次遍历时，遇到一个T就做一次自减操作，

这样就可以得到当前字符A的后面的T的个数。

整个算法伪代码如下

先遍历整个字符串，统计T的个数countT

遍历整个字符串

若遇到P，当前字符前的P的个数++,countP++

若遇到T，countT--，表示当前字符A后的T的个数

若遇到字符A，统计当前字符A可以构成多少个PAT，即countP*countT，然后累加每次A的结果。

 #include <bits/stdc++.h>

 using namespace std;

 char str[];

 int main()

 {

     scanf("%s",str);

     int ans=;

     int countP,countT;

     countP=countT=;

     //先统计整个字符串中T的个数即countT

     for(int i=;i<strlen(str);i++)

     {

         if(str[i]=='T')

             countT++;

     }

     for(int i=;i<strlen(str);i++)

     {

         if(str[i]=='P')

             countP++;

         else if(str[i]=='T')

             countT--;//总的T的个数减去待统计字符A的之前的T的个数，等于待统计A的之后的T的个数，秒！

         else

             ans=(ans+countP*countT)%;

     }

     printf("%d",ans);

     return ;

 }

巴特西

1040 有几个PAT （25 分）

最新文章

热门文章