题目
给出一个罗马算式（其实就是数字用罗马字母表示的算式），问是否成立；如果字母代表的是0-9，有没有可能存在一种方案使得自然算式成立
解法
第一问很简单，我就不说什么了。不过处理的时候有简单的地方，如果第i个罗马数字>第i-1个罗马数字，结果就加上num[i]-2*[numi-1]。
第二问让我纠结好久。。fzu赛区一个题目和这个一样，不过那个数据量小。这题数据量MS很大。如果没有剪枝的程序跑了1.5秒。。虽然uva是过了，poj却差很多。后来google，找到一个日本人写的代码，跑了79ms。。。。仔细研读，发现我漏了一个重要的剪枝条件：a+b=c能够成立当且仅当c的位数<=1+max(a、b的位数并且c的位数>=
max(a、b的位数)，就+了这一个判断在POJ上就过了。。。。其他的还有很大的常数优化空间，不过我这种人很懒的- -
代码
1 //============================================================================
2 // Name : pku1213.cpp
3 // Author : yzhw
4 // Version :
5 // Copyright : yzhw
6 // Description : Hello World in C++, Ansi-style
7 //============================================================================
8
9 #include <iostream>
10 # include <cstdio>
11 # include <cstring>
12 # include <algorithm>
13 using namespace std;
14 char str[128],d[3][20];
15 int charmap[255],digit[255];
16 bool flag;
17 int GetRomanNum(char *num)
18 {
19 int res=digit[*num];
20 for(int i=1;num[i]!='\0';i++)
21 if(digit[num[i]]>digit[num[i-1]])
22 res=res-2*digit[num[i-1]]+digit[num[i]];
23 else res+=digit[num[i]];
24 return res;
25 }
26 int GetNormalNum(char *num)
27 {
28 int res=0;
29 for(int i=0;num[i]!='\0';i++)
30 res=res*10+charmap[num[i]];
31 return res;
32 }
33 bool search(int num,int pos)
34 {
35 if(num==3)
36 {
37 if(GetNormalNum(d[0])+GetNormalNum(d[1])==GetNormalNum(d[2]))
38 {
39 if(!flag)
40 {
41 flag=true;
42 return false;
43 }
44 else
45 return true;
46 }
47 else return false;
48 }
49 else if(d[num][pos]=='\0')
50 return search(num+1,1);
51 else
52 {
53 if(charmap[d[num][pos]]!=-1)
54 return search(num,pos+1);
55 else
56 {
57 for(int i=0;i<10;i++)
58 {
59 charmap[d[num][pos]]=i;
60 if(search(num,pos+1)) return 1;
61 charmap[d[num][pos]]=-1;
62 }
63 return 0;
64 }
65 }
66 }
67 bool search(int num)
68 {
69 if(num==3)
70 {
71 if(search(0,1)) return true;
72 else return false;
73 }
74 else if(charmap[d[num][0]]!=-1) return search(num+1);
75 else
76 {
77 for(int i=1;i<10;i++)
78 {
79 charmap[d[num][0]]=i;
80 if(search(num+1)) return true;
81 charmap[d[num][0]]=-1;
82 }
83 return false;
84 }
85 }
86 int main() {
87 digit['I']=1;
88 digit['V']=5;
89 digit['X']=10;
90 digit['L']=50;
91 digit['C']=100;
92 digit['D']=500;
93 digit['M']=1000;
94 while(true)
95 {
96 scanf("%s",str);
97 if(str[0]=='#') break;
98 strcpy(d[0],strtok(str,"+"));
99 strcpy(d[1],strtok(NULL,"="));
100 strcpy(d[2],strtok(NULL," "));
101 //test Roman Number
102 if(GetRomanNum(d[0])+GetRomanNum(d[1])==GetRomanNum(d[2]))
103 printf("Correct ");
104 else
105 printf("Incorrect ");
106 //test Normal Number
107 flag=false;
108 memset(charmap,-1,sizeof(charmap));
109 if(strlen(d[2])>max(strlen(d[0]),strlen(d[1]))+1||strlen(d[2])<max(strlen(d[0]),strlen(d[1])))
110 {
111 printf("impossible\n");
112 continue;
113 }
114 if(search(0)) printf("ambiguous\n");
115 else if(flag) printf("valid\n");
116 else printf("impossible\n");
117 }
118 return 0;
119 }
120