【HDU - 5455】Fang Fang（水题，有坑）

题干：

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.

Input

An 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.

Output

The 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".

题目大意：定义递推式F为f(0)='f',f(1)='ff',f(2)='cff',f(n)=f(n-1)+'f'，给出一个首位相连的字符串s，问组成s至少需要多少个F，如果F不能组成s，输出-1.

解题报告：

就是看有多少个c就行了，注意题目中说字符串是小写字母串，但是没说只含有c和f

AC代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cctype>
using namespace std;
typedef long long ll;

int n,len;
char str[1000100];
int main()
{
	int t,i,j,k,cnt=0,nn,ans;
	bool nf;
	cin>>t; getchar();
	for(;t;t--){
		scanf("%s",str);
		nn=nf=0;
		len=strlen(str);
		printf("Case #%d: ",++cnt);
		if(len<=2){
				for(i=0;i<len&&str[i]=='f';i++);
				if(i<len) puts("-1");
				else puts("1");
	
			continue;
		}
		for(i=0;i<len;i++){
			if(str[i]=='c'){
				if(i<len-1&&str[i+1]=='c'||i==len-1&&str[0]=='c')//cc
					nf=1;
				//cfc
				else if(i<len-2&&str[i+1]=='f'&&str[i+2]=='c'||i==len-2&&str[i+1]=='f'&&str[0]=='c'||i==len-1&&str[0]=='f'&&str[1]=='c')
					nf=1;
				else nn++;
				if(nf==1) break;
			}
			else if(str[i]!='f')
				nf=1;
		}
		if(nf) puts("-1");
		else {
			if(nn==0)
				ans=len/2+len%2;
			else ans=nn;
			printf("%d\n",ans);
		}
	}
	return 0;
}