P1465 [USACO2.2] 序言页码 Preface Numbering

题目描述

给定 $n$，求 $1\sim n$ 的 罗马数字 表示中，各个字符出现了多少次。

比如 $n=5$，表示为 I, II, III, IV, V。总共有 $7$ 个 I 出现，$2$ 个 V 出现。

输入格式

一个整数 $n$。

输出格式

每行一个字符和一个数字 $k$，表示这个字符出现了 $k$ 次。字符必须按罗马数字表中的递增顺序输出。

输入输出样例 #1

输入 #1

5

输出 #1

I 7
V 2

说明/提示

【数据范围】
对于 $100\%$ 的数据，$1\le n\le 3500$。

翻译来自NOCOW

USACO 2.2

C++实现

#include<bits/stdc++.h>
using namespace std;

int id[][3]={{1, 2, 3}, {3, 4 ,5}, {5, 6 ,7}, {7, 0, 0}};
int cnt[10];
char str[]=" IVXLCDM";
int w[][3]={{0, 0, 0}, {1, 0, 0}, {2, 0, 0}, {3, 0, 0}, // 0~4
{1, 1, 0}, {0, 1, 0}, {1, 1, 0}, {2, 1, 0}, {3, 1, 0}, // 5~8
{1, 0, 1}}; // 9

void add(int x) {
for(int i=0;x;i++, x/=10) {
int j=x%10;
for(int k=0;k<3;k++)
cnt[id[i][k]]+=w[j][k];
}
}

int main() {
ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=1;i<=n;i++) add(i);
for(int i=1;i<=7;i++)
if(cnt[i]) cout<<str[i]<<’ '<<cnt[i]<<endl;
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容