Fang Fang HDU - 5455 (思维题)
Fang Fang says she wants to be remembered.
I promise her. We define the sequence FF of strings.
F0 = ‘‘f",F0 = ‘‘f",
F1 = ‘‘ff",F1 = ‘‘ff",
F2 = ‘‘cff",F2 = ‘‘cff",
Fn = Fn−1 + ‘‘f", for n > 2Fn = Fn−1 + ‘‘f", for n > 2
Write down a serenade as a lowercase string SS in a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings in FF, or nothing could be done but put her away in cold wilderness.
I promise her. We define the sequence FF of strings.
F0 = ‘‘f",F0 = ‘‘f",
F1 = ‘‘ff",F1 = ‘‘ff",
F2 = ‘‘cff",F2 = ‘‘cff",
Fn = Fn−1 + ‘‘f", for n > 2Fn = Fn−1 + ‘‘f", for n > 2
Write down a serenade as a lowercase string SS in a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings in FF, or nothing could be done but put her away in cold wilderness.
InputAn positive integer TT, indicating there are TT test cases.
Following are TT lines, each line contains an string SS as introduced above.
The total length of strings for all test cases would not be larger than 106106.OutputThe output contains exactly TT lines.
For each test case, if one can not spell the serenade by using the strings in FF, output −1−1. Otherwise, output the minimum number of strings in FF to split SSaccording to aforementioned rules. Repetitive strings should be counted repeatedly.Sample Input
8 ffcfffcffcff cffcfff cffcff cffcf ffffcffcfff cffcfffcffffcfffff cff cffc
Sample Output
Case #1: 3
Case #2: 2
Case #3: 2
Case #4: -1
Case #5: 2
Case #6: 4
Case #7: 1
Case #8: -1
Hint
Shift the string in the first test case, we will get the string "cffffcfffcff" and it can be split into "cffff", "cfff" and "cff".
题意很简单不说了。
题解：sumf记录f的个数，然后遇见一个c判断一下是不是符合题意，如果‘c’在[0，len-1）区间内,判断一下它的下一个以及下下个是不是f，因为这个字符串是循环串，所以如果这个c是倒数第二个，判断一下最后一个和第一个字符是不是f
如果最后一个字符是c，判断一下第一个和第二个字符是不是f，如果是，sumc++；
不存在的时候就是sumf+sumc！=字符串的长度就行了
代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<stack> 6 #include<queue> 7 #include<map> 8 #include<algorithm> 9 using namespace std; 10 typedef long long ll; 11 int main() 12 { 13 int T,t=1; 14 scanf("%d",&T); 15 while(T--) 16 { 17 string a; 18 cin>>a; 19 20 int len=a.length(); 21 int sumc=0,sumf=0,flag=0; 22 for(int i = 0;i < len;i++) 23 { 24 if(a[i]=='f') 25 sumf++; 26 else if(a[i]=='c') 27 { 28 if(a[i+1]=='f'&&a[i+2]=='f') 29 sumc++; 30 if(i==len-2) 31 { 32 if(a[i+1]=='f'&&a[0]=='f') 33 sumc++; 34 } 35 if(i==len-1) 36 { 37 if(a[0]=='f'&&a[1]=='f') 38 sumc++; 39 } 40 } 41 } 42 printf("Case #%d: ",t++); 43 if(sumc+sumf!=len) 44 printf("-1\n"); 45 else 46 { 47 if(sumc==0) 48 printf("%d\n",sumf+1>>1); 49 else 50 printf("%d\n",sumc); 51 } 52 } 53 return 0; 54 }
卓越教育公司福利 103人发布