題干：

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')//ccnf=1;//cfcelse 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; }

?

總結

以上是生活随笔為你收集整理的【HDU - 5455】Fang Fang（水题，有坑）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。