自动搬运

查看原文

来自洛谷，原作者为

	狸狸养的敏敏 **

搬运于2025-08-24 21:39:06，当前版本为作者最后更新于2019-03-02 11:25:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

其实这道题只需要按照题意来模拟就好了，可以证明到，最坏的时间复杂度就是$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;
}