Fang Fang
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1294 Accepted Submission(s): 541
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.
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 .
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.
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
solution:
把前两个直接拼接到最后,然后扫C的位置,看后面是否跟着两个f,注意可能含有其他字母,坑~
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1e6 + 20;
char s[maxn];
int main()
{
int t;
scanf("%d", &t);
for (int k = 1; k <= t;k++)
{
scanf("%s", s);
int flag = 0, len = strlen(s), ans = 0;
s[len] = s[0]; s[len + 1] = s[1];
for (int i = 0; i < len; i++)
if (s[i] == 'c' || s[i] == 'f')continue;
else { flag = 1; break; }
for (int i = 0; i < len&&!flag;i++)
if (s[i] == 'c')
{
if (s[i + 1] == 'f'&&s[i + 2] == 'f')
{
i++;
while (i < len&&s[i] == 'f')
i++;
ans++; i--;
}
else {
flag = 1;
}
}
printf("Case #%d: ", k);
if (flag == 1)printf("-1\n");
else if (ans == 0)printf("%d\n", len / 2 + len % 2);
else printf("%d\n", ans);
}
return 0;
}