USACO Preface Numbering 构造

一开始看到这道题目的时候,感觉好难

还要算出罗马的规则。

但是仔细一看,数据规模很小, n 只给到3500

看完题目给出了几组样例之后就有感觉了

解题方法就是:

n的每个十进制数 转换成相应的罗马数字,然后统计每个罗马数字出现的次数即可

还是一道简单的构造题。

(以下摘自https://www.byvoid.com/blog/usaco-221preface-numbering/)

转化有以下规则:

1、数较大部分在前,较小部分在后

2、表示10整倍数的字母(I X C M)最多可以累加三次

3、要累加4次的数应该将比该数的字母稍大的表示5整倍数或是10的整倍数的字母在后,累加的字母在前(例如IV XL CD CM)

了解以上规则后发现并不需要实际“转化”出罗马数字,而只用统计每个字母出现的次数。

My Source Code:

/*
ID: wushuai2
PROG: preface
LANG: C++
*/
//#pragma comment(linker, "/STACK:16777216") //for c++ Compiler
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
#include <stack>
#include <string>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#define Max(a,b) (((a) > (b)) ? (a) : (b))
#define Min(a,b) (((a) < (b)) ? (a) : (b))
#define Abs(x) (((x) > 0) ? (x) : (-(x)))
#define MOD 1000000007
#define pi acos(-1.0) using namespace std; typedef long long ll ;
typedef unsigned long long ull ;
typedef unsigned int uint ;
typedef unsigned char uchar ; template<class T> inline void checkmin(T &a,T b){if(a>b) a=b;}
template<class T> inline void checkmax(T &a,T b){if(a<b) a=b;} const double eps = 1e- ;
const int M = ;
const ll P = 10000000097ll ;
const int INF = 0x3f3f3f3f ;
const int MAX_N = ;
const int MAXSIZE = ; int N, ans[];
string op[][] = {
{},
{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
{"", "M", "MM", "MMM"}
}; void add(string str){
int i, j;
for(i = ; i < str.length(); ++i){
if(str[i] == 'I') ++ans[];
else if(str[i] == 'V') ++ans[];
else if(str[i] == 'X') ++ans[];
else if(str[i] == 'L') ++ans[];
else if(str[i] == 'C') ++ans[];
else if(str[i] == 'D') ++ans[];
else if(str[i] == 'M') ++ans[];
}
} int main() {
ofstream fout ("preface.out");
ifstream fin ("preface.in");
int i, j, k, t, n, s, c, w, q;
fin >> N;
for(i = ; i <= N; ++i){
int temp_g = i % ;
string temp = op[][temp_g];
add(temp);
if(i < ) continue;
int temp_s = (i / ) % ;
temp = op[][temp_s];
add(temp); if(i < ) continue;
int temp_b = (i / ) % ;
temp = op[][temp_b];
add(temp); if(i < ) continue;
int temp_q = i / ;
temp = op[][temp_q];
add(temp);
}
int flag = -;
for(i = ; i >= ; --i){
if(ans[i]){
flag = i;
break;
}
}
for(i = ; i <= flag; ++i){
if(i == ){
fout << "I" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "V" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "X" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "L" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "C" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "D" << ' ' << ans[i] << endl;
} else if(i == ){
fout << "M" << ' ' << ans[i] << endl;
}
} fin.close();
fout.close();
return ;
}
上一篇:xshell退出保持后台服务运行的方法


下一篇:LSD-SLAM深入学习(3)-代码解析