4.5 相关题库_数据结构编程实验（第3版）-QQ阅读男生轻小说网

书名：数据结构编程实验（第3版）
作者名：吴永辉王建德编著
本章字数：13468字
更新时间：2021-08-13 17:24:07

4.5　相关题库

【4.5.1　时间日期格式转换】

世界各地有多种格式来表示日期和时间。对于日期的表示，在我国常采用的格式是“年年年年/月月/日日”或写为英语缩略表示格式“yyyy/mm/dd”，此次编程大赛的启动日期“2009/11/07”就符合这种格式，而美国所用的日期格式则为“月月/日日/年年年年”或“mm/dd/yyyy”，如将“2009/11/07”改成这种格式，对应的则是“11/07/2009”。对于时间的格式，则常有12小时制和24小时制两种表示方法，24小时制用0～24来表示一天中的24小时，而12小时制用1～12表示小时，用am/pm来表示上午或下午，比如“17:30:00”是采用24小时制来表示时间，而对应的12小时制的表示方法是“05:30:00pm”。注意12:00:00pm表示中午12点，而12:00:00am表示晚上12点。

对于给定的采用“yyyy/mm/dd”加24小时制（用短横线“–”连接）来表示日期和时间的字符串，请编程实现将其转换成“mm/dd/yyyy”加12小时制格式的字符串。

输入

第一行为一个整数T（T≤10），代表总共需要转换的时间日期字符串的数目。接下来总共T行，每行都是一个需要转换的时间日期字符串。

输出

分行输出转换之后的结果。

试题来源：2010“顶嵌杯”全国嵌入式系统C语言编程大赛初赛

在线测试：POJ 3751

提示

时间日期的转换有两个关键点：

1）将小时hour由24小时制转换为12小时制：若hour==0，则转换为hour=12；否则hour=（hour>12?hour-12:hour）。

2）根据24小时制的hour信息，在时间后加上下午信息，即输出hour>=12?"pm":"am"。

【4.5.2　Moscow Time】

在E-mail中使用下述的日期和时间设置格式：EDATE::=Day_of_week,Day_of_month Month Year Time Time_zone。

其中EDATE是日期和时间格式的名称，“::=”定义如何给出日期和时间的格式。EDATE的有关项的描述如下。

Day-of-week表示星期几，可能的值为：MON、TUE、WED、THU、FRI、SAT和SUN。后面给出逗号字符“,”。

Day-of-month表示该月的哪一天，用两个十进制数表示。

Month表示月份的名称，可能取的值为：JAN、FEB、MAR、APR、MAY、JUN、JUL、AUG、SEP、OCT、NOV和DEC。

Year用两个或四个十进制数表示。如果年份用两个十进制数，则设定是××世纪的年份。例如，74和1974表示1974年。

Time：当地时间的格式是hours:minutes:seconds，其中hours、minutes和seconds由两个十进制数表示。时间的范围从00:00:00到23:59:59。

Time_zone：当地时间的开始从Greenwich时间计算。用“+”或“-”后面4位数。前两位表示小时，后两位表示分钟。时间的绝对值不超过24小时。时区用下述名字之一表示。

EDATE两个相邻的项用一个空格分开。星期几、月份和时区用大写给出。例如，St.Petersburg的比赛日期的10am表示为：

TUE,03 DEC 96 10:00:00+0300

请编写一个程序，将EDATE格式给出的日期和时间转换为Moscow时区的相应的日期和时间。本题不考虑所谓的“夏季时间”。程序输入的Day-of-week和Time_zone是正确的。

请注意：

1）Moscow时间比Greenwich时间差3小时（Greenwich时区+0300）。

2）January、March、May、July、August、October和December有31天；April、June、September和November有30天；February一般有28天，在闰年时则是29天。

3）如果是闰年，则要满足条件：数字能被4整除，但不能被100整除；数字能被400整除。例如1996和2000是闰年，而1900和1997则不是闰年。

输入

输入在一行中给出以EDATE格式给出的日期和时间。输入数据中最小的年份是0001，最大是9998。在输入的EDATE字符串开始和结束不包含空格。

输出

输出一行以EDATE格式表示的Moscow时区的时间。在输出的EDATE字符串中Year用两种可允许的方式之一表示。输出字符串开始和结束不能有空格。

试题来源：ACM Northeastern Europe 1996

在线测试：POJ 1446，ZOJ 1323，UVA 505

提示

首先，将以EDATE格式输入的日期和时间转换成相应的数字信息。

设week为周几的变量，week==0对应“SUN”，week==1对应“MON”，……，week==6对应“SAT”；year为年份变量，若输入的年份信息为两位，则应加上1900，使之变成四位整数；month为月份变量，month==1对应“JAN”，……，month==12对应“DEC”；day为月内几号的变量；hour、minute、second为时、分、秒。hour和minute根据所在时区调整，second无变化；zt为时区变量。zt=0对应'UT'，……，zt=5对应'PDT'。对应于Greenwich时间，第zt个时区小时的调整量为d[zt]。按照题意，d[0]=3，d[1]=3，d[2]=7，d[3]=8，d[4]=9，d[5]=10。若输入的时间属于时区zt，则调整小时hour+=d[zt]；否则属于Greenwich时间，需要输入正负号c计算小时的调整量dh和分钟的调整量dm。若c的符号为负，则hour-=dh，minute+=dm；若c的符号为正，则hour+=dh，minute-=dm。

接下来，按照60分钟小时制和每日24小时制的要求规整时间和日期。规整分钟（minute）时，可能会影响小时（hour）；而规整时间可能会影响日期（day、month、week和year）。牵一发而动全身，因此必须审慎处理：

1）处理分钟越界的情况：若minute<0，则minute+=60，--hour；若minute≥60，则minute-=60，++hour。

2）处理小时越界的情况：若hour<0，则hour+=24，week=(week-1+7)%7，--day。若day≤0，则--month。若month-1后小于1，则month=12，--year。day=day+year年month的天数；若hour≥24，则hour-=24，week=(week+1)%7，++day。若day+1后大于year年month的天数，则day=1，++month。若month+1后大于12，则month=1，++year。

此时，得出了以EDATE格式表示的Moscow时区的时间为：

week对应的星期串，day、month对应的月份串，year,hour,minute,second。

【4.5.3　Double Time】

在公元前45年，Julius Caesar采用了标准的日历：每年有365天，每4年有额外的一天，即2月29日。然而，这是不太准确的日历，并不能反映真正的阳历，而且季节也在逐年恒定地变化。在1582年，Pope GregoryⅩⅢ规范了反映这一变化的新型的日历。从此，世纪年如果能被400整除，这一世纪年才是闰年。因此，1582年进行了调整，使得日历与季节符合。这种新的日历，以及对原来日历进行校正的要求，立即被某些国家所采用，那天的第二天是1582年10月4日星期四，被改为1582年10月15日星期五。英国和美国等国家一直到1752年才改了过来，把9月2日星期三改为9月14日星期四。（俄罗斯一直到1918年才改变，而希腊一直到1923年才改变。）因此在很长的一段时间内，历史以两个不同的时间来记录。

请编写一个程序，输入日期，先确定是哪一种日期类型，然后将其转换为另一种类型的日期。

输入

输入由若干行组成，每行给出一天的日期（例如Friday 25 December 1992），日期的范围从1600年1月1日到2099年12月31日，被转换的日期可以超出这个范围。注意所有日期和月份的名字如样例所示，即第一个字母大写，其余字母小写。输入以一行给出一个字符“#”为结束。

输出

输出由若干行组成，每行与输入的一行对应。每行给出另一种类型的日期，其格式和间距如样例所示。注意在每两个数据之间输出一个空格。为了在类型之间有所区分，老的类型日期在月份的日期之后要有一个星号(*)，该星号与月份日期之间没有空格。

试题来源：New Zealand Contest 1992

在线测试：UVA 150

提示

我们将Julius Caesar日历简称为老日历，Pope Gregory XIII日历简称为新日历。设输入的日期为week（周几）、day（天）、month（月）、year（年）。按照题意，老日历中的year年能被4整除，则year年为闰年；新日历中的year年能被4整除但不能被100整除或者能被400整除，则year年为闰年。

按老日历计算[公元0000年1月1日..year年month月day-1日]的总天数为

按新日历计算[公元0000年1月1日..year年month月day-1日]的总天数为

1）若(1+d1)%7==week，则说明当前日历为老日历，应输出新日历的日期。计算方法如下：

·按照新增的闰年数调整。

·规整日期：若day大于按老日历规定的year年month月的天数，则应减去该月天数，月份month+1。若月份month大于12，则调整为month=1，年份year+1。

2）若(1+d1)%7≠week，则说明当前日历为新日历，应输出老日历的日期。计算方法如下：

·按照减少的闰年数调整。

·规整日期：若day小于1，则月份month-1。若月份month小于1，则调整month=12，年份year-1。然后计算老日历下year年month月的天数d，day=day+d。

【4.5.4　Maya Calendar】

