$$\mathrm{Kitty貓基因編碼}$$

題目鏈接：$\mathrm{l}\mathrm{u}\mathrm{o}\mathrm{g}\mathrm{u}?\mathrm{P}2562$

題目

小可可選修了基礎生物基因學。教授告訴大家 Super Samuel 星球上 Kitty 貓的基因的長度都是 $2$ 的正整數(shù)次冪 )， 全是由兩種不同的基因單元組成的。 這兩種不同的基因單元分別記成 $0$ 和 $1$ ，于是 Kitty 貓基因可以寫成一個 01 串表達式 。

為了便于分析和降低數(shù)據(jù)存儲量，教授發(fā)明了 ABC 編碼規(guī)則。該編碼規(guī)則是不斷地按照

對 Kitty 貓基因 01 串表達式 進行改寫， 直至最終被改寫成只含有字符 “A” 、“B” 、“C” 的符號串。

請你編寫程序幫助小可可求出 Kitty 貓基因的 ABC 編碼以協(xié)助教授開展科研工作。

輸入

文件中以一行的形式存放了一個 Kitty 貓基因的 01 串表達式。

輸出

以一行的形式輸出這個 Kitty 貓基因的 ABC 編碼。

樣例輸入1

00

樣例輸出1

A

樣例輸入2

01001011

樣例輸出2

CCCABACCBAB

數(shù)據(jù)范圍

給出的 01 字符串長度 $Len\le 256$

思路

這道題其實和我之前做過的 FBI樹 很像，只有幾點不同：

FBI 樹中就算是全 $0$ 或者全 $1$ 串，都要繼續(xù)遞歸，但是這個不用

FBI 樹后序遍歷，這個是先序遍歷

FBI 樹給出了 $n$ ，而這個沒有

代碼

#include<cstdio> #include<cstring>using namespace std;char a[1051];void work(int l, int r) {int check = a[l] - '0';for (int i = l + 1; i <= r; i++)if ((a[i] - '0') != check) {check = -1;break;}if (check == -1) {printf("C");if (l < r) {int mid = (l + r) >> 1;work(l, mid);work(mid + 1, r);}}else if (check == 0) printf("A");else printf("B"); }int main() {scanf("%s", &a);work(0, strlen(a) - 1);return 0; }

總結

以上是生活随笔為你收集整理的Kitty猫基因编码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。