SGOI11之《Kitty猫基因编码》解题报告
　　　　　　　　

题意简述

　　输入一个长为（k≤8）01串s，按照"ABC编码规则"进行编码，ABC编码规则是：
　　

例如：
　　

算法分析

　　本题着重考察了选手递归知识的掌握及编程基本功，因此只要明确了递归过程的作用，算法就比较简单了：设work(s:string)是将01串s改写成ABC编码，则可以这样设计算法：
　　

　　改进算法：这种算法的时间复杂度是O(Nlog2N)级别的，然而我们很容易想到使用"部分和"的方法将算法时间复杂度降为O(N)级--算法1的"瓶颈"主要在使用了一重循环判断某一个串是否全是0或者1，如果使用了部分和，这一步将成为O(1)级。另外，由于下面是改进算法：
　　
　　然后，我们可以通过算法3的预处理求出函数subsum：
　　

　　至此，我们已经很完美的解决了这一问题了，但是在实现的时候有一个细节需要注意：由于题目中s串的长度≤=256，比Turbo Pascal提供的string的最大长度大，因此，我们必须采用数组存贮s串。

程序

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+}
{$M 65520,0,655360}
Const
　　InFile = 'AH02T2.in'; 　　　　　　　//输入文件
　　OutFile = 'AH02T2.out';　　　　　　//输出文件
　　Limit = 512;　　　　　　　　　　　　//s串的最大长度（放大了一倍）

Type
　　Tdata = record
　　　　　　　　　　len : integer;
　　　　　　　　　　data : array[1..Limit] of integer;
　　　　　end; 　　　　　　　　　　　　　　　　　　//s串类型的定义
　　Tsubsum = array[0..Limit] of integer;　　　　//函数subsum类型的定义

Var
　　data : Tdata;
　　subsum : Tsubsum;

procedure init; 　　　　　　　　　　　　　　　　　//读入过程
var
　　c : char;
begin
　　fillchar(data , sizeof(data) , 0);　　　　　　//初始化：s串归0
　　assign(INPUT , InFile); ReSet(INPUT);　　　　//打开输入文件
　　　while not eoln do
　　　　begin
　　　　　　read(c);
　　　　　　inc(data.len);
　　　　　　data.data[data.len] := ord(c) - ord('0'); 　//将字符转化为数字
　　　　end; //of while
　　Close(INPUT);　　　　　　　　　　　　　　　　//关闭输入文件
end; //of init

procedure Get_Subsum; 　　　　　　　　　　　　　//预处理--求出函数subsum
var
　　i : integer;
begin
　　fillchar(subsum , sizeof(subsum) , 0);　　//初始化：subsum归0
　　subsum[0] := 0; 　　　　　　　　　　　　　　//初始化边界条件
　　for i := 1 to data.len do
　　　subsum[i] := subsum[i - 1] + data.data[i]; //递推求出subsum[i]
end; //of Get_Subsum

procedure work(start , stop : integer);
//将01串sstart…sstop改写成ABC编码并输出
var
　　tmp : integer;
begin
　　tmp := subsum[stop] - subsum[start - 1]; 　　　//求出sstart…sstop的和
　　if (tmp = 0) or (tmp = stop - start + 1) then　//如果s串全部一样
　　　if data.data[start] = 0 then 　　　　　　　　　//如果s串全是0
　　　　write('A') 　　　　　　　　　　　　　　　　　　//输出A
　　　else
　　　　　　　write('B') 　　　　　　　　　　　//如果s串全是1输出B
　　else
　　　begin
　　　　　write('C'); 　　　　　　　　　　　　　　//按照题目的要求输出C
　　　　　work(start , (start + stop) div 2); 　//递归输出s1串的ABC编码
　　　　　work((start + stop) div 2 + 1 , stop); //递归输出s2串的ABC编码
　　　end; 　　　　　　　　　　　　　　　　　　　　//of else
end;　　　　　　　　　　　　　　　　　　　　　　　//of work

Begin
　　init;
　　Get_Subsum;
　　assign(OUTPUT , OutFile); ReWrite(OUTPUT); 　　//打开输出文件
　　　work(1 , data.len);
　　　writeln;
　　Close(OUTPUT); 　　　　　　　　　　　　　　　　　//关闭输出文件
End.　　　　　　　　　　　　　　　　　　　　　　　　　//of main