hdu 5455 Fang Fang

发布时间：2020-12-13 21:31:29 所属栏目：PHP教程来源：网络整理

导读：F题 Fang Fang 链接：http://acm.hdu.edu.cn/showproblem.php?pid=5455 题意：F0 = f F1 = ff F2 = cff 后面的每一个在前一个基础上加一个f 求一个字符串首尾相连最少用多少个F可以表示完思路：分有c和无c的情况，无c时则全部由F0 和F1 组成有c时则考虑c后

F题 Fang Fang

链接：http://acm.hdu.edu.cn/showproblem.php?pid=5455

题意：F0 = f

　　　F1 = ff

　　　F2 = cff

　　　后面的每一个在前一个基础上加一个f

　　　求一个字符串首尾相连最少用多少个F可以表示完

思路：分有c和无c的情况，无c时则全部由F0 和F1 组成

有c时则考虑c后的f个数至少为2，首尾的f可单独计数再比较（

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 #include <cstring>
 6 
 7 using namespace std;
 8 
 9 const int N = 1e6 + 10;
10 char str[N],ch[2];
11 
12 int main()
13 {
14     int t,ca = 0,ans;
15     cin>>t;
16     while(t -- ){
17         ca ++ ;
18         ans = 0;
19         printf("Case #%d: ",ca);
20         int flag1 = 0;//flag1首有多少f,flag3中有多少f
21         bool flag2 = false;//flag2:是否遇见c
22         scanf("%s",str);
23         gets(ch);
24         bool f = true;
25         int l = strlen(str);
26         for(int i = 0,j = 1; i < l; i += j,j = 1){
27             int flag3 = 0;
28 
29             if(!flag2 && str[i] == ‘f‘) flag1 ++ ;
30             else flag2 = true;
31             if(flag2){
32                 while(str[i+j] == ‘f‘){
33                     flag3 ++ ;
34                     j ++ ;
35                 }
36                 if(flag3 <= 1 && i + j <= l - 1) f = false;
37 
38                 if((i == l - 1 && str[i] == ‘c‘) || (i + j == l)){
39                     if(flag3 + flag1 <= 1) f = false;
40                 }
41                 if(!f) break;
42                 else ans ++ ;
43             }
44             if(!flag2 && i == l - 1){
45                 if(flag1 % 2 == 1) ans = flag1 / 2 + 1;
46                 else ans = flag1 / 2;
47             }
48         }
49         if(f) printf("%dn",ans);
50         else printf("-1n");
51     }
52     return 0;
53 }

View Code

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!