Chicken brother is very happy today, because he attained N pieces of biscuits whose tastes are A or B. These biscuits are put into a box. Now, he can only take out one piece of biscuit from the box one time. As we all know, chicken brother is a creative man. He wants to put an A biscuit and a B biscuit together and eat them. If he take out an A biscuit from the box and then he take out a B biscuit continuously, he can put them together and eat happily. Chicken brother’s happiness will plus one when he eat A and B biscuit together one time.
Now, you are given the arrangement of the biscuits in the box(from top to bottom) ,please output the happiness of Chicken Brother when he take out all biscuit from the box.
The first line is an integer indicates the number of test cases.
In each case, there is one line includes a string consists of characters ‘A’ and ‘B’.
The length of string is not more than 1000000.
For each test case:
The first line output “Case #k:", k indicates the case number.
The second line output the answer.
1
ABABBBA
Case #1:
2
题解:
特别提醒:此题出题人已挖好大坑等着萌新们入坑,我也是第一次遇到这种100W就TL的情况,原因我给你们分析一下,就是这个strlen的应用,之前我将strlen放在for循环内,复杂度为100W*100W,O(n^2)必然超时,只要把strlen提出来,复杂度降为100W+100W,O(n+n),神TM知道这个函数调用也会TL!
下面附上AC代码:
1 #include <bits/stdc++.h>
2 using namespace std;
3 char s[1000010];
4 int main()
5 {
6 int n;
7 while(cin>>n)
8 {
9 int ans=0;
10 for(int i=1;i<=n;i++)
11 {
12 scanf("%s",s);
13 printf("Case #%d:\n",i);
14 int len=strlen(s);
15 int ans=0;
16 for(int j=0;j<len;j++)
17 {
18 if(s[j]=='A'&&s[j+1]=='B')
19 ans++;
20 }
21 printf("%d\n",ans);
22 }
23 }
24 return 0;
25 }