Fang Fang
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 945 Accepted Submission(s): 393
Problem Description
Fang Fang says she wants to be remembered.
I promise her. We define the sequenceF of
strings.
F0 = ‘‘f",
F1 = ‘‘ff",
F2 = ‘‘cff",
Fn = Fn−1 + ‘‘f", for n > 2
Write down a serenade as a lowercase stringS in
a circle, in a loop that never ends.
Spell the serenade using the minimum number of strings inF ,
or nothing could be done but put her away in cold wilderness.
I promise her. We define the sequence
Write down a serenade as a lowercase string
Spell the serenade using the minimum number of strings in
Input
An positive integer T ,
indicating there are T test
cases.
Following areT lines,
each line contains an string S as
introduced above.
The total length of strings for all test cases would not be larger than106 .
Following are
The total length of strings for all test cases would not be larger than
Output
The output contains exactly T lines.
For each test case, if one can not spell the serenade by using the strings inF ,
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
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".
水题，实际上就是查cff的个数。唯一的坑就是全部是f时要判断一下。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
long long test;
char a[1000005];
int main()
{
long long i, j, h, k, len, res, res_count;
int flag;
cin >> test;
for (i = 1; i <= test; i++)
{
cin >> a;
len = strlen(a);
flag = 1;
res = 0;
for (h = 0; h < len; h++)
{
if (a[h] == 'c')
{
flag = 2;
if (a[(h + 1) % len] == 'f'&&a[(h + 2) % len] == 'f')
{
h = h + 2;
res++;
}
else
{
flag = 0;
break;
}
}
else if (a[h] == 'f')
{
continue;
}
else
{
flag = 0;
break;
}
}
if (flag == 0)
{
cout << "Case #" << i << ": " << -1 << endl;
}
else if (flag == 2)
{
cout << "Case #" << i << ": " << res << endl;
}
else
{
cout << "Case #" << i << ": " << (len+1)/2 << endl;
}
}
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。