本文主要是介绍P2562 [AHOI2002]Kitty猫基因编码(洛谷),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
小可可选修了基础生物基因学。教授告诉大家 Super Samuel 星球上 Kitty猫的基因的长度都是 2 的正整数次幂 ), 全是由两种不同的基因单元组成的。 这两种不同的基因单元分别记成 0 和 1,于是 Kitty 猫基因可以写成一个 01 串表达式 。
为了便于分析和降低数据存储量,教授发明了 ABC 编码规则。该编码规则是不断地按照
对 Kitty 猫基因 01 串表达式 进行改写, 直至最终被改写成只含有字符 “ A”、“ B”、“ C”的符号串。
请你编写程序帮助小可可求出 Kitty 猫基因的 ABC 编码以协助教授开展科研工作。
输入输出格式
输入格式:
文件中以一行的形式存放了一个 Kitty 猫基因的 01 串表达式。
输出格式:
以一行的形式输出这个 Kitty 猫基因的 ABC 编码。
输入输出样例
输入样例#1: 复制
00
输出样例#1: 复制
A
输入样例#2: 复制
01001011
输出样例#2: 复制
CCCABACCBAB
说明
给出的01字符串长度
Len≤256Len\leq 256
Len≤256
#include <stdio.h>#include <iostream>using namespace std;int s[2000010]={0};void Find(int l,int r){if(s[r]-s[l-1]==0) //可以手模一下{cout << "A";return;}if(s[r]-s[l-1]==r-l+1) //可以手模一下{cout << "B";return;}cout << "C";int mid=(l+r)/2;Find(l,mid);Find(mid+1,r);}int main(){int num=0;while(1){char t=getchar();if(t!='1'&&t!='0'){break;}s[++num]=s[num-1]+t-'0';}Find(1,num);return 0;}
这篇关于P2562 [AHOI2002]Kitty猫基因编码(洛谷)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!