Fang Fang
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Problem Description
Fang Fang says she wants to be remembered.
I promise her. We define the sequence F of strings.
F0 = “f”,
F1 = “ff”,
F2 = “cff”,
Fn = Fn?1+“f”, for n>2
Write down a serenade as a lowercase string S in a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings in F , or nothing could be done but put her away in cold wilderness.
I promise her. We define the sequence F of strings.
F0 = “f”,
F1 = “ff”,
F2 = “cff”,
Fn = Fn?1+“f”, for n>2
Write down a serenade as a lowercase string S in a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings in F , or nothing could be done but put her away in cold wilderness.
Input
An positive integer
T , indicating there are
T test cases.
Following are T lines, each line contains an string S as introduced above.
The total length of strings for all test cases would not be larger than 106 .
Following are T lines, each line contains an string S as introduced above.
The total length of strings for all test cases would not be larger than 106 .
Output
The output contains exactly
T lines.
For each test case, if one can not spell the serenade by using the strings in F , output ?1 . Otherwise, output the minimum number of strings in F to split S according to aforementioned rules. Repetitive strings should be counted repeatedly.
For each test case, if one can not spell the serenade by using the strings in F , output ?1 . Otherwise, output the minimum number of strings in F to split S according 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: -1HintShift the string in the first test case, we will get the string "cffffcfffcff" and it can be split into "cffff", "cfff" and "cff".
Source
2015 ACM/ICPC Asia Regional Shenyang Online
/*********************************************************************/
题意：给你一个由小写字母组成的循环字符串S(循环字符串的意思是你可以从任意位置i开始，顺时针经过n回到i-1的位置)，问至少需要序列F中的多少项才能组成字符串S
序列F的格式是F 0 ="f",F 1 ="ff",F 2 ="cff",F n =F n-1 +"f"，即F 3 ="cfff",F 4 ="cffff",……对于样例1,"ffcfffcffcff"，我们可以以从左到右第一个字符'c'为起点，那么这个串可以转化为"cfffcffcffff"，这样字符串S则可以由"cfff"、"cff"、"cffff"3项组成；
对于样例3,"cffcff"，字符串S由"cff"、"cff"两项组成；
对于样例4,"cffcf"，"cf"不是序列F里的项，所以输出"-1"；
对于样例8,"cffc"，"c"也不是序列F里的项，故输出"-1"
由此可见，我们只需找到字符串S中的第一个字符'c'，然后遍历整个字符串，判断有多少个符合序列F项(符合序列F项的意思是没有"c"、"cf"这样的带'c'的项)的字符'c'有多少个即为所求
需要注意的一点是，字符串S可能还有除'c'与'f'以外的其他字符，这样也要输出"-1"
然而对于字符串如果全为'f'，即不出现除'f'以外的其他字符(包括字符'c')，那么我们需判断字符串长度的奇偶性，如果为偶，意味着我们可以只由"ff"项组成，ans=strlen(s)/2；否则，还需一项"f",ans=strlen(s)/2+1
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 1000005;
const int inf = 1000000000;
const int mod = 2009;
char s[N];
int main()
{int n,k=1,l,i,j,ans,c,flag;scanf("%d",&n);while(n--){scanf("%s",s);l=strlen(s);flag=1;printf("Case #%d: ",k++);for(c=2,ans=-1,i=0;i<l&&s[i]!='c';i++);if(i==l)flag=2;for(j=i;i<=l+j;i++)if(s[i%l]=='c'){if(c<2)flag=0;ans++;c=0;}else if(s[i%l]=='f')c++;elseflag=0;if(flag==1)printf("%d\n",ans);else if(flag==2)printf("%d\n",l%2?l/2+1:l/2);elseputs("-1");}return 0;
}