P2562kitty猫基因

这道题是安徽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)/;

    for(int i=left+;i<=right;i++){

        if(s[i]!=s[i-]){

            flag=false;

            break;

        }

    }

    if(flag==false){

        cout<<"C";

        work(left,mid);

        work(mid+,right);//!

        return;

    }

    if(flag==true){

        if(s[left]=='') cout<<"A";

        else if(s[left]=='') cout<<"B";

    }

    return;

}

int main(){

    cin>>s;

    int len=s.length();

    work(,len-);//!

    return ;

}

巴特西

P2562kitty猫基因

最新文章

热门文章