公司门户网站制作,淘宝电脑版官网,网站更换logo,有关网站建设的书字符串APPAPT中包含了两个单词“PAT”#xff0c;其中第一个PAT是第2位(P),第4位(A),第6位(T)#xff1b;第二个PAT是第3位(P),第4位(A),第6位(T)。现给定字符串#xff0c;问一共可以形成多少个PAT#xff1f;输入格式#xff1a;输入只有一行#xff0c;包含一个字符串… 字符串APPAPT中包含了两个单词“PAT”其中第一个PAT是第2位(P),第4位(A),第6位(T)第二个PAT是第3位(P),第4位(A),第6位(T)。现给定字符串问一共可以形成多少个PAT输入格式输入只有一行包含一个字符串长度不超过105只包含P、A、T三种字母。输出格式在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大只输出对1000000007取余数的结果。输入样例APPAPT输出样例2错误代码 /************************************************************************* File Name: 1040.c Author: YueBo Function:有几个PAT Created Time: 2016年11月19日 星期六 15时30分09秒************************************************************************/#include stdio.h
#include stdlib.h
#define NUM 1000000007
int main()
{char patString[100000], ch;int i, j, k, N 0, sum 0;while ((ch getchar()) ! \n) {patString[N] ch;N;}for (i 0; i N; i) {for (j i1; j N; j) {for (k j1; k N; k) {if (patString[i] P patString[j] A patString[k] T) {sum;sum sum % NUM;}}}}printf(%d, sum);return 0;
}这个庸俗的算法是地球人都能想到哒下面观察几个量的变化看能否想出一个新算法呢 APPAPT假设第一个位置是0最后一个位置是5aCnt表示A的数量apCnt表示AP组合的数量aptCnt表示APT组合的数量。
0-- pCnt 0 paCnt 0 patCnt 0
1-- pCnt 1 paCnt 0 patCnt 0
2-- pCnt 2 paCnt 0 patCnt 0
3-- pCnt 2 paCnt 02 patCnt 0
4-- pCnt 3 paCnt 2 patCnt 0
5-- pCnt 3 patCnt 2 patCnt 2
结合下面的代码可理解上面的过程
/************************************************************************* File Name: 1040_1.c Author: YueBo Function: Created Time: 2016年11月19日 星期六 23时40分11秒************************************************************************/#include stdio.h
#include stdlib.h#define NUM 1000000007
int main()
{long long pCnt 0, paCnt 0, patCnt 0;char ch;while ((ch getchar()) ! \n) {if (ch P) {pCnt;} else if (ch A) {paCnt pCnt;} else {patCnt paCnt;patCnt % NUM;}}printf(%lld, patCnt);return 0;
}
