[数据结构与算法][USACO2.2]序言页码 Preface Numbering(题解)

link

此题首先要要学会罗马数字并且理解他

不然你就会去纠结 $8$ 为什么不可以表示为 $\mathrm{I}\mathrm{V}\mathrm{I}\mathrm{V}$（比如说我）

其实最难解决的是做减法的这种情况，比如说 $4$

我们不难发现，对于一个数 $n$ ，它所需的字母就等于把他拆分成若干个整十数，这若干个整十数所需字母之和。(可能描述得有点抽象)

比如 $1314$ 可以拆分为 $1000+300+10+4$，而 $1000$ 的罗马数字是 $\mathrm{M}$，$300$ 的罗马数字是 $\mathrm{C}\mathrm{C}\mathrm{C}$，$10$ 的罗马数字是 $\mathrm{X}$，$4$ 的罗马数字是 $\mathrm{I}\mathrm{V}$，所以 $1314$ 的罗马数字是 $\mathrm{M}\mathrm{C}\mathrm{C}\mathrm{C}\mathrm{X}\mathrm{I}\mathrm{V}$

所以我们只用打出整十数的减法拆分情况即可，这就只用讨论 $4$ 种情况，这就很容易打出以下代码：

$su{m}_i$ 表示第 $i$ 个字母用的个数

void solve(int t) {
	if (t >= 1 && t <= 9) {
    	if (t % 5 == 4) sum[1]++;
    	else sum[1] += t % 5;
    	if (4 <= t && t <= 8) sum[2]++;
		if (t == 9) sum[3]++;
	} else if (t >= 10 && t <= 90 && t % 10 == 0) {
		t /= 10;//除10好判断
    	if (t % 5 == 4) sum[3]++;
    	else sum[3] += t % 5;
    	if (4 <= t && t <= 8) sum[4]++;
		if (t == 9) sum[5]++;
	} else if (t >= 100 && t <= 900 && t % 100 == 0) {
		t /= 100;//除100好判断
    	if (t % 5 == 4) sum[5]++;
    	else sum[5] += t % 5;
    	if (4 <= t && t <= 8) sum[6]++;
		if (t == 9) sum[7]++;
	} else if (t >= 1000 && t <= 3500 && t % 1000 == 0) {
		t /= 1000;//除100好判断
		sum[7] += t;
	}
}

在加上 $1?n$ 的循环和拆分的代码就能 $\mathrm{A}\mathrm{C}$ 了，时间复杂度接近 $\mathcal{O}(n)$

$code$

#include <bits/stdc++.h>
using namespace std;
int n;
int sum[8];
void solve(int t) {
	if (t >= 1 && t <= 9) {
    	if (t % 5 == 4) sum[1]++;
    	else sum[1] += t % 5;
    	if (4 <= t && t <= 8) sum[2]++;
		if (t == 9) sum[3]++;
	} else if (t >= 10 && t <= 90 && t % 10 == 0) {
		t /= 10;//除10好判断
    	if (t % 5 == 4) sum[3]++;
    	else sum[3] += t % 5;
    	if (4 <= t && t <= 8) sum[4]++;
		if (t == 9) sum[5]++;
	} else if (t >= 100 && t <= 900 && t % 100 == 0) {
		t /= 100;//除100好判断
    	if (t % 5 == 4) sum[5]++;
    	else sum[5] += t % 5;
    	if (4 <= t && t <= 8) sum[6]++;
		if (t == 9) sum[7]++;
	} else if (t >= 1000 && t <= 3500 && t % 1000 == 0) {
		t /= 1000;//除100好判断
		sum[7] += t;
	}
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
    	int t = i;
    	int tot = 1;//表示10的tot次方 
		while (t != 0) {//拆分 
			solve((t % 10) * tot);//分别解决 
			t /= 10;
			tot *= 10;
		}
    }
    if (sum[1] != 0) printf("I %d\n", sum[1]);
    if (sum[2] != 0) printf("V %d\n", sum[2]);
    if (sum[3] != 0) printf("X %d\n", sum[3]);
    if (sum[4] != 0) printf("L %d\n", sum[4]);
    if (sum[5] != 0) printf("C %d\n", sum[5]);
    if (sum[6] != 0) printf("D %d\n", sum[6]);
    if (sum[7] != 0) printf("M %d\n", sum[7]);
    return 0;
}
//the TJ by cqbzjyh