USACO代码解析Preface Numbering (preface).docx

描述一类书的序言是以罗马数字标页码的。传统罗马数字用单个字母表示特定的数值，以下是标准数字表:I 1 V 5 X 10 L 50 C 100 D 500 M 1000 最多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前面，等等)。在这种情况下，数值等于后面的那个数减去前面的那个数:IV = 4IX = 9XL = 40一个数 用罗马数字来表示 有且仅有一种 而且不能复合嵌套使用（比如I是1 X是10 有人可能要说 IXL就能表示50-10-1 但是IXL绝对不能用来表达39 ） （那么39用什么来表示呢 XXXIX是唯一 而且正确的选择- -）像XD, IC, 和XM这样的表达是非法的，因为前面的数比后面的数小太多。对于XD(490的错误表达)，可以写成 CDXC; 对于IC(99的错误表达)，可以写成XCIX; 对于XM(990的错误表达)，可以写成CMXC。 90 写成 XC 而不是 LXL, 因为 L 后面的 X 意味着后继标记是 X 或者更小 (不管怎样，可能吧)（等同于阿拉伯数字 每位 数字分别表示）。给定N(1 = N 3,500)， 序言的页码数，请统计在第1页到第N页中，有几个I出现，几个V出现，等等 (从小到大的顺序)。不要输出没有出现过的字符。比如N = 5, 那么页码数为: I, II, III, IV, V. 总共有7个I出现，2个V出现。编辑格式PROGRAM NAME: prefaceINPUT FORMAT:(preface.in)一个整数N。OUTPUT FORMAT:(preface.out)每行一个字符和一个数字k，表示这个字符出现了k次。字符必须按数字表中的递增顺序输出。编辑SAMPLE INPUT5编辑SAMPLE OUTPUTI 7V 2任意一个数对应的罗马数字，都可以用其他几个n10k表示，比如999=900+90+9=CM+XC+IX;所以我们预先处理出19,1090,100900,10003000这几个数所对应的字符，我们应该制造一个数字表： const shu:array1.4,0.9 of string=(,I,II,III,IV,V,VI,VII,VIII,IX),/个 (,X,XX,XXX,XL,L,LX,LXX,LXXX,XC),/十 (,C,CC,CCC,CD,D,DC,DCC,DCCC,CM),/百 (,M,MM,MMM,);/千#include #include using namespace std;/ 0 1 2 3 4 5 6/ I V X L C D Mint res7;int a107,b107,c107,d107;/个位，十位，百位，千位。 int main()/*19109010090010003000*/freopen(preface.in, r, stdin);freopen(preface.out, w, stdout);/个位为1，则I（0）出现1次； 为2则I两次。/I II III IIIIa10 = a60 = 1;a20 =a70 = 2;a30 =a80 = 3; a40 =a90 = 1;/ IV VVI VII VIII IXfor(int i = 4; i = 8; i+) ai1 = 1; a92=1;/十位：/X XX XXX XL L LX LXX LXXX XCb12 = b62 = 1;b22 =b72 = 2;b32 =b82 = 3; b42 =b92 = 1;for(int i = 4; i = 8; i+) bi3 = 1; b94=1;/C CC CCC CD D DC DCC DCCC CMc14 = c64 = 1;c24 =c74 = 2;c34 =c84 = 3; c44 =c94 = 1;for(int i = 4; i N;for(int t = 1; t = N; t+)int n = t;/千位 if(n/1000!=0) int tmp = n/1000;for(int i = 0; i =6; i+)resi+=dtmpi;/百位 n=n%1000;if(n/100!=0)int tmp = n/100;for(int i = 0; i = 6; i+)resi += ctmpi;/十位 n = n%100;if(n/10!=0)int tmp = n/10;for(int i = 0; i = 6; i+)resi += btmpi;/个位 n = n%10;if(n!=0)int tmp = n/1;for(int i = 0; i = 6; i+)resi += atmpi;for(int i = 0; i = 6; i+)switch(i)case 0: if(resi!=0) coutI resiendl;break;case 1: if(resi!=0) coutV resiendl;break;case 2: if(resi!=0) coutX resiendl;break;case 3: if(resi!=0) coutL resiendl;break;case 4: if(resi!=0) coutC resiendl;break;case 5: if(resi!=0) coutD resiendl;break;case 6: if(resi!=0) coutM resiendl;break;更妙：#include#includeint main() FILE *fin,*fout; int i,v,x,l,c,d,m,j,k,n; fin=fopen(preface.in,r); fout=fopen(preface.out,w); assert(fin!=NULL & fout!=NULL); fscanf(fin,%d,&n); i=0; v=0; x=0; l=0; c=0; d=0; m=0; for (j=1;j0) if (k=1000) k-=1000;m+; if (k=900 & k=500 & k=400 & k=100 & k=90 & k=50 & k=40 & k=10 & k=9 & k=5 & k=4 & k=1 & k4) k-=1;i+; if (i!=0) fprintf(fout,I%dn,i); if (v!=0) fprintf(fout,V%dn,v); if (x!=0) fprintf(fout,X%dn,x); if (l!=0) fprintf(fout,L%dn,l); if (c!=0) fprintf(fout,C%dn,c); if (d!=0) fprintf(fout,D%dn,d); if (m!=0) fprintf(fout,M%dn,m);或者：#includeint I,V,X,L,C,D,M;int main()freopen(preface.in,r,stdin);freopen(preface.out,w,stdout);int n;scanf(%d,&n);for(int i=1;i=n;i+)int w1=i%10,w2=i/10%10,w3=i/100%10,w4=i/1000;if(w1=1) I+;if(w1=2) I+=2;if(w1=3) I+=3;if(w1=4) I+;V+;if(w1=5) V+;if(w1=6) I+;V+;if(w1=7) I+=2;V+;if(w1=8) I+=3;V+;if(w1=9) I+;X+;if(w2=1) X+;if(w2=2) X+=2;if(w2=3) X+=3;if(w2=4) X+;L+;if(w2=5) L+;if(w2=6) X+;L+;if(w2=7) X+=2;L+;if(w2=8) X+=3;L+;if(w2=9) X+;C+;if(w3=1) C+;if(w3=2) C+=2;if(w3=3) C+=3;if(w3=4) C+;D+;if(w3=5) D+;if(w3=6) C+;D+;if(w3=7) C+=2;D+;if(w3=8) C+=3;D+;if(w3=9) C+;M+;if(w4=1) M+;if(w4=2)