[usaco]罗马数字

Preface Numbering

A certain book’s prefaces are numbered in upper case Roman numerals. Traditional Roman numeral values use a single letter to represent a certain subset of decimal numbers. Here is the standard set:

        I   1     L   50    M  1000
        V   5     C  100
        X  10     D  500

As many as three of the same marks that represent 10n may be placed consecutively to form other numbers:

III is 3
CCC is 300
Marks that have the value 5x10n are never used consecutively.

Generally (with the exception of the next rule), marks are connected together and written in descending order to form even more numbers:

CCLXVIII = 100+100+50+10+5+1+1+1 = 268
Sometimes, a mark that represents 10^n is placed before a mark of one of the two next higher values (I before V or X; X before L or C; etc.). In this case, the value of the smaller mark is SUBTRACTED from the mark it precedes:

IV = 4
IX = 9
XL = 40
This compound mark forms a unit and may not be combined to make another compound mark (e.g., IXL is wrong for 39; XXXIX is correct).

Compound marks like XD, IC, and XM are not legal, since the smaller mark is too much smaller than the larger one. For XD (wrong for 490), one would use CDXC; for IC (wrong for 99), one would use XCIX; for XM (wrong for 990), one would use CMXC. 90 is expressed
XC and not LXL, since L followed by X connotes that successive marks are X or smaller (probably, anyway).

Given N (1 <= N < 3,500), the number of pages in the preface of a book, calculate and print the number of I’s, V’s, etc. (in order from lowest to highest) required to typeset all the page numbers (in Roman numerals) from 1 through N. Do not print letters
that do not appear in the page numbers specified.

If N = 5, then the page numbers are: I, II, III, IV, V. The total number of I’s is 7 and the total number of V’s is 2.

PROGRAM NAME: preface
INPUT FORMAT
A single line containing the integer N.
SAMPLE INPUT (file preface.in)
5

OUTPUT FORMAT
The output lines specify, in ascending order of Roman numeral letters, the letter, a single space, and the number of times that letter appears on preface page numbers. Stop printing letter totals after printing the highest value letter used to form preface
numbers in the specified set.
SAMPLE OUTPUT (file preface.out)
I 7
V 2

 

————————————————————————————————————————
题目给出一个整数N,要求求出1-》N的所有的罗马数表示法,然后统计各个字母的数量。

由罗马数的表示法,可以看出,每一位上的表示是基本相同的,
比如1->9
I II III IV V VI VII VIII IX
10 ->90
X XX XXX XL L LX LXX LXXX XC

从上边可以看出一些规律。
因此每一位数字需要3个字母即可表示出来。
我们定义以下二维数组:
char index1[4][3]={
 {‘I’,’V’,’X’},
 {‘X’,’L’,’C’},
 {‘C’,’D’,’M’},
 {‘M’}
};
因此可以用这个数组表示一位数:
10^r->9*10^r:
index1[r][0]   index1[r][0]index1[r][0]   index1[r][0]index1[r][0]index1[r][0] index1[r][0]index1[r][1] index1[r][1]
index1[r][1]index1[r][0] index1[r][1]index1[r][0]index1[r][1] index1[r][1]index1[r][0]index1[r][1]index1[r][0]index1[r][0]index1[r][0] index1[r][0]index1[r][2]
因此我的解法是:
—————————————————————————————————————————
 

/*
ID: yunleis2
PROG: preface
LANG: C++
*/
#include<fstream>
#include<iostream> 
using namespace std;
int result[7]={0};
char str[7]={'I','V',
'X','L',
'C','D','M'};
void getNum1(int r,int c);
int getindex11(char c);
char index1[4][3]={
	{'I','V','X'},
	{'X','L','C'},
	{'C','D','M'},
	{'M'}
};
int main()
{
	fstream fin("preface.in",ios::in);
	int N;
	fin>>N;
	for(int i=1;i<=N;i++)
	{
		int r=0;
		int t=i;
		while(t!=0)
		{
			getNum1(r,t%10);
			r++;
			t=t/10;
		}
	}
	fstream fout("preface.out",ios::out);
	for(int i=0;i<7;i++)
	{
		if(result[i]!=0)
		{
			fout<<str[i]<<" "<<result[i]<<endl;
		}
	} 
}
void getNum1(int r,int c)
{
	 
	if(c==1)
	{
		result[getindex11(index1[r][0])]++;
	}
	if(c==2)
	{
		result[getindex11(index1[r][0])]+=2;
	}
 
	if(c==3)
	{
		result[getindex11(index1[r][0])]+=3;
	}
	if(c==4)
	{
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][1])]++;
	}
	if(c==5)
	{
		result[getindex11(index1[r][1])]++;
	}
	if(c==6)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==7)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==8)
	{
		result[getindex11(index1[r][1])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][0])]++;
	}
	if(c==9)
	{
		result[getindex11(index1[r][0])]++;
		result[getindex11(index1[r][2])]++;
	}
}
int getindex11(char c)
{
	if(c=='I')
		return 0;
	if(c=='V')
		return 1;
	if(c=='X')
		return 2;
	if(c=='L')
		return 3;
	if(c=='C')
		return 4;
	if(c=='D')
		return 5;
	if(c=='M')
		return 6;
}