Kitty猫基因编码

原题链接：https://www.luogu.org/problemnew/show/2562#sub

简单的递归题。记录一下前缀和然后二分求解就好。

参考代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 2000005
using namespace std;
int s[maxn];
int num;
void find(int l,int r){
    if (s[r] - s[l-1] == 0){
        printf("A");
        return;
    }

    if (s[r] - s[l-1] == r - l + 1){
        printf("B");
        return ;
    }
    printf("C");
    int mid = (l + r) >> 1;
    find(l,mid);
    find(mid+1,r);
}
int main(){
    while (1){
        char c = getchar();
        if (c != '0' && c != '1')
            break;
        s[++num] = s[num-1] + c - '0';
    }
    find(1,num);
    return 0;
}