首页 > 其他 > 详细

P2562kitty猫基因

时间:2019-07-25 20:07:53      阅读:87      评论:0      收藏:0      [点我收藏+]

这道题是安徽NOI省选题,但是难度并没有那么难。

这道题是一个字符串的递归题,有很多大佬用线段树来写的(我也想学线段树,lowbit当头一棒)。题意为全部相同则输出B或A,不同则分成长度相同的两个子串,并输出C。看到这个便很容易想到递归加二分,但是如何去写上面的函数呢?我顿时想退缩,然后得出策略:枚举子串,假如有不同的则递归二分输出C,直到相同输出A、B。

1.避免出现低级错误,eg.string s[],(mid+1,left),,会耽误很多调试时间

2.熟练运用递归的二分

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define N 100001
using namespace std;
string s;//!
bool flag;
void work(int left,int right){
    flag=true;
    int mid=(left+right)/2;
    for(int i=left+1;i<=right;i++){
        if(s[i]!=s[i-1]){
            flag=false;
            break;
        }
    }
    if(flag==false){
        cout<<"C";
        work(left,mid);
        work(mid+1,right);//!
        return;
    }    
    if(flag==true){
        if(s[left]==0) cout<<"A";
        else if(s[left]==1) cout<<"B";
    }
    return;
}
int main(){
    cin>>s;
    int len=s.length();
    work(0,len-1);//!
    return 0;
} 

 

P2562kitty猫基因

原文:https://www.cnblogs.com/china-mjr/p/11246317.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!