M.A.Ya教授对古老的玛雅有了一个重大发现。从一个古老的节绳（玛雅人用于记事的工具）中，教授发现玛雅人使用一个一年有365天的Haab历法。Haab历法每年有19个月，在开始的18个月，一个月有20天，月份的名字分别是pop、no、zip、zotz、tzec、xul、yoxkin、mol、chen、yax、zac、ceh、mac、kankin、muan、pax、koyab和cumhu。这些月份中的日期用0～19表示。Haab历的最后一个月是uayet，它只有5天，用0～4表示。玛雅人认为这个日期最少的月份是不吉利的，在这个月法庭不开庭，人们不从事交易，甚至没有人打扫房屋中的地板。

玛雅人还使用了另一个历法，在这个历法中年被称为Tzolkin（holly年），一年被分成13个不同的时期，每个时期有20天，每一天用一个数字和一个单词相组合的形式来表示。使用的数字是1～13，使用的单词共有20个，它们分别是imix、ik、akbal、kan、chicchan、cimi、manik、lamat、muluk、ok、chuen、eb、ben、ix、mem、cib、caban、eznab、canac和ahau。注意，年中的每一天都有着明确且唯一的描述。比如，在一年的开始，可如下描述日期：1 imix,2 ik,3 akbal,4 kan,5 chicchan,6 cimi,7 manik,8 lamat,9 muluk,10 ok,11 chuen,12 eb,13 ben,1 ix,2 mem,3 cib,4 caban,5 eznab,6 canac,7 ahau,8 imix,9 ik,10 akbal……也就是说数字和单词各自独立循环使用。

Haab历和Tzolkin历中的年都用数字0，1，…表示，数字0表示世界的开始。所以第一天被表示成：

Haab:0.pop 0

Tzolkin:1 imix 0

请帮助M.A.Ya教授写一个程序把Haab历转化成Tzolkin历。

输入

Haab历中的数据由如下方式表示：

日期.月份年数

输入中的第一行表示要转化的Haab历日期的数据量。下面的每一行表示一个日期，年数小于5000。

输出

Tzolkin历中的数据由如下方式表示：

天数字天名称年数

第一行表示输出的日期数量。下面的每一行表示一个输入数据中对应的Tzolkin历中的日期。

试题来源：ACM Central Europe 1995

在线测试：POJ 1008，UVA 300

提示

设Haab历的日期为year年month月date天，则这一日期从世界开始计起的天数day=365×year+(month-1)×20+date+1。

对于第day天来说，Tzolkin历的日期为year年的第num个时期内的第word天。由于Tzolkin历每年有260天（13个时期，每时期20天），因此若day%260=0，则表明该天是Tzolkin历中某年最后一天，即year=day/260-1；num=13，word=20天；若day%260≠0，则year=day/260；num=(day%13==0?13:day%13)，word=(day-1)%20+1。

【4.5.5　Time Zones】

直到19世纪，时间校准还是一个纯粹的地方现象。当太阳升到最高点的时候，每一个村庄把时钟调到中午12点。一个钟表制造商人家的时间或者村里主表的时间被认为是官方时间，市民们把自家的钟表和这个时间对齐。每周一些热心的市民会带着时间标准的表，游走在大街小巷为其他市民对表。在城市之间旅游的话，在到达新地方的时候需要把怀表校准。但是，当铁路投入使用之后，越来越多的人频繁地长距离地往来，时间变得越来越重要。在铁路运营的早期，时刻表非常让人迷惑，每一个所谓的停靠时间都基于停靠地点的当地时间。时间的标准化对于铁路的高效运营变得非常重要。

在1878年，加拿大人Sir Sanford Fleming提议使用一个全球的时区（这个建议被采纳，并衍生了今天使用的全球时区的概念），他建议把世界分成24个时区，每一个跨越15°经线（因为地球的经度为360°，被划分成24块后，一块为15°）。Sir Sanford Fleming的方法解决了全球性时间混乱的问题。

美国铁路公司于1883年11月18日使用了Fleming提议的时间方式。1884年一个国际子午线会议在华盛顿召开，其目的是选择一个合适的本初子午线。大会最终选定了格林威治为标准的0°。尽管时区被确定了下来，但是各个国家并没有立刻更改它们的时间规范，在美国，尽管到1895年已经有很多州开始使用标准时区时间，国会直到1918年才强制使用会议制定的时间规范。

今天，各个国家使用的是Fleming时区规范的一个变种，我国一共跨越了5个时区，但是使用了一个统一的时间规范，比Coordinated Universal Time（UTC，格林威治时间）早8个小时。俄罗斯也采用这个时区规范，尽管整个国家使用的时间和标准时区提前了1个小时。澳大利亚使用3个时区，其中主时区提前于按Fleming规范的时区半小时。很多中东国家也使用了半时时区（即不是按照Fleming的24个整数时区）。

因为时区是对经度进行划分，在南极或者北极工作的科学家直接使用了UTC时间，否则南极大陆将被分解成24个时区。

时区的转化表如下所示。

UTC　Coordinated Universal Time

GMT　Greenwich Mean Time,定义为UTC

BST　British Summer Time,定义为UTC+1 hour

IST　Irish Summer Time,定义为UTC+1 hour

WET　Western Europe Time,定义为UTC

WEST　Western Europe Summer Time,定义为UTC+1 hour

CET　Central Europe Time,定义为UTC+1

CEST　Central Europe Summer Time,定义为UTC+2

EET　Eastern Europe Time,定义为UTC+2

EEST　Eastern Europe Summer Time,定义为UTC+3

MSK　Moscow Time,定义为UTC+3

MSD　Moscow Summer Time,定义为UTC+4

AST　Atlantic Standard Time,定义为UTC-4 hours

ADT　Atlantic Daylight Time,定义为UTC-3 hours

NST　Newfoundland Standard Time,定义为UTC-3.5 hours

NDT　Newfoundland Daylight Time,定义为UTC-2.5 hours

EST　Eastern Standard Time,定义为UTC-5 hours

EDT　Eastern Daylight Saving Time,定义为UTC-4 hours

CST　Central Standard Time,定义为UTC-6 hours

CDT　Central Daylight Saving Time,定义为UTC-5 hours

MST　Mountain Standard Time,定义为UTC-7 hours

MDT　Mountain Daylight Saving Time,定义为UTC-6 hours

PST　Pacific Standard Time,定义为UTC-8 hours

PDT　Pacific Daylight Saving Time,定义为UTC-7 hours

HST　Hawaiian Standard Time,定义为UTC-10 hours

AKST　Alaska Standard Time,定义为UTC-9 hours

AKDT　Alaska Standard Daylight Saving Time,定义为UTC-8 hours

AEST　Australian Eastern Standard Time,定义为UTC+10 hours

AEDT　Australian Eastern Daylight Time,定义为UTC+11 hours

ACST　Australian Central Standard Time,定义为UTC+9.5 hours

ACDT　Australian Central Daylight Time,定义为UTC+10.5 hours

AWST　Australian Western Standard Time,定义为UTC+8 hours

下面给出了一些时间，请在不同时区之间进行转化。

输入

输入的第一行包含了一个整数N，表示有N个测试用例。接下来N行，每一行给出一个时间和两个时区的缩写，它们之间用空格隔开。时间由标准的a.m./p.m给出。midnight表示晚上12点（12:00 a.m.），noon表示中午12点（12:00 p.m.）。

输出

假设输入行给出的时间是在第一个时区中的标准时间，要求输出这个时间在第二个时区中的标准时间。

试题来源：Waterloo 2002.09.28

在线测试：POJ 2351，ZOJ 1916，UVA 10371

提示

（1）建立时区转化常量表

由于试题直接给出了24个时区转化表，因此我们事先建立一个字符常量表x[]，表中连续2个元素为一组，对应一个时区，其中第k组中x[2×k]为第k个时区的缩写，x[2×k+1]为该时区时间相对格林威治时间的提前量，简称时间增量（0≤k≤32）

char*x[]={"WET","0","UTC","0","GMT","0","BST","+1","IST","+1","WEST","+1","CET","+1","CEST","+2","EET","+2","EEST","+3","MSK","+3","MSD","+4","AST","-4","ADT","-3","NST","-3.5","NDT","-2.5","EST","-5","EDT","-4","CST","-6","CDT","-5","MST","-7","MDT","-6","PST","-8","PDT","-7","HST","-10","AKST","-9","AKDT","-8","AEST","+10","AEDT","+11","ACST","+9.5","ACDT","+10.5","AWST","+8","",""};

（2）将时区标准的a.m./p.m.时间统一转化为以分为单位的时间

设a.m./p.m.时间中的小时为h，分钟为m；以分为单位的时间为time。显然：

·中午12点（"noon"）：time=12×60。

·晚上12点（"midnight"）：time=0。

其他时间：

·上午（"a.m."）：time=(h%12)×60+m。

·下午（"p.m."）：time=(h%12)×60+12×60+m。

（3）计算第一个时区的时间在第二个时区中的对应时间time'

