USACO Training Section 2.2 Preface Numbering

英文原题 中文题译

大致题意：统计在古罗马计数法下从1-N出现的字母的个数。

罗马数字表示法至今沿用于表示目录，不过其用于表示大数不大方便。该表示由7个字母构成，分别是：I=1, V=5, X=10, L=50, C=100, D=500, M=1000。由I,II,III,IV,V,VI,VII,VIII,IX表示1-9，由X,XX,XXX,XL,L,LX,LXX,LXXX,XC表示10,20,...90，由C,CC,CCC,CD,D,DC,DCC,DCCC,CM表示100,200,...900，由M,MM,MMM表示1000,2000,3000。

计数有两种主要方式，一种是逐个生成字串统计，一个是利用数据规律直接计算。前者思路简单，程序较长，后者程序简洁，但需要仔细事先计算。

主体思路：注意到个位、10位、百位的表示，实际上是三个字母一组，IVX,XLC,CDM...由此可以一次性事先统计出在该位上字母出现的个数。计数时只需考虑每个位数字出现的次数即可。

由此，计数＝高位计数＋本位计数＋余数。举例说明：2974中的十位（XLC组合），该组合完整的出现2900次，10-60各出现10次，7出现5次，这就是程序中加法三部分的由来。

看了USACO Training上的标程，似乎都比我的程序复杂，我想我的程序至今应该是最简单的了，呵呵。有点疑惑的是，为什么这个题放在这一节（数据结构与动态规划）。比较牵强的理由，是这其中包含对子结构的判定吧。

/*
ID: blackco3
TASK: preface
LANG: C++
*/
#include <fstream>
#include <iostream>
using namespace std ;
int appc[3][10]={ /* counter for appearance of symbols */
   /*   I II III IV V VI VII VIII IX */
	{0, 1, 3, 6, 7, 7, 8, 10, 13, 14 },
	{0, 0, 0, 0, 1, 2, 3, 4,  5,  5  },
	{0, 0, 0, 0, 0, 0, 0, 0,  0,  1  }
};
char names[7][2]={"I", "V", "X", "L", "C", "D", "M"};
int  n_appear[7]={ 0,   0,   0,   0,   0,   0,   0 };

int main() {
    ofstream fout ("preface.out");
    ifstream fin ("preface.in");
	int n ;
	fin >> n ;
	for( int rank=0, tmp=n, prod=1; tmp ; rank++, prod*=10 ){
		int r=tmp%10;
		tmp /= 10 ;
		for( int i=0; i<3; i++ )
			n_appear[rank*2+i] += tmp*prod*appc[i][9] +
				( r ? appc[i][r-1]*prod + (appc[i][r]-appc[i][r-1])*(n-(tmp*10+r)*prod+1 : 0) ;	
	}
	for( int i=0; i<7; i++ ){
		if( !n_appear[i] )
			continue ;
		fout << names[i] << " " << n_appear[i] << endl ;
	}
	return 0;
}