信息学竞赛宝典:基础算法
上QQ阅读APP看书,第一时间看更新

1.1.4 字符串的展开

【上机练习】字符串的展开(expand)NOIP 2007

如果在输入的字符串中含有类似于“d-h”或者“4-8”的子串,我们就把它当作一种简写。输出时,用连续递增的字母或数字串替代其中的“-”,即将上面的两个子串分别输出为“defgh”和“45678”。在本题中,我们通过增加一些参数,使字符串的展开更为灵活。约定如下。

(1)遇到下面的情况需要进行字符串的展开:在输入的字符串中,出现了“-”,“-”两边同为小写字母或同为数字,且按照ASCII的顺序,“-”右边的字符严格大于左边的字符。

(2)参数p1:当p1=1时,对于字母子串,填充小写字母;p1=2时,对于字母子串,填充大写字母(这两种情况下数字子串的填充方式相同);p1=3时,不论是字母子串还是数字子串,都用与要填充的字母或数字个数相同的星号“*”来填充。 

(3)参数p2:填充字符的重复个数。p2=k表示同一个字符要连续填充k次。例如当p2=3时,子串“d-h”应扩展为“deeefffgggh”。“-”两边的字符不变。 

(4)参数p3:确定是否改为逆序。p3=1表示维持原来顺序,p3=2表示采用逆序输出,注意这时候仍然不包括“-”两边的字符。例如当p1=1、p2=2、p3=2时,子串“d-h”应扩展为“dggffeeh”。

(5)如果“-”右边的字符恰好是左边字符的后继,删除中间的“-”,例如“d-e”应输出为“de”,“3-4”应输出为“34”。如果“-”右边的字符按照ASCII的顺序小于或等于左边的字符,输出时,保留中间的“-”,例如“d-d”应输出为“d-d”,“3-1”应输出为“3-1”。

【输入格式】

第1行为用空格分隔的3个正整数,依次表示参数p1p2p3。 

第2行为字符串,仅由数字、小写字母和“-”组成,行首和行末均无空格。

【输出格式】 

只有一行,为展开后的字符串。 

【输入样例1】 

1 2 1 

abcs-w1234-9s-4zz

【输出样例1】 

abcsttuuvvw1234556677889s-4zz

【输入样例2】

2 3 2 

a-d-d

【输出样例 2】 

aCCCBBBd-d

【输入样例3】 

3 4 2 

di-jkstra2-6 

【输出样例3】 

dijkstra2************

【数据规模】

40%的数据满足:字符串长度不超过5。 

100%的数据满足:1p13,1p28,1p32,字符串长度不超过100。

【算法分析】

虽然这是一道简单的模拟题,但是细节要考虑周全,例如“-”可能出现在字符串的第一个或最后一个,也可能连续出现。

此外,对于字符c来说,判断它是否为小写英文字母可以用islower(c),判断它是否为大写英文字母可以用isupper(c),判断它是否为数字可以用isdigit(c),将之转为小写字母可以用tolower(c),将之转为大写字母可以用toupper(c)。