USACO/preface

分析一

枚举

首先大多数人都能想到的算法就是枚举，因为枚举容易易懂。虽说枚举不超时，但是我们也应该尽可能优化，使程序更快速。所以我们应该制造一个数字表：

const
  shu:array[1..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','','','','','',''));//千

那么之后进行枚举时就可以加快速度...详细内容请看程序ID:81585271;-Holy Tears;

分析二

数学问题

这道题的n只有3000多，从1~n把根据题目转换成字母，然后统计出现次数也不会超时。不过这里介绍另一种更高效的算法。

0~9中IVX出现的次数和10~19,20~29,x0~x9中的相同（其它字母都未出现）。0~99中仅十位产生的字母中，字母出现的次数相同，不同的是字母成了XLC，后移了2位。

我们把n按十进制位从低到高的顺序统计每位出现的字母次数。

以n=234为例，

仅个位：23个0~9的次数，1个0~3的次数，1个4的次数。(IVX)

仅十位：2个0~9的次数*10，1个0~2的次数*10，5个3的次数。(XLC)

仅百位：0个0~9的次数*100，1个0~1的次数*100，35个2的次数。(CDM)

分析三

数学统计 首先，不考虑顺序，那么任意一个数对应的罗马数字，都可以用其他几个n×10^k表示，比如999=900+90+9=CM+XC+IX;所以我们预先处理出1~9,10~90,100~900,1000~3000这几个数所对应的字符，这样再枚举效率就要高些（当然对于3000的数据看不太出来，要是10^6试试……）。

分析四

每一位对应三个字母

个位 I V X

十位 X L C

百位 C D M

千位 M

字母 A B C

然后：

1对应A，2对应AA，3对应AAA，4对应AB，5对应B，6对应BA，7对应BAA，8对应BAAA，9对应AC

这样先写一个1..9,A..C的常量数组，然后对每一个数的每一位进行统计就OK了~

分析五

呃~用点动态规划.建立一个字符串数组,长度3500,保存对应数字的罗马数字形式.计算一个数的罗马数,如果已经存在,就直接返回,否则按位分解,比如2530,分解成2000 + 530,2000 = MM,530已经计算出来,直接加就行了.以此类推.

当然这个算法论速度比不上上面任意一个算法,但是程序稍加改动就能生成3500以内任一数字的罗马数形式,而且子问题不会重复计算,所以速度还是很OK的.见C++

分析六

打表，将所有数字的罗马数字存起来。

PS：打表只要用excel的roman(x)函数，然后一拖就行了......

这种方法太威武了……—wsc500

参考代码

C

C++

Pascal

Java

引用

[1]

[2]