字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)。
现给定字符串,问一共可以形成多少个PAT?
输入格式:
输入只有一行,包含一个字符串,长度不超过105,只包含P、A、T三种字母。
输出格式:
在一行中输出给定字符串中包含多少个PAT。由于结果可能比较大,只输出对1000000007取余数的结果。
输入样例:
1 |
APPAPT |
输出样例:
1 |
2 |
注意优化……三重循环能解,但是一定会超时!
思路大体是这样的:
- 读入字符串,通过声明的结构体数组count实现对字符串的重新储存和计数,重新处理即为对相邻重复字符串的合并与计数。
- 从count末端开始,把T的计数向前依次叠加至距离其前最近的A的next上,获得每个A后有多少个T。
- 仍然从count末端开始,把每个A所对应的num*next,即此处后AT总个数向前叠加至A的num上(这里我当时应该是写烦了,感觉最好是P的next上,尽管效果都一样),这样每个A的位置就储存了其(包括它自身)后方共有多少个AT。
- 从count前端开始,累加(每个P的num*其后第一个A的num)计算PAT的数量。
代码如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
#include<stdio.h> struct { char c; long num; long next; }count[100001],*pcount,*pcount_e; int main() { char buf[100001]=" "; int i,j,k; long result=0,count_t=0,count_a=0; pcount=count; gets(buf); count[0].c=buf[0]; count[0].num++; for(i=1;buf[i];i++) { if(buf[i]==pcount->c) { (pcount->num)++; } else { pcount++; pcount->c=buf[i]; pcount->num++; } } pcount_e=pcount+1; pcount_e->c='T'; pcount_e->num=0; for(i=0;pcount+i>count;i--) { if((pcount+i)->c=='T') { (pcount+i)->num+=count_t; count_t=(pcount+i)->num; } else if((pcount+i)->c=='A') { (pcount+i)->next=count_t; (pcount+i)->num*=(pcount+i)->next; (pcount+i)->num+=count_a; count_a=(pcount+i)->num; } } /* count_t=0; for(i=0;pcount+i>count;i--) { if((pcount+i)->c=='A') { for(j=i+1;pcount+j<=pcount_e;j++) { if((pcount+j)->c=='T') { (pcount+i)->next=(pcount+j)->num; break; } } (pcount+i)->num*=(pcount+i)->next; (pcount+i)->num+=count_t; count_t=(pcount+i)->num; } }*/ for(i=0;count+i<pcount-1;i++) { if(count[i].c=='P') { for(j=i+1;count+j<pcount_e;j++) { if(count[j].c=='A') { result+=(count[i].num*count[j].num); result%=1000000007; break; } } } } /* for(i=0;count+i<pcount_e;i++) { temp[0]=1; if(count[i].c=='P') { temp[0]*=count[i].num; temp[1]=0; for(j=i+1;count+j<pcount_e;j++) { if(count[j].c=='A') { temp[2]=1; temp[2]*=count[j].num; temp[2]*=count[j].next; temp[1]+=temp[2]; } } temp[0]*=temp[1]; result+=temp[0]; result%=1000000007; } }*/ printf("%dn",result); } |