Solution - 「USACO2.2」序言页码 Preface Numbering

link

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

不然你就会去纠结 \(8\) 为什么不可以表示为 \(\rm IVIV\)（比如说我）

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

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

比如 \(1314\) 可以拆分为 \(1000+300+10+4\)，而 \(1000\) 的罗马数字是 \(\rm M\)，\(300\) 的罗马数字是 \(\rm CCC\)，\(10\) 的罗马数字是 \(\rm X\)，\(4\) 的罗马数字是 \(\rm IV\)，所以 \(1314\) 的罗马数字是 \(\rm MCCCXIV\)

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

\(sum_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;//除1000好判断
		sum[7] += t;
	}
}

在加上 \(1 -n\) 的循环和拆分的代码就能 \(\rm AC\) 了，时间复杂度接近 \(\mathcal{O}(n)\)

\(code\)

#include 
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;//除1000好判断
		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