题解 P2562 【[AHOI2002]Kitty猫基因编码】

· · 题解

看到楼下一堆大佬都是用的什么前缀和，线段树，我感觉很惭愧啊。

其实这道题只需要按照题意来模拟就好了，可以证明到，最坏的时间复杂度就是O(NlogN),就是101010....交替出现的情况

那么这个复杂度对这道题来说是很优秀的，我们知道c++为我们提供了string类，所以利用string类可以使用"+"运算符的特性，我们写出以下代码

#include<bits/stdc++.h>
using namespace std;
string T(string str)
{
    int sum=0;
    for(int i=0;i<str.length();i++)
    sum+=str[i]-'0';//统计字符串中1的个数
    if(!sum)return "A";//按照题意，全0串返回"A"
    if(sum==str.length())return "B";//全1串返回"B"
    int mid=(str.length()+1)>>1;//计算字符串的一半的长度
    string str1,str2;
    str1=str2="";
    for(int i=0;i<mid;i++)
    str1+=str[i];//暴力截取前半部分
    for(int i=mid;i<str.length();i++)
    str2+=str[i];//暴力截取后半部分
    return "C"+T(str1)+T(str2);//按题意
}
string str;
int main()
{
    cin>>str;
    cout<<T(str)<<endl;//主程序很简单
    return 0;
}