题解 P1465 【序言页码 Preface Numbering】

· · 题解

/* * P:1465

* Au:Small_Ash

* 本题本人采用的是一个罗马数字的快速生成法...(自己随便取的,[一本正经的胡说八道])

* 首先,我们需要一个表(可以手推,别问我为什么怎么清楚)

* 1 I * 4 IV * 5 V * 9 IX * 10 X * 40 XL

* 50 L * 90 XC

* 100 C

* 400 CD

* 500 D

* 900 CM

* 1000 M

* (没错,就是1,4,5,9及其全部的10^n次方倍[然而罗马数字最大到3500])

* 为什么要这个表呢,规律我不会证(都说是我乱想想出来的),但是确实可以用

* 比如一个数 2333 大于1000 2倍 所以是 MM

* 余数 333 大于100 3倍 所以是CCC

* 余数 33 大于10 3倍 所以是XXX

* 余数 3 大于1 3倍 所以是III

* 所以2333=MMCCCXXXIII (我真的乱选的,不是正好这么奇怪)

* 又比如 834->334->34->4->0

* 500 100 10 4

* D CCC XXX IV

* 所以是DCCCXXXIV,所以,利用这个表,我们就能快速求出一个罗马数字的字母个数,然后再累加就行了

* 下面是代码.

*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
int n;
int i[20],v[20],x[20],l[20],c[20],d[20],m[20],A[20];
int ansi,ansv,ansx,ansl,ansc,ansd,ansm;
void mem(){
    A[1]=1;i[1]=1;
    A[2]=4;i[2]=1;v[2]=1;
    A[3]=5;v[3]=1;
    A[4]=9;i[4]=1;x[4]=1;
    A[5]=10;x[5]=1;
    A[6]=40;x[6]=1;l[6]=1;
    A[7]=50;l[7]=1;
    A[8]=90;x[8]=1;c[8]=1;
    A[9]=100;c[9]=1;
    A[10]=400;c[10]=1;d[10]=1;
    A[11]=500;d[11]=1;
    A[12]=900;c[12]=1;m[12]=1;
    A[13]=1000;m[13]=1;
}
void add(int b,int num){
    ansi+=i[b]*num;
    ansv+=v[b]*num;
    ansx+=x[b]*num;
    ansl+=l[b]*num;
    ansc+=c[b]*num;
    ansd+=d[b]*num;
    ansm+=m[b]*num;
    return;
}
int main()
{
    scanf("%d",&n);
    mem();
    for (int j=1;j<=n;j++){
        int temp=j,now=13;
        while (temp){
            while (temp<A[now]) now--;
            add(now,temp/A[now]);
            temp%=A[now];
        }
    }
    if (ansi!=0) printf("I %d\n",ansi);
    if (ansv!=0) printf("V %d\n",ansv);
    if (ansx!=0) printf("X %d\n",ansx);
    if (ansl!=0) printf("L %d\n",ansl);
    if (ansc!=0) printf("C %d\n",ansc);
    if (ansd!=0) printf("D %d\n",ansd);
    if (ansm!=0) printf("M %d\n",ansm);
    return 0;
}