100861J Jig-saw Puzzle

给一个火柴棒罗马数字表达式(保证不合法),要求你对一根火柴做出改变,使得式子仍然成立,输出成立的所有式子。

模拟即可…想清楚的话其实也比较好写

首先需要判断数字是否合法,不能出现三个以上连续的字符并且十位和个位要分开,以及不能大于等于$90$,$1-3$的倍数只能列举表示。这样的话对读入也会造成麻烦,于是学习某人打了一张表…

然后在判断表达式成立(只有一个等号,没有两个以上连续的运算符)的基础上判断等式成立即可(可以用一个栈简单地实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
#include <bits/stdc++.h>
using namespace std;
string ss,ori;
int n;
map<string ,int > rfl;
set<string > res;
inline bool Is_Num(char x){return x=='I' || x=='V' || x=='X' || x=='L';}
void Make_Table()
{
rfl["I"]=1;
rfl["II"]=2;
rfl["III"]=3;
rfl["IV"]=4;
rfl["V"]=5;
rfl["VI"]=6;
rfl["VII"]=7;
rfl["VIII"]=8;
rfl["IX"]=9;
rfl["X"]=10;
rfl["XI"]=11;
rfl["XII"]=12;
rfl["XIII"]=13;
rfl["XIV"]=14;
rfl["XV"]=15;
rfl["XVI"]=16;
rfl["XVII"]=17;
rfl["XVIII"]=18;
rfl["XIX"]=19;
rfl["XX"]=20;
rfl["XXI"]=21;
rfl["XXII"]=22;
rfl["XXIII"]=23;
rfl["XXIV"]=24;
rfl["XXV"]=25;
rfl["XXVI"]=26;
rfl["XXVII"]=27;
rfl["XXVIII"]=28;
rfl["XXIX"]=29;
rfl["XXX"]=30;
rfl["XXXI"]=31;
rfl["XXXII"]=32;
rfl["XXXIII"]=33;
rfl["XXXIV"]=34;
rfl["XXXV"]=35;
rfl["XXXVI"]=36;
rfl["XXXVII"]=37;
rfl["XXXVIII"]=38;
rfl["XXXIX"]=39;
rfl["XL"]=40;
rfl["XLI"]=41;
rfl["XLII"]=42;
rfl["XLIII"]=43;
rfl["XLIV"]=44;
rfl["XLV"]=45;
rfl["XLVI"]=46;
rfl["XLVII"]=47;
rfl["XLVIII"]=48;
rfl["XLIX"]=49;
rfl["L"]=50;
rfl["LI"]=51;
rfl["LII"]=52;
rfl["LIII"]=53;
rfl["LIV"]=54;
rfl["LV"]=55;
rfl["LVI"]=56;
rfl["LVII"]=57;
rfl["LVIII"]=58;
rfl["LIX"]=59;
rfl["LX"]=60;
rfl["LXI"]=61;
rfl["LXII"]=62;
rfl["LXIII"]=63;
rfl["LXIV"]=64;
rfl["LXV"]=65;
rfl["LXVI"]=66;
rfl["LXVII"]=67;
rfl["LXVIII"]=68;
rfl["LXIX"]=69;
rfl["LXX"]=70;
rfl["LXXI"]=71;
rfl["LXXII"]=72;
rfl["LXXIII"]=73;
rfl["LXXIV"]=74;
rfl["LXXV"]=75;
rfl["LXXVI"]=76;
rfl["LXXVII"]=77;
rfl["LXXVIII"]=78;
rfl["LXXIX"]=79;
rfl["LXXX"]=80;
rfl["LXXXI"]=81;
rfl["LXXXII"]=82;
rfl["LXXXIII"]=83;
rfl["LXXXIV"]=84;
rfl["LXXXV"]=85;
rfl["LXXXVI"]=86;
rfl["LXXXVII"]=87;
rfl["LXXXVIII"]=88;
rfl["LXXXIX"]=89;
}
int getnum(char c)
{
if(c=='I') return 1;
else if(c=='V') return 5;
else if(c=='X') return 10;
else if(c=='L') return 50;
else assert(0);
}
bool Expression_Valid(string x)
{
int len=x.length();
if(!Is_Num(x[0]) || !Is_Num(x[len-1])) return false;
for(int i=0;i<len;){
if(!Is_Num(x[i])){
int j=i;
while(j<len && !Is_Num(x[j])) j++;
if(j-i>=2) return false;
i=j;
}else{
int j=i;
while(j<len && Is_Num(x[j])) j++;
if(rfl.find(x.substr(i,j-i))==rfl.end()) return false;
i=j;
}
}
return true;
}
stack<int > sta;
bool Equal_Valid(string x)
{
//it is build on the base of Expression_Valid
int len=x.length();
while(!sta.empty()) sta.pop();
int lef=0,rgh=0,cnt=0;
for(int i=0;i<len;)
{
if(x[i]=='-') {
int j=i+1;
while(j<len && Is_Num(x[j])) j++;
int tmp=rfl[x.substr(i+1,j-i-1)];
sta.push(-tmp);
i=j;
}else if(x[i]=='=') {
cnt++;
while(!sta.empty()) lef+=sta.top(),sta.pop();
i++;
}else if(x[i]=='+') {
int j=i+1;
while(j<len && Is_Num(x[j])) j++;
int tmp=rfl[x.substr(i+1,j-i-1)];
sta.push(tmp);
i=j;
}else{
int j=i;
while(j<len && Is_Num(x[j])) j++;
int tmp=rfl[x.substr(i,j-i)];
sta.push(tmp);
i=j;
}
}
while(!sta.empty()) rgh+=sta.top(),sta.pop();
return cnt==1 && lef==rgh;
}
void dfs(int hav,int op)
{
if(!hav && op)
{
if(Expression_Valid(ss) && Equal_Valid(ss)) res.insert(ss);
return;
}else if(!hav && !op){
string pre;pre=ss;
//remove
int len=ss.length();
string p1="",p2="";
for(int i=0;i<len;i++) {
if(ss[i]=='I' || ss[i]=='-'){
p1=ss.substr(0,i),p2=ss.substr(i+1,len-i-1);
p1+=p2;
ss=p1;
dfs(1,0);
ss=pre;
}
if(ss[i]=='L' || ss[i]=='+') {
ss[i]='I';
dfs(1,0);
ss=pre;
}
if(ss[i]=='+' || ss[i]=='=') {
ss[i]='-';
dfs(1,0);
ss=pre;
}
}
//change
for(int i=0;i<len;i++) {
if(ss[i]=='I') {
ss[i]='-',dfs(0,1),ss=pre;
}else if(ss[i]=='L') {
ss[i]='+',dfs(0,1),ss=pre;
}else if(ss[i]=='=') {
ss[i]='+',dfs(0,1),ss=pre;
}else if(ss[i]=='V') {
ss[i]='X',dfs(0,1),ss=pre;
}else if(ss[i]=='-') {
ss[i]='I',dfs(0,1),ss=pre;
}else if(ss[i]=='+') {
ss[i]='L',dfs(0,1),ss=pre;
ss[i]='=',dfs(0,1),ss=pre;
}else if(ss[i]=='X') {
ss[i]='V',dfs(0,1),ss=pre;
}
}
}else if(hav && !op) {
int len=ss.length();
string pre;pre=ss;
//add
for(int i=0;i<len;i++) {
if(ss[i]=='I') {
ss[i]='L',dfs(0,1),ss=pre;
ss[i]='+',dfs(0,1),ss=pre;
}else if(ss[i]=='-') {
ss[i]='=',dfs(0,1),ss=pre;
ss[i]='+',dfs(0,1),ss=pre;
}
}
//insert
for(int i=0;i<len;i++) {
ss.insert(ss.begin()+i,'I');
dfs(0,1);ss=pre;
ss.insert(ss.begin()+i,'-');
dfs(0,1);ss=pre;
}
ss.insert(ss.end(),'I');dfs(0,1);ss=pre;
}
}
int main()
{
Make_Table();
cin>>ss;ori=ss;
n=ss.length();
dfs(0,0);
for(set<string>::iterator ite=res.begin();ite!=res.end();++ite) cout<<*ite<<"\n";
return 0;
}