原文链接：http://www.mydrs.org/program/list.asp?id=355
题意简述输入一个长为
（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
输出Belse
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
作者：
来源：ChinaSchool
时间：2002-05-03
上一篇：SGOI11之《数的朗读》
下一篇：SGOI11之《黑白图像压缩》