USACO代码解析Preface Numbering (preface)

《USACO代码解析Preface Numbering (preface)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、描述一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，以下是标准数字表:I1V5X10L50C100D500M1000最多3个同样的可以表示为10n的数字(I,X,C,M)可以连续放在一起，表示它们的和:III=3CCC=300可表示为5x10n的字符(V,L,D)从不连续出现。除了下一个规则，一般来说，字符以递减的顺序接连出现:CCLXVIII=100+100+50+10+5+1+1+1=268有时，一个可表示为10n的数出现在一个比它大1级或2级的数前(I在V或X前面，X在L或C前面，

2、等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:IV=4IX=9XL=40一个数用罗马数字来表示有且仅有一种而且不能复合嵌套使用（比如I是1X是10有人可能要说IXL就能表示50-10-1但是IXL绝对不能用来表达39）（那么39用什么来表示呢XXXIX是唯一而且正确的选择--）像XD,IC,和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成CDXC;对于IC(99的错误表达)，可以写成XCIX;对于XM(990的错误表达)，可以写成CMXC。90写成XC

3、而不是LXL,因为L后面的X意味着后继标记是X或者更小(不管怎样，可能吧)（等同于阿拉伯数字每位数字分别表示）。给定N(1<=N<3,500)，序言的页码数，请统计在第1页到第N页中，有几个I出现，几个V出现，等等(从小到大的顺序)。不要输出没有出现过的字符。比如N=5,那么页码数为:I,II,III,IV,V.总共有7个I出现，2个V出现。[编辑]格式PROGRAMNAME:prefaceINPUTFORMAT:(preface.in)一个整数N。OUTPUTFORMAT:(preface.out)每行一个字

4、符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。[编辑]SAMPLEINPUT5[编辑]SAMPLEOUTPUTI7V2任意一个数对应的罗马数字，都可以用其他几个n×10^k表示，比如999=900+90+9=CM+XC+IX;所以我们预先处理出1~9,10~90,100~900,1000~3000这几个数所对应的字符，我们应该制造一个数字表：constshu:array[1..4,0..9]ofstring=((,'I','II','III','IV','V','VI','VII',

5、'VIII','IX'),//个(,'X','XX','XXX','XL','L','LX','LXX','LXXX','XC'),//十(,'C','CC','CCC','CD','D','DC','DCC','DCCC','CM'),//百(,'M','MM','MMM',,,,,,));//千#include#includeusingnamespacestd;//0123456//IVXLCDMintres[7];inta[10][7],b[10][7],c[10][7

6、],d[10][7];//个位，十位，百位，千位。intmain(){/*1~910~90100~9001000~3000*/freopen("preface.in","r",stdin);freopen("preface.out","w",stdout);//个位为1，则I（0）出现1次；为2则I两次。。。//IIIIIIIIIIa[1][0]=a[6][0]=1;a[2][0]=a[7][0]=2;a[3][0]=a[8][0]=3;a[4][0]=a[9][0]=1;//IVVVIVIIVIIIIXfor

7、(inti=4;i<=8;i++)a[i][1]=1;a[9][2]=1;//十位：//XXXXXXXLLLXLXXLXXXXCb[1][2]=b[6][2]=1;b[2][2]=b[7][2]=2;b[3][2]=b[8][2]=3;b[4][2]=b[9][2]=1;for(inti=4;i<=8;i++)b[i][3]=1;b[9][4]=1;//CCCCCCCDDDCDCCDCCCCMc[1][4]=c[6][4]=1;c[2][4]=c[7][4]=2;c[3][4]=c[8][4]=3;c[4][4

8、]=c[9][4]=1;for(inti=4;i<=8;i++)c[i][5]=1;c[9][6]=1;//MMMMMMd[1][6]=1;d[2][6]=2;d[3][6]=3;intN;cin>>N;for(intt=1;t<=N;t++){intn=t;//千位if(n/1000!=0){inttmp=n/1000;for(inti=0;i<=6;i++)res[i]+=d[tm