按上述方法分别将两个时区的a.m./p.m.时间转换为以分为单位的时间。设第一个时区的时间为time。我们按照下述方法计算time在第二个时区中的对应时间time'：

1）寻找第一个时区的时间增量x[k1+1]。计算方法：输入第一个时区的缩写s1后在x[]中寻找对应的时区序号k1，即x[k1]=s1，则对应时区的时间增量为x[k1+1]。

2）寻找第二个时区的时间增量x[k2+1]。计算方法：输入第二个时区的缩写s2后在x[]中寻找对应的时区序号k2，即x[k2]=s2，则对应时区的时间增量为x[k2+1]。

3）time'=time+x[k2+1]×60-x[k1+1]×60。

（4）将time'转化为标准的a.m./p.m.时间

计算t=(time'+24×60)%(24×60)。直接根据模的结果计算和输出解：

·晚上12点：t==0。

·中午12点：t==12×60。

·上午"a.m."：t≤12×60。

·下午"p.m."：t>60×12。

·小时h：。若h为0，则调整h=12；m=t%60。

【4.5.6　Polynomial Remains】

给出多项式a(x)=a_nxⁿ+…+a₁x+a₀，计算a(x)被x^k+1整除后的余数r(x)。如图4.5-1所示。

图　4.5-1

输入

输入由多个测试用例组成，每个测试用例的第一行是两个整数n和k(0≤n,k≤10 000)。下一行n+1个整数给出a(x)的系数，以a₀开始，以a_n结束。输入以n=k=-1结束。

输出

对于每个测试用例，在一行中输出余数的系数。从常量系数r0开始。如果余数是0，则输出这一常量系数0；否则，对一个d次的余数输出d+1个系数，每个系数用空格分开。

假设余数的系数可以用32位整数表示。

试题来源：Alberta Collegiate Programming Contest 2003.10.18

在线测试：POJ 2527

提示

设存储余数多项式的数组为a，数组的长度为n+1，多项式中各项的系数存储在a[0..n]中。

初始时，存储被除数多项式a(x)：for(i=0;i<=n;i++)scanf("%d", & a[i]);。

a(x)重复地被x^k+1除的算法如下。初始时i=n。如果i≥k，则a(x)被x^k+1重复除直到i<k：

for (i=n; i>=k; i--) 
    if (a[i]!=0) 
        { a[i-k] += (-a[i]); a[i] = 0; }

然后数组a的长度被调整：while(n>=0 & & !a[n])n--;。

最后，a[0..n-1]为余数多项式中各项的系数，并被输出：for(i=0;i<n;i++)printf("%d",a[i]);。

【4.5.7　Factoring a Polynomial】

Georgie最近在学习多项式，一元多项式的形式是a_nxⁿ+a_n-1x^n-1+…+a₁x+a₀，其中x是形式变量，a_i是多项式的系数，使a_i!=0的最大的i称为多项式的度。如果对所有的i，a_i都为0，则该多项式的度数是-∞。如果多项式的度数是0或者-∞，称该多项式是平凡的，否则称该多项式是非平凡的。

在Georgie学多项式时，让他印象深刻的是，对于整数多项式，可以应用不同的算法和技巧。例如，给出两个多项式，这两个多项式可以相加、相乘和相除。

在Georgie看来，多项式最有趣的特性就是它像整数一样，可以被因式分解。如果多项式不能被表示成两个或多个非平凡的实系数多项式的乘积，我们称这样的多项式是不可化简的；否则，该多项式称为可化简的。例如，多项式x²-2x+1是可化简的，因为它可以表示为(x-1)(x-1)，而x²+1则是不可化简的。众所周知，一个多项式可以表示为一个或多个不可化简的多项式的乘积。

给出一个整系数多项式，Georgie希望知道该多项式是否是不可化简的。当然他也希望知道其因子，但这样的问题现在对他来说似乎太难，因此他只要知道多项式是否可化简即可。

输入

输入的第一行给出n，表示多项式的度(0≤n≤20)；后面一行给出n+1个整数a_n,a_n-1,…,a₁,a₀，表示多项式系数（-1000≤a_i≤1000,a_n!=0）。

输出

如果输入给出的多项式是不可化简的，则输出“YES”，否则输出“NO”。

试题来源：ACM Northeastern Europe 2003,Northern Subregion

在线测试：POJ 2126

提示

若多项式的度n<2，则无法化简；若多项式的度n>2，则可以证明，多项式一定可以分解因式；若多项式的度n=2，则根据韦达定理判断ax²+bx+c是否可以分解因式：若b²-4ac≥0，则可以分解因式，否则无法分解因式。

【4.5.8　What’s Cryptanalysis?】

密码分析是破解被其他人加密过的文本的过程，有时要对一个（加密）文本的段落进行某种统计分析。请编写一个程序，对一个给定的文本进行简单分析。

输入

输入的第一行给出一个十进制正整数n，表示后面要输入的行数。后面的n行每行包含0个或多个字符（可以有空格），这是要被分析的文本。

输出

每个输出行包含一个大写字母，后跟一个空格，然后是一个十进制正整数，这个整数表示相应的字母在输入文本中出现的次数。在输入中大写字母和小写字母被认为是相同的。其他字符不必被计算。输出排序必须按计数的递减顺序，即出现次数最多的字母在输出的第一行，输出的最后一行则是出现次数最少的字母。如果两个字母出现次数相等，那么在字母表中先出现的字母在输出中先出现。如果某个字母没有出现在文本中，则该字母不能出现在输出中。

试题来源：University of Valladolid September'2000 Contest

在线测试：UVA 10008

提示

在字母集中，“A”（“a”）的序号值设为0，“B”（“b”）的序号值设为1，……，“Z”（“z”）的序号值设为25。对于字母c，无论大小写，其序号值应为tolower(c)-'a'。设cnt[i]为序号值为i的字母的频率（0≤i≤25）。

我们反复输入字符c，统计出其中各字母的频率cnt，直至输入“EOF”为止。

然后反复搜索cnt表：每次找出频率最高的字母序号k，并输出对应的字母（其ASCII码为k+'A'）及其频率cnt[k]，并将cnt[k]设为0，避免重复搜索。重复这个过程直至cnt表全0为止。

【4.5.9　Run Length Encoding】

请编写一个程序，按下述规则对一个字符串进行编码。

在字符串中，2～9个相同的字符组成的子串用两个字符来编码表示：第一个字符是这一字符串的长度，为2～9；第二个字符是相同字符的值。如果一个字符串中存在一个相同字符多于9个的子串，就先对前9个字符进行编码，然后对其余相同字符组成的子串采用相同方法进行编码。

在字符串中，如果存在某个子串，其中没有一个字符连续重复出现，就表示为以字符1开始，后面跟着这一子串，再以字符1结束。如果在字符串中存在只有1个字符“1”出现的子串，则以两个字符“1”作为输出。

输入

输入是由字母（大写和小写）、数字、空格和标点符号组成的字符串。每行由换行符结束。输入中没有其他字符。

输出

输出中的每一行被单独编码。标志每行结束的换行符不会被编码，直接输出。

试题来源：Ulm Local Contest 2004

在线测试：POJ 1782，ZOJ 2240

提示

本题也是一道模拟题，要求实现在题目描述中给出的规则。

输入被逐行处理。每次循环处理一行，从当前位置，根据题目给出的规则进行编码。

【4.5.10　Zipper】

给出3个字符串，确定第3个字符串是否由前两个字符串中的字符组成。在第3个字符串中，前两个字符串可以被任意地混合，但是每个字符还是以原来的次序排列。例如，字符串“tcraete”由“cat”和“tree”组成。

字符串A：cat

字符串B：tree

字符串C：tcraete

如你所见，第3个字符串由通过交错地采用前两个字符串中的字符构成。如第2个例子，“catrtee”由“cat”和“tree”组成。

字符串A：cat

字符串B：tree

字符串C：catrtee

不可能由“cat”和“tree”组成“cttaree”。

输入

输入的第1行是一个1～1000的正整数，表示后面给出的测试用例的数目。对每个测试用例的处理是相同的，在后面的行中给出测试用例，一个测试用例一行。

对每个测试用例，输入行有3个字符串，用1个空格将它们分开。第3个字符串的长度是前两个字符串长度之和。前两个字符串的长度在1～200之间。

输出

对于每个测试用例，如果第3个字符串由前两个字符串构成，则输出：

Data set n:yes

如果没有，则输出：

Data set n:no

n表示测试用例的编号，参见样例输出。

试题来源：ACM Pacific Northwest 2004

在线测试：POJ 2192，ZOJ 2401，UVA 3195

提示

设A=a₀a₁…a_n-1，其中前缀串A_i=a₀a₁…a_i（0≤i≤n-1）；B=b₀b₁…b_m-1，其中前缀串B_j=b₀b₁…b_j（0≤j≤m-1）；C=c₀c₁…c_n+m-1其中前缀串C_K=c₀c₁…c_k（0≤k≤n+m-1）；can[i][j]为A_i-1（A中长度为i的前缀串）和B_j-1（B中长度为j的前缀串）成功组成C_i+j-1（C中长度为i+j的前缀串）的标志。显然，can[0][0]=true。

1）当i≥1且c_i+j-1=a_i-1时，需要看A_i-2和B_j-1能否成功组成C_i+j-2，即can[i][j]=can[i][j]||can[i-1][j]，（0≤i≤n,0≤j≤m）；

2）当j≥1且c_i+j-1=b_j-1时，需要看A_i-1和B_j-2能否成功组成C_i+j-2，即can[i][j]=can[i][j]||can[i][j-1]，（0≤i≤n，0≤j≤m）。

显然，最后得出的can[n][m]便是A和B能否组成C的标志。

【4.5.11　Anagram Groups】

A.N.Agram教授当前研究如何对大量的变形词组进行处理，他为英语文本中字符的分布理论找到了一个新的应用。给出一段文本，请找到最大的变形词组。

一段文本是一个单词的序列。单词w是单词v的一个变形词，当且仅当存在某个字符位置的交换p，将w变成v，则w和v在同一变形词组中。变形词组的大小是在一个词组中单词的数量。请找出5个最大的变形词组。

输入

输入的单词由小写字母字符组成，单词由空格或换行符分开，输入由EOF终止。本题设定不超过30 000个单词。

输出

输出5个最大的变形词组。如果小于5个词组，则输出所有的变形词组。词组按大小的递减排序。相同大小按字典顺序。对每个词组，输出其大小和组内的单词。将组内单词按字典次序排列，相同的单词仅输出一次。

试题来源：Ulm Local 2000

在线测试：POJ 2408，ZOJ 1960

提示

由变形词组成的词组可以被视为等价关系的类。

在每个单词输入的时候，如果该单词所在类已经存在，我们找到单词所在类的代表元，并将这个单词加入该类；否则，创建一个类，这个单词作为该类的代表元。然后，根据类的大小，以及类中按字典次序排列最小的单词，对产生的类进行排序。最后，根据题目要求输出结果。

【4.5.12　Inglish-Number Translator】

在本题中，给出英语中的一个或多个整数，请将这些数字翻译成它们的整数表示。这些数字的范围为-999 999 999～+999 999 999。下面给出程序要使用的完整的英语单词列表：

negative,zero,one,two,three,four,five,six,seven,eight,nine,ten,eleven,twelve,thirteen,fourteen,fifteen,sixteen,seventeen,eighteen,nineteen,twenty,thirty,forty,fifty,sixty,seventy,eighty,ninety,hundred,thousand,million。

输入

输入由若干测试用例组成。

负数在单词前加“negative”。

在能使用“thousand”时，不使用“hundred”。例如，1500写作“one thousand five hundred”，而不是“fifteen hundred”。

输入以空行结束。

输出

一行输出一个答案。

试题来源：CTU Open 2004

在线测试：UVA 486，POJ 2121，ZOJ 2311

提示

设单词常量表Word顺序存储（0、1、2、…、20、30、40、50、60、70、80、90、百、千、百万、负）的32个单词。Word[0]…Word[20]中的数串与下标一一对应，即Word[i]代表正整数i（0≤i≤20）；在Word[21]…Word[27]中，Word[i]代表正整数(i-18)×10（21≤i≤27）；Word[28]…Word[30]中的数串分别代表100、1000、1000 000；s为当前单词；Num为当前测试用例代表的整数；负数标志为isNeg。

我们按照下述方法输入和处理当前测试用例。

反复输入单词s，直至s为空行为止。每输入1个单词s，则：

1）负数标志isNeg被初始化为false。若s为Word[31]，则设负数标志isNeg=true，读下一个单词s。

2）计算数值部分：

3）若isNeg为true，则num取负；输出num。

【4.5.13　Message Decowding】

奶牛们很高兴，因为它们学会了对信息的加密。它们认为它们能够使用加密的信息与其他农场的奶牛举行会议。

奶牛们的智力是众所周知的。它们的加密方法不是采用DES或BlowFish或任何其他好的加密方法。它们使用的是简单的替代密码。

奶牛有一个解密密钥和加密的消息。用解密密钥对加密的消息进行解码。解密密钥形式如下：

yrwhsoujgcxqbativndfezmlpk

这表示在加密消息中“a”实际表示“y”，“b”实际表示“r”，“c”实际表示“w”，依次类推。空格不被加密，字符所在的位置不变。

输入字母是大写或小写，解密都使用相同的解密密钥，当然相应地转化为对应的大写或小写。

输入

第1行：用于表示解密密钥的26个小写字母。

第2行：要被解码的多达80个字符的消息。

输出

一行已经被解码的消息。长度与输入第2行的长度相同。

试题来源：USACO 2003 March Orange

在线测试：POJ 2141

提示

设解密密钥为key。在加密消息中“a”实际表示为key[0]，……，“z”实际表示为key[25]。

我们反复输入字符c，直至c为结束标志“EOF”为止。每输入一个字符c，按照下述方法进行加密：

1）若c是非字母，则直接输出c；

2）若c是字母，则分析：

·若c是小写字母，则输出key[c-'a']；

·若c是大写字母，则输出key[c-'A']-'a'+'A'（因为各字符的密钥是小写字母，需转化为大写形式）。

【4.5.14　Common Permutation】

给出两个由小写字母组成的字符串a和b，输出小写字母组成的最长的字符串x，使得存在x的一个排列是a的子序列且存在x的一个排列是b的子序列。

输入

输入由若干行组成。连续的两行组成一个测试用例。也就是说，输入中的第1行和第2行是一个测试用例，第3行和第4行是一个测试用例，依次类推。每个测试用例的第一行给出字符串a，第二行给出字符串b。一个字符串一行，每个字符串至多由1000个小写字母组成。

输出

对于每个输入集合，输出一行给出x，如果存在若干个满足上述标准的x，则按字母排序选择第一个。

试题来源：World Finals Warm-up Contest,Problem Source:University of Alberta Local Contest

在线测试：UVA 10252

提示

由于x是字符串a和字符串b的公共子串，因此x中每个字母出现的次数不能超过a和b的任一字符串中该字母的频率，即x中字母c的出现次数应为min{a中字母c的频率，b中字母c的频率}。设a[i]是字符串a中序号值为i的字母频率；b[i]是字符串b中序号值为i的字母频率（“a”的序号值设为0，“b”的序号值设为1，……，“z”的序号值设为25，因此字母序号范围为0≤i≤25）。

我们在输入两个字符串的同时，分别计算出字母频率数组a和b。然后枚举每个字母序号i（0≤i≤25），该序号对应字母（其ASCII码为i+'a'）在公共字符串x中连续出现min{a[i],b[i]}次。

【4.5.15　Human Gene Functions】

众所周知，人的基因可以被视为一个序列，由4种核苷酸组成，用4个字母来标识，即A、C、G和T。生物学家对于识别人的基因以及确定基因的功能很感兴趣，因为这可以用于诊断疾病和设计新药。

一个人的基因可以通过一系列耗时的生物学实验来识别，经常需要计算机程序的帮助。一旦得到一个基因序列，接下来的工作就是确定其功能。

要确定一条刚被识别的新的基因序列的功能，生物学家使用的方法之一是用这条新的基因对数据库进行查询。被检索的数据库存储着许多基因序列及其功能。许多研究人员已经向数据库提交了他们研究的基因及其功能，可以通过互联网对该数据库进行自由的查询。

对数据库的检索结果是从数据库返回一个基因序列列表，这些基因与查询的基因相似。

生物学家认为序列的相似性往往意味着功能的相似性。因此，新基因的功能可能是列表中的基因所具有的功能之一。为了准确判断哪一个功能是新基因的功能，就需要另外进行一系列的生物学实验。

你的任务是编写一个程序，比较两个基因，并确定它们的相似性。如果你的程序有效，这个程序就将被用于数据库检索。

给出两种基因AGTGATG和GTTAG，它们的相似性如何呢？衡量两个基因相似的方法之一被称为对齐。在对齐中，如果需要，空格被插入到基因的合适的位置上，使得两个基因长度相等，并且根据评分矩阵对产生的基因进行评分。

例如，将一个空格插入AGTGATG中，产生AGTGAT-G，插入三个空格到GTTAG将产生-GT--TAG，空格用减号(-)来标识。这两个基因目前长度相等。两个字符串对齐如下：

在这一对齐中，有4个匹配，即在第2个位置的G、在第3个位置的T、在第6个位置的T，以及在第8个位置的G。每对对齐的字符按照图4.5-2的评分矩阵给出分数。

图　4.5-2

空格对空格的匹配是不允许的，上面对齐的得分是(-3)+5+5+(-2)+(-3)+5+(-3)+5=9。

当然，也存在许多其他的对齐。一个对齐如下所示（不同数量的空格被插入到不同的位置）：

这个对齐的分数是(-3)+5+5+(-2)+5+(-1)+5=14。因此，这个对齐比前一个好。事实上这一对齐是最佳的，因为没有其他的对齐可以获得更高的分数。因此可以说这两个基因的相似度是14。

输入

输入由T个测试用例组成，测试用例数（T）在输入的第一行给出。每个测试用例由两行组成：每行先给出一个整数，表示基因的长度，后面跟着基因序列。每个基因序列的长度至少为1，不超过100。

输出

输出给出每个测试用例的相似度，每个相似度一行。

试题来源：ACM Taejon 2001

在线测试：POJ 1080，ZOJ 1027,UVA 2324

提示

我们将空格和4种核苷酸的字母标识[“A”，“C”，“G”，“T”]标记为整数[0(空格)，1(A)，2(C)，3(G)，4(T)]，分别将基因序列a和基因序列b转化为整数序列s1和s2。为了便于计算任何一个基因序列的尾字符与空格配对的可能情况，分别在s1和s2的尾部加1个0（代表空格），得出s1的长度len1+1和s2的长度len2+1。

设评分矩阵为score[][]。按照题意：

f[i,j]为基因序列a中长度为i的前缀与基因序列b中长度为j的前缀对齐的最大得分。显然对齐时i和j不能全为0。

·当i>0时，a_i-1与空格对齐的最大得分为f[i-1][j]+score[0][s1[i-1]]；

·当j>0时，b_j-1与空格对齐的最大得分为f[i][j-1]+score[0][s2[j-1]]；

·当i和j都大于0时，a_i-1与b_j-1对齐的最大得分为f[i-1][j-1]+score[s1[i-1]][s2[j-1]]。

由此得出：f[i][j]=max{f[i-1][j]+score[0][s1[i-1]]，f[i][j-1]+score[0][s2[j-1]]，f[i-1][j-1]+score[s1[i-1]][s2[j-1]]}；0≤i≤len1+1，0≤j≤len2+1。

显然，两个基因序列的尾字符（a_len1-1与b_len2-1）匹配时的最大得分为f[len1][len2]。但这并代表最终答案，因为其中任何一个基因序列的尾字符有可能与空格匹配：

·a_len1-1与空格匹配时的最大得分为f[len1][len2+1]；

·空格与b_len2-1匹配时的最大得分为f[len1+1][len2]。

由此得出，基因序列a和b对齐的相似程度应为：max{f[len1][len2]，f[len1][len2+1]，f[len1+1][len2]}。

【4.5.16　Palindrome】

回文词（Palindrome）是一种对称的字符串，即一个字符串从左向右读和从右向左读是等同的。任意给出一个字符串，通过插入若干个字符，都可以变成回文词。本题的任务是，求出将给定字符串变成回文词所需要插入的最少的字符数。

比如，“Ab3bd”插入2个字符后可以变成回文词“dAb3bAd”或“Adb3bdA”，但是插入少于2个的字符无法变成回文词。

输入

程序从标准输入读入。第一行是一个整数，输入的字符串长度为N，3≤N≤5000；第二行给出长度为N的字符串，该字符串由A～Z的大写字母、由a～z的小写字母和由0～9的数字组成，本问题区分大小写。

输出

标准输出。第一行给出一个整数，它是所要求的最小数。

试题来源：IOI 2000

在线测试：POJ 1159

提示

设C(i,j)是为了获得回文词而插入到字符串s_i…s_j中的最少字符数。所以，本题要计算C(1,n)。

下述公式成立：

【4.5.17　Power Strings】

给出两个字符串a和b，我们定义a×b为它们的毗连。例如，如果a=“abc”并且b=“def”，那么a×b=“abcdef”。如果把毗连视为乘法，非负整数的指数定义为：a^0=“”(空串)，a^(n+1)=a×(a^n)。

输入

每个测试用例是一个可打印字符组成的字符串s。s的长度至少是1，不超过1 000 000个字符。最后一个测试用例后的一行为一个句号。

输出

对每个s输出最大的n，使得对于某个字符串a，s=a^n。

试题来源：Waterloo local 2002.07.01

在线测试：POJ 2406，ZOJ 1905

提示

由s=a^n可以看出，s由子串a重复n次而成。要使n最大，则重复子串a必须最短。问题转变为如何求s的最短重复子串a。设s的长度为len。

我们先用KMP算法的思想生成s的前缀函数suffix[]。若suffix[cur]=k，则s[0..(k-1)]=s[(cur-k)..(cur-1)]，且k是s的前缀和s[0..(cur-1)]的后缀间的最长匹配子串的长度。由s[0..suffix[len]-1]=s[(len-suffix[len])..(len-1)]易知，如果(len-suffix[len])是len的约数，则s[0..(len-suffix[len]-1)]必然是s[]的最短重复子串，其长度为len-suffix[len]，重复次数。

【4.5.18　Period】

给出一个由N个字符（每个字符的ASCII码在97～126之间）组成的字符串S，对于S的每个前缀，我们希望知道该前缀是否是一个周期性的字符串，即对每个长度为i的S的前缀(2≤i≤N)，是否存在最大的一个K(K>1)（如果有一个的话），使长度为i的S的前缀可以被写为A_K，即存在某个字符串A，A连续出现K次以构成这个长度为i的S的前缀。当然，我们也要知道周期K。

输入

输入由若干个测试用例组成，每个测试用例两行。第一行给出N（2≤N≤1 000 000），表示字符串S的大小；第二行给出字符串S，输入结束为一行，给出0。

输出

对于每个测试用例，在一行内输出“Test case#”和连续的测试用例编号；对每个长度为i的前缀，有周期K>1，输出前缀长度i和周期K，用空格分开，前缀按升序。在每个测试用例后输出一个空行。

试题来源：ACM Southeastern Europe 2004

在线测试：POJ 1961，ZOJ 2177，UVA 3026

提示

我们先用KMP算法的思想生成S的前缀数组suffix[]。若suffix[cur]=K，则S[0..(K-1)]=S[(cur-K)..(cur-1)]，且K是S的前缀和S[0..(cur-1)]的后缀间的最长匹配子串的长度。然后枚举S的每个前缀S[0]…S[m-1](2≤m≤n)：由S[0..suffix[m]-1]=S[(m-suffix[m])..(m-1)]易知，若(m-suffix[m])是m的约数，则S[0..(m-suffix[m]-1)]必然是S[]的最短重复子串。

【4.5.19　Seek the Name,Seek the Fame】

小猫非常有名，许多夫妇都翻山越岭来到Byteland，要求小猫给他们刚出生的婴儿取名字。他们不仅要小猫为婴儿取名字，而且他们要求取的名字是与众不同的响亮的名字。为了摆脱这种枯燥的工作，创新的小猫设计了一个容易但又神奇的算法：

1）连接父亲的名字和母亲的名字，产生一个新的字符串S；

2）找到S的一个适当的前后缀字符串（不仅是S的前缀，而且是S的后缀）。

例如，父亲=“ala”，妈妈=“la”，则S=“ala”+“la”=“alala”。S的潜在的前后缀字符串是{“a”,“ala”,“alala”}。给出字符串S，你能帮小猫写一个程序来计算S的可能的前后缀字符串的长度吗？（他会通过给你的宝宝取名字来表示感谢。）

输入

输入包含多组测试用例，每个测试用例一行，给出一个如上所述的字符串S。

限制：输入中只有小写字母可以出现，1≤S的长度≤400 000。

输出

对于每个测试用例，在一行中以升序输出数字，给出新婴儿姓名的可能的长度。

试题来源：POJ Monthly--2006.01.22,Zeyuan Zhu

在线测试：POJ 2752

提示

首先用KMP算法的思想生成S的前缀数组suffix[]。若suffix[cur]=K，则S[0..(K-1)]=S[(cur-k)..(cur-1)]，且K是S的前缀和S[0..(cur-1)]的后缀间的最长匹配子串的长度。

由KMP算法的原理可知，通过遍历suffix[len],suffix[suffix[len]],suffix[suffix[suffix[len]]],…，可以得到所有满足同时是S[]前缀和后缀的子串长度。

【4.5.20　Excuses,Excuses!】

法官Ito遇上一个问题：被征召参加陪审团的人们以相当蹩脚的借口逃避服务。为了减少听取这些愚蠢的借口所需要的时间，法官Ito要求你写一个程序，在一个被认为是站不住脚的借口列表中搜寻一个关键字列表。被匹配的关键字与借口无关。

输入

程序的输入由多个测试用例组成。每个测试用例的第一行给出两个整数。第一个数字（1≤K≤20）给出在搜寻中要使用的关键字的数目，第二个数字（1≤E≤20）给出要被搜寻的借口的数目。第2～K+1行每行给出一个关键字，第K+2～K+1+E行每行给出一个借口。在关键字列表中的所有关键字只包含小写字母，长度为L（1≤L≤20），在输入行中从第1～L列。所有的借口都包含大写和小写字母、空格，以及下述括号中的标点符号（“.,!?），长度不超过70个字符。借口至少有1个非空格字符。

输出

对每个测试用例，从列表中输出最差的借口。最差借口是关键字出现最多的借口，如果一个关键字在一个借口中出现多于一次，每次出现被认为是一个独立的出现。一个关键字“出现”在一个借口中当且仅当它以连续的形式存在于一个字符串中，并由行开始、行结束、非字母字符或空格来给出这一关键字范围。

对每个测试用例，输出一行，在字符串“Excuse Set#”后是测试用例的编号（见样例输出）。后面的行给出最差的借口，像输入一样，一个借口一行。如果有多于一个最差借口，按任意次序输出。在一个测试用例的输出之后，再输出一个空行。

试题来源：ACM South Central USA 1996

在线测试：POJ 1598,UVA 409

提示

设关键字集合为key，其中第i个关键字的字符数组为key[i]；关键字的前缀函数集合为next，其中第i个关键字的前缀函数为next[i]；当前借口在关键字集合中出现次数为keycnt，其中在关键字i中出现次数为keycnt[i]（0≤i≤e-1）；借口集合为sentence，其中第j个借口的字符数组为sentence[j]（0≤j≤k-1）。

试题要求找出在k个关键字中出现次数最多的借口。要达到这一点，必须求出每个借口在k个关键字中出现次数。于是，问题的关键变成了怎样计算借口sentence[i]在第j个关键字key[j]中的出现次数cnt。借助第j个关键字的前缀函数next[j]，可以使计算变得十分高效。

设借口sentence[i]的字符数为n，第j个关键字key[j]的字符数为m，sentence[i]的匹配指针为cur，key[j]的匹配指针为p。

我们按照如下方法计算cnt。将比较次数cnt初始化为0，从sentence[i]和key[j]的首字符出发（p=0,cur=0），依次进行比较：

1）若sentence[i][cur]与key[j][p]为同一字母，则比较两个串的下一个字符（++cur;++p）。

2）在sentence[i][cur]与key[j][p]非同一字母的情况下，若曾有匹配字符（p≥0），则sentence[i][cur]与key[j]的第next[j][p]个字符进行比较（p=next[j][p]），否则sentence[i][cur+1]与key[j][0]进行比较（++cur;p=0）。

3）在匹配成功的情况下（p==m），若sentence[i][cur]与sentence[i][cur-p-1]都为非字母，则累计比较次数（++cnt）。继续从第r个关键字中的第next[j][p]个字符比较下去（p=next[r][p]）。

上述比较过程一直进行到cur≥n为止。此时得出的cnt即借口sentence[i]在第j个关键字key[j]中的出现次数。

有了以上基础，便可以得出主算法：

1）在读入每个关键字key[i]的同时，计算其前缀函数next[i]（0≤i≤k-1）。

2）依次读入每个借口sentence[i]（0≤i≤e-1），统计sentence[i]在k个关键字的出现次数。

3）在k个关键字中出现最多次数的借口即问题解。

【4.5.21　Product】

本问题是两个整数X和Y相乘，0≤X,Y<10²⁵⁰。

输入

输入是一个由一对对的行组成的集合。在每一对中，一行给出一个乘数。

输出

对于输入的每一对数，输出给出乘积的一行。

试题来源：Sergant Pepper’s Lonely Programmers Club.Junior Contest 2001

在线测试：UVA 10106

提示

本题是高精度乘法的程序实现。设X为被乘数的数串，长度为L1；Y为乘数的数串，长度为L2；Ans为积的高精度数组，其中Ans[0]为数组长度，上限为L1+L2，Ans[Ans[0]..1]为积的各位十进制数。

反复输入被乘数串X和乘数串Y，直至文件结束为止。若数串X为“0”或数串Y为“0”，则直接输出结果0；否则，计算X和Y的长度L1和L2；乘积Ans初始化为0，长度初始化为L1+L2，先将被乘数X与乘数Y的每位数字的乘积累加到积数组Ans的对应位上(Ans[i+j-1]+=(X[i]-'0')*(Y[j]-'0')；i=L1-1…1，j=L2-1…1)，然后按照由低位到高位的顺序对Ans进行进位处理，最后看Ans[Ans[0]+1]是否大于0，若是，则长度Ans[0]+1。

【4.5.22　Expression Evaluator】

本题是关于计算C风格的表达式的。要计算的表达式仅包含简单的整数变量和一个有限的操作符集合，且表达式中没有常量。程序中有26个变量，用小写字母a～z命名。在运算前，这些变量的初始值是a=1,b=2,…,z=26。

操作符可以是加和减(二元+和-)，其含义已知。因此，表达式“a+c-d+b”的值是2(1+3-4+2)。此外，在输入的表达式中也可以采用“++”和“--”操作符，它们是一元操作符，可以在变量前，也可以在变量后。如果“++”操作符在变量前，那么在变量值用于表达式的值的计算之前，其变量值要增加1，即“++c-b”的值是2。如果“++”操作符在变量后，那么在变量值用于表达式的值的计算之后，其变量值再增加1，因此，“c++-b”的值是1，虽然在整个表达式的值计算之后，c的值会增加，但c的值也是4。“--”操作符除了对操作数的值减1之外，其他操作规则和“++”一样。

更形式化地说，表达式的运算是按下述步骤进行的：

1）识别每个前面“++”的变量，对每个这样的变量给出一句进行增1的赋值语句，然后在表达式中这样的变量前略去“++”。

2）对变量后的“++”执行相似的操作。

3）此时，在表达式中没有“++”操作符。新产生的语句将在步骤1）给出的语句之后，并在步骤2）给出的语句之前，计算结果。

4）执行步骤1）给出的语句，然后执行步骤3）确定的语句，最后是步骤2）给出的语句。

按这样的方法，计算“++a+b++”和计算“a=a+1,result=a+b,b=b+1”结果一样。

输入

输入的第一行给出一个整数T，表示测试用例的个数。后面的T行每行给出一个作为测试用例的输入的表达式。在输入的表达式中忽略空格。本题设定在输入的表达式中没有二义性（诸如“a+++b”）存在。相似地，“++”或“--”操作符不会在同一个变量前面和后面同时出现（诸如“++a++”）。设定每个变量在一个表达式中仅出现一次。

输出

对每个测试用例，将输入中给出的表达式输出，然后给出整个表达式的值，然后将运算后每个变量的值逐行输出（按变量名排序）。仅输出在表达式中出现的变量。按照下面输出样例给出的形式输出。

试题来源：ACM Tehran 2006 Preliminary

在线测试：POJ 3337

提示

设变量a对应的序号为0，变量b对应的序号为1，……，变量z对应的序号为25；v[i]是序号为i的变量值；occur[i]是序号为i的变量在表达式中的出现标志；value是表达式的值。

初始时，所有字母均未在表达式中出现，a=1,b=2,…,z=26，（occur[i]=false,v[i]=i+1，0≤i≤25）。

由左而右分析表达式串s的每个字符：

1）若s[k]为“+”或者“-”，则分析：

·若s[k]s[k+1]是“++”或“--”，则变量s[k+2]+1(或-1)，即k+=2;v[int(s[k]-'a')]+=(s[k]=='+'?1:-1)；

·若s[k]是运算符“+”或“-”，则将运算符值记入b，准备处理s[k+1]（b=(s[k]=='+'?1:-1);++k）。

2）若s[k]为变量：

·当前项（b×v[c]）计入表达式值value（c为变量s[k]的序数值int(s[k]-'a')）；

·若变量s[k]为初始值且后置“++”或“--”，则变量值+1或-1（v[c]+=(s[k+1]=='+'?1:-1)），字符指针k后移2位（k+=2）；

·标志s[k]对应的字母已出现在表达式中（occur[c]=true）；

·字符指针k后移1位（++k）。

分析完表达式串s的所有字符后，最终得出表达式值为value，并确定表达式中每个变量的值（occur[i]=true，其变量名为char('a'+i)，值为v[i]，0≤i≤25）。

【4.5.23　Integer Inquiry】

Chip Diller是BIT的新型超级计算机的第一批用户之一。他的研究工作要求3的幂次在0～333之间，他要计算这些数字之和。

“超级计算机非常伟大，”Chip评价道，“我希望Timothy能够在这里看到这些结果。”（Chip搬进了一个新的公寓，位于Third Street上Lemon Sky公寓的第3层。）

输入

输入最多有100行文字，每行是一个单一的VeryLongInteger。每个VeryLongInteger不多于100个字符，而且只包含数字（VeryLongInteger不是负数）。

输入的结束是在单独的一行中给出一个0。

输出

你的程序要输出在输入中给出的所有VeryLongInteger的总和。

试题来源：ACM East Central North America 1996

在线测试：POJ 1503，ZOJ 1292，UVA 424

提示

由于每行数串的长度上限为100，因此采用高精度数组存储。对所有行的高精度数组进行加法运算，累加结果即为解。

【4.5.24　Super long sums】

新的程序设计语言D++的创造者看到，无论如何制订SuperLongInt类型的范围，有时候程序员还是需要在更大的数字上进行操作。1000位的范围太小。你被要求计算出最大有1 000 000位的两个整数的和。

输入

输入的第一行是一个整数N，然后是一个空行，后面是N个测试用例。每个测试用例的第一行给出一个整数M（1≤M≤1 000 000）——整数的长度（为了使长度相等，可以加前导0）。后面用列中给出数据，也就是说，后面的M行数据中每行给出两个用空格分开的一位数字。这两个给出的整数每个不会小于1，并且它们和的长度不超过M。

在两个测试用例之间有一个空行。

输出

对于每个测试用例，输出一行，该行是含M位的整数，是两个整数的和。在两个输出行之间有一个空行。

试题来源：Ural State University collegiate programming contest(25.03.2000)，Problem Author:Stanislav Vasilyev and Alexander Klepinin

在线测试：UVA 10013，Ural 1048

提示

本题也是一道高精度加法题，只是被加数、加数的输入格式和高精度数组的生成方式有所不同：用m行表示被加数和加数，每行两个数字，按照由高位到低位的顺序依次给出被加数和加数当前十进制位的数字。因此可通过for(int i=m-1;i>=0;i--)循环，将当前行的两个数字分别插入被加数和加数的第i位；然后相加，并去掉和的前导0后输出。

【4.5.25　Exponentiation】

对数值很大、精度很高的数进行高精度计算是一类十分常见的问题。比如，对国债进行计算就属于这类问题。

现在要你解决的问题是：对一个实数R（0.0<R<99.999），要求写程序精确计算R的n次方（Rⁿ），其中n是整数并且0<n≤25。

输入

输入包括多组R和n。R的值占第1～6列，n的值占第8和第9列。

输出

对于每组输入，要求输出一行，该行包含精确的R的n次方。输出需要去掉前导的0后不要的0。如果输出是整数，不要输出小数点。

试题来源：ACM East Central North America 1988

在线测试：POJ 1001，UVA 748

提示

幂运算实际上是乘法运算，问题是本题要求进行实数的次幂运算，因此需要做一些特殊的处理：

1）将底数转化为高精度数组时，需要记下小数位置dec，并删除整数部分的前导0和小数部分的后导0。

2）两个实数数组a和b相乘（a和b的长度分别为l_a和l_b，小数位置分别为k_a和k_b）时：

·进行高精度乘法c=a×b，并记下乘积小数位的位置k_a+k_b+1。

·对乘积数组c作进位处理，并计算出实际长度l_c（l_a+l_b-1或者l_a+l_b）。

·删去小数部分末尾多余的0。

【4.5.26　NUMBER BASE CONVERSION】

请编写一个程序，将一个进制的数转换为另一个进制的数。有62个不同的数字：{0～9,A～Z,a～z}。

提示

如果使用一个转换的输出作为下一个转换的输入来进行一系列的进制转换，在将它转化为一个原始的进制的时候，你就得到一个原始的数字。

输入

输入的第一行给出一个正整数，表示后面会有几行。后面的每一行给出输入的进制（进制数用十进制表示）、输出的进制（进制数用十进制表示），以及用输入的进制表示的一个数。输入的进制数和输出的进制数的范围都在2～62之间，（进制数用十进制表示）。A=10,B=11,…,Z=35；a=36,b=37,…,z=61；0～9则是其一般的含义。

输出

对于每个要求的进制转换，程序输出3行。第一行是以十进制表示的输入数据的进制，后面跟一个空格，然后是输入数据（以给出的输入数据进制表示）；第二行是输出数据的进制，后面跟一个空格，然后是以输出数据的进制表示的输入数据；第三行是一个空行。

试题来源：ACM Greater New York 2002

在线测试：POJ 1220，ZOJ 1325，UVA 2559

提示

设初始进制为ibase，以ibase进制表示的数串为s，目标进制为obase。

1）将s中的每位ibase进制的数符转化为对应的数字，存储在高精度数组a中；

2）将a由ibase进制数转化为obase进制数，办法是ibase进制的高精度数组转化为十进制数后，除obase取余：

·a的每一位除obase。每一次相除的余数乘obase后加a的下一位后再除obase，直至得到整商a₁和余数r₀。

·a₁按照上述方法除obase，得到整商a₂和余数r₁。

……

·a_i-1按照上述方法除obase，得到整商a_i和余数r_i-1。

……

直至整商a_k=0为止。由此得到a对应的obase进制数为r=r_k-1…r₀。

3）然后，将r中的每位obase进制数转化为字符表示后输出。

【4.5.27　If We Were a Child Again】

“噢！如果我能像我小学的时候一样做简单的数学题该多好！我可以毕业，而且我不会出任何错！”一个聪明的大学生这样说。

但他的老师更聪明：“Ok!我就在软件实验室里给你安排这样一些课题，你不要悲伤。”

“好的！”这位同学感到高兴，他太高兴了，以至于没有注意到老师脸上的微笑。

这位可怜的同学做的第一个项目是实现一个能执行基本算术操作的计算器。

和许多其他大学生一样，他不喜欢自己来做所有的工作。他只是想从各处收集程序。因为你是他的朋友，他请你来写程序。但你也是一个聪明人。你只答应为他写整数的整除和取余（C/C++中的%）运算。

输入

输入由一个行的序列组成。每行给出一个输入的数字，一个或多个空格，一个标志（整除或取余），再跟着一个或多个空格，然后是另一个输入的整数。两个输入的整数都是非负整数，第一个数可以任意长，第二个数的范围为n（0<n<2³¹）。

输出

对每个输入，输出一行，每行给出一个整数，见样例输出。输出不包含任何多余空格。

试题来源：May 2003 Monthly Contest

在线测试：UVA 10494

提示

由于被除数任意长，除数的上限为2³¹，因此被除数和商应采用高精度数组存储，除数的数据类型为长整型，而余数不大于除数，亦应采用长整型。设被除数的数串为x，其长度为len；除数为长整数y；商的长度为Ans[0]，商存储在Ans[1..Ans[0]]中；算符为op；余数为ret。

我们反复输入两个操作数x、y和算符op，直至读至文件结束符为止。每次读入被除数串x、除数y和算符op，就要首先计算被除数x的长度，而将余数ret和商的长度Ans[0]初始化为0。按照x[0]…x[len-1]的顺序计算当前余数ret和Ans的当前位（ret=ret*10+x[i]-'0';Ans[++Ans[0]]=ret/y;ret%=y;）。

若要求计算余数(op[0]='%')，则直接输出ret；若要求计算商(op[0]='/')，则先计算Ans首部第1个非零位Ans[j]。若Ans全零(j>Ans[0])，则输出商为0；否则输出商为Ans[j..Ans[0]]。

【4.5.28　Simple Arithmetics】

新型WAP界面的一部分是一个计算长整数表达式的计算器。为了使输出看起来更好，结果要被格式化为和手写计算一样的形式。

请完成这个计算器的核心部分。给出两个数字以及要求的操作，你来计算结果，并按下述指定的形式打印。对于加法和减法，计算结果的数字写在两个数字的下方。乘法相对有些复杂：首先，给出一个数的每一位数字与另一个数相乘的部分结果，然后再把结果加在一起。

输入

第一行输入给出一个正整数T，表示后面要给出的表达式的数目。每个表达式由一个正整数、一个运算符（+、-和*之一）和第二个正整数组成。每个数字最多500位。行中没有空格。如果运算符是减号，则第二个数字总是小于第一个数字。没有数字以0开始。

输出

对于每个表达式，在两行中输出两个给出的整数，第二个数字必须在第一个数字之下，两个数字的最后一位数字必须在同一列对齐。把运算符放在第二个数的第一位前面。在第二个数字后，由多个短横线（-）构成一条水平线。

对每个加法和减法，将运算结果输出在水平线下，运算结果的最后一位与两个操作数的最后一位对齐。

对于每一个乘法，用第二个数的每一位数字去乘第一个数。从第二个数字的最后一位开始，将乘出来的局部结果单独在一行里输出。每个乘出来的局部结果要与相应的位对齐，即每个乘出来的局部结果的最后一位必须要与上一个乘出来的局部结果的第二个数对齐。这些局部结果不能有任何多余的零。如果第二个数的某一位数字是零，则产生的局部结果只有一位数字——0。如果第二个数多于一位，还要在最后一个局部乘积下输出一条水平线，然后输出总和。

空格只能出现在每一行的前面部分，并且在满足上述要求的条件下尽可能少。

分隔线要正好覆盖它的上一行和下一行的数字或运算符。就是左端要与上一行和下一行中最左边的非空格字符对齐，右端要与上一行和下一行的最右边一个字符对齐。

在每一次运算结束后，输出一个空行，包括最后一次运算。

试题来源：ACM Central Europe 2000

在线测试：POJ 1396，ZOJ 2017，UVA 2153

提示

从表达式串中取出运算符c，并截出两个操作数串，将之转化为高精度数组a和b，长度为l_a和l_b。

1）若c==“+”，则进行高精度的加法运算，得到sum←a+b，长度为l_sum；计算行宽l=max(l_sum，l_b+1)；以l为行宽，向右靠齐，分4行输出a、“+”、b、max{l_b+1，l_sum}个“-”和sum。

2）若c==“-”，则进行高精度的减法运算，得到delta←a-b，长度为l_delta；计算行宽l=max{l_a，l_b+1}；以l为行宽，向右靠齐，分4行输出a、“-”、b、max{l_b+1,l_delta}个“-”和delta。

3）若c==“*”，则进行高精度的乘法运算，得到product←a*b，长度为l_product；然后计算中间运算过程，即p[0]=a*b[0]，p[1]=a*b[1]，…，p[l_b-1]=a*b[l_b-1]，其中p[i]的长度为l_p[i]（0≤i≤l_b-1）；调整行宽l=max{l_product，l_b+1，l_p[i]+i}（0≤i≤l_b-1）；以l为行宽，向右靠齐，先分3行输出a、“*”、b、max{l_b+1，l_p[0]}个“-”；然后分l_b行输出中间计算过程，其中第i行以l-(i-1)为行宽，向右靠齐，输出p[i]；若l_b>1，则分两行，分别以l为行宽，向右靠齐，输出max{l_b+1,l_p[0]}个“-”和积product。

【4.5.29　ab-ba】

给出自然数a和b，求a^b-b^a。

输入

输入常整数a和b（1≤a,b≤100）。

输出

输出答案。

在线测试：SGU 112

提示

由于需要高精度数组连乘，因此宜采用面向对象的程序设计方法。定义一个名为bigNumber的类，其私有（private）部分是一个长度为len的高精度数组a，被bigNumber类的对象和成员函数访问；其公共（public）界面包括：

·bigNumber()——高精度数组a初始化为0；

·int length()——返回高精度数组a的长度；

·int at(int k)——返回a[k]；

·void setnum(char s[])——将字符串s[]转换成长度为len的高精度数组a；

·isNeg()——判断高精度数组a是否为负数；

·void add(bigNumber & x)——高精度加法运算：a←a+x；

·void multi(bigNumber & x)——高精度乘法运算：a←a*x；

·int compare(bigNumber & x)——比较a与x之间的大小，返回；

·void minus(bigNumber & x)——高精度减法运算：a←a-x；

·void multi(bigNumber & x)——高精度乘法运算：a←a*x；

·void power(int k)——高精度乘幂运算：num←num^k。

有了bigNumber类的定义，主算法就变得十分清晰：

1）定义bna和bnb为bigNumber类（bigNumber bna,bnb），将a、b分别转化为数组bna和bnb（bna.setnum(a);bnb.setnum(b)）；

2）计算bna←bna^b，bnb←bnb^a（bna.power(b);bnb.power(a)），bna←bna-bnb（bna.minus(bnb)）；

3）若bna是负数（bna.isNeg()=true），则输出加负号；输出bna.at(bna.length()-1)…bna.at(0)。

【4.5.30　Fibonacci Number】

Fibonacci序列的头两个数是1，序列的计算是将前两个数相加。

f(1)=1,f(2)=1,f(n>2)=f(n-1)+f(n-2)

输入与输出

输入是每行一个数，输出该数的Fibonacci数。

注意：在测试数据中，Fibonacci数没有超过1000位，即f(20)=6765有4位。

试题来源：UVa Local Qualification Contest 2003

在线测试：UVA 10579

提示

显然，Fibonacci数的上限为1000位，须采用高精度数组存储。由于递推Fibonacci序列的过程需要反复进行高精度的加法运算，因此不妨采用面向对象的程序设计方法：定义一个类，将加法运算涉及的函数放在类的公共（public）界面，将类的对象和成员函数访问的高精度数组放在类的私有（private）部分，使主程序的结构更清晰。

【4.5.31　How many Fibs】

Fibonacci数的定义如下：

·F₁:=1；

·F₂:=2；

·F_n:=F_n-1+F_n-2（n≥3）。

给出两个整数a和b，请计算在区间[a,b]中有多少个Fibonacci数。

输入

输入包含若干个测试用例。每个测试用例由两个非负整数a和b组成，输入以a=b=0结束。其他a≤b≤10¹⁰⁰。给出的整数a和b没有多余的前导0。

输出

对于每个测试用例输出一行，输出满足a≤F_i≤b的Fibonacci数F_i的数目。

试题来源：Ulm Local 2000

在线测试：POJ 2413，ZOJ 1962

提示

由于Fibonacci序列中第500个Fibonacci数将超过题目给出的上限10¹⁰⁰，因此可采用离线计算方法，先通过高精度加法运算递推序列中前500个Fibonacci数fib[1]…fib[500]；然后反复测试数据组。每输入一对整数a和b，分别在fib[]中寻找第1个不小于a的整数fib[left]（fib[left]≥a）和第1个不大于b的整数fib[[right]（fib[[right]≤b）。显然，区间[a,b]内Fibonacci数的个数为right-left。

由于该题需要反复进行高精度加法和比较大小的运算，因此比较适宜采用面向对象的程序设计方法。

【4.5.32　Heritage】

富有的叔叔逝世了，他的遗产将由亲戚和教堂来继承（叔叔在遗嘱中坚持教堂要得到一些遗产）。在遗嘱中有N个亲戚（N≤18）被提到，他们是按照重要性递减顺序排列的（第一个人最重要）。因为你在家庭中是计算机专业人士，你的亲戚请你帮助他们。因为遗嘱中需要填写一些空格，所以他们需要你的帮助。空格的形式如下：

亲戚#1将获得全部遗产的1/---，

亲戚#2将获得全部遗产的1/---，

……

亲戚#N将获得全部遗产的1/---。

亲戚们的愿望是填空时要保持叔叔的遗愿（即分数是非递增的，并且教堂要得到遗产），留给教堂的遗产数量要最少。

输入

只有一行，给出一个整数N(1≤N≤18)。

输出

输出空格中要填写的数字，每个数字一行，使得留给教堂的遗产最少。

试题来源：Bulgarian Online Contest September 2001

在线测试：POJ 1405，Ural 1108

提示

设a[i]为第i+1个亲戚对应空格的数字，即该亲属获得全部遗产的1/a[i]（0≤i≤n-1）。数学上可以证明。

教堂分得的遗产为。由于a[0]…a[n-1]均为正整数，因此要使l最少，则只要证明：

证明：

由递推式可得：

a[1]=a[0]*a[0]-a[0]+1=a[0]*(a[0]-1)+1=a[0]+1；

a[2]=a[1]*(a[1]-1)+1=a[0]*a[1]+1；

…

依次类推，可得a[i]=a[0]*a[1]*…a[i-1]+1（1≤i≤n-1）。

将此结论依次代入下式，可得：

证毕。

由于计算每个亲属的分数是一个递推过程，需要反复进行高精度的加减乘运算。因此可采用面向对象的程序设计方法。定义一个类，将这些运算涉及的函数放在类的公共（public）界面，将类的对象和成员函数访问的高精度数组放在类的私有（private）部分，这样可使主程序的结构变得比较清晰。

【4.5.33　Digital Fortres】

去年的IIUPC比赛，有一道试题“Da Vinci Code”，是有关Dan Brown的最佳售书的故事。本题则是基于他的另一项技术：Digital Fortress。本题给出一个密码文本。请你破译这个文本，使用的解密技术如下。例如，给出一个密码文本：

WECGEWHYAAIORTNU

输出为：

WEAREWATCHINGYOU

在上述实例中，在给出的密码文本“WECGEWHYAAIORTNU”中有16个字符，也就是4的平方。这些字母被放置在n×n（在本例中为4×4）的网格中，并且每个字母从给定的输入中以行为主顺序被放置在网格中（第一行，第二行，第三行，……）。当给定的密码文本放置在网格中时，可以被视为：

W E C G

E W H Y

A A I O

R T N U

对于上面的网格，如果我们以列为主顺序输出字母（第一列，第二列，第三列，……），那么得到以下的解密文本：

WEAREWATCHINGYOU

输入

输入的第一行给出一个单一的数字T，然后给出T个测试用例。每个测试用例一行，在这一行中给出密码文本。密码文本包含大写字母或空格。文本中的字符总数不会超过10 000。

输出

对于每一个测试用例，输出一行，给出解密文本。如果在输入文本中的字符数不是任意数的平方，则输出“INVALID”。

试题来源：IIUPC 2009

在线测试：UVA 11716

提示

首先设计一个函数judge(x)：若密码文本的长度x不是任意整数的平方，则返回0；否则返回x的整数平方根。显然，若judge(x)返回0，则应输出“INVALID”；否则应输出x的整数平方根对应的解密文本。

设x的整数平方根v=4，则解密文本放置在4×4的网格中时，对应密码文本的字符指针如下：

以列为主顺序，解密文件的字母依次为密码文本中第0～3个字符（网格第1列）、4～7个字符（网格第2列）、8～11个字符（网格第3列）、12～15个字符（网格第4列）。

显然，如果密码文本长度x有整数平方根v，则可通过双重循环输出对应的解密文本：外循环i控制列（0≤i≤v），内循环j控制行（0≤j≤v），依次输出密码文本中的第i+v*j个字符。