网站开发里的输入,医院网站php源码,有关建设旅行网站的建设,公司网站建设费会计分录题目
字符串 APPAPT 中包含了两个单词 PAT#xff0c;其中第一个 PAT 是第 2 位(P#xff09;#xff0c;第 4 位(A)#xff0c;第 6 位(T)#xff1b;第二个 PAT 是第 3 位(P#xff09;#xff0c;第 4 位(A)#xff0c;第 6 位(T)。
现给定字符串#xff0c;问一…题目
字符串 APPAPT 中包含了两个单词 PAT其中第一个 PAT 是第 2 位(P第 4 位(A)第 6 位(T)第二个 PAT 是第 3 位(P第 4 位(A)第 6 位(T)。
现给定字符串问一共可以形成多少个 PAT
输入格式
输入只有一行包含一个字符串长度不超过10 5 只包含 P、A、T 三种字母。
输出格式
在一行中输出给定字符串中包含多少个 PAT。由于结果可能比较大只输出对 1000000007 取余数的结果。
输入样例
APPAPT输出样例
2分析
先看一个比较复杂的字符串APPATTAAPATTAPAT共有2 * 5 2 * 3 2 * 3 3 * 3 3 * 1 4 * 1 38可以发现每一个’A’构成的PAT是它前面的P的数目乘以它后面T的数目。总数把每个’A’构成的PAT数目加起来就可以了。多次遍历暴力求肯定不行因为限时150ms所以一次遍历就要解决。继续观察越往后P越大T越小。所以可以先遍历一次把T的数目求出来。然后每当遍历到P就自增遍历到T就自减遍历到A就把当前的P的数目乘以T的数目并累加。为防止溢出结果要用long long存。
AC代码
#includeiostream
using namespace std;
int main()
{string s;int i,p0,t0;long long rst0;cins;int lens.length();for(i0; ilen; i){if(s[i]T)t;}for(i0; ilen; i){if(s[i]P)p;else if(s[i]T)t--;elserstrst(p*t);}rstrst%1000000007;coutrst;return 0;
}更多题解 pat 乙级(Basic Level) 题解汇总持续更新C
