PAT甲级1093 Count PAT

柔光的暖阳◎ 2023-02-14 00:28 144阅读 0赞

在这里插入图片描述
pnum【i】记录对于下标为 i 的位置，其左边的 ’ P ’ 个数；
tnum【i】记录对于下标为 i的位置，其右边’ T ‘的个数；
然后对于每个’A’，以当前A为中心的PAT组合个数就是pnum【i】*tnum【i】，对每个A计算该值，然后累加，输出最后结果即可

  1. #include<iostream>
  2. #include<cstring>
  3. #include<vector>
  4. using namespace std;
  5. int main()
  6. { 
  7.     string s;
  8.     cin>>s;
  9.     vector<int> pnum,tnum;
  10.     vector<int> calculate;//记录需要处理的A下标
  11.     pnum.resize(s.size());
  12.     tnum.resize(s.size());
  13.     int p=0,t=0;
  14.     for(int i=0;i<s.size();i++)
  15.     { 
  16.         if(s[i]=='P')p++;
  17.         else if(s[i]=='A')calculate.push_back(i);
  18.         pnum[i]=p;
  19.     }
  20.     for(int i=s.size()-1;i>=0;i--)
  21.     { 
  22.         if(s[i]=='T')t++;
  23.         tnum[i]=t;
  24.     }
  25.     long long result=0,temp;
  26.     for(int i=0;i<calculate.size();i++)
  27.     { 
  28.         temp=pnum[calculate[i]]*tnum[calculate[i]];
  29.         result+=temp;
  30.         result%=1000000007;
  31.     }
  32.     cout<<result;
  33.     return 0;
  34. }

发表评论

表情：
评论列表 （有 0 条评论，144人围观）

还没有评论，来说两句吧...

相关阅读