题目描述
毒瘤模拟。。写吐了。。
算法
(暴力枚举)
首先这题还不能太暴力，不能直接爆搜等式中所有的数字，然后找它能变成那些数字，会TLE
处理方法：先在字符串中找到=和#，分别处理等号两边的值，然后分别处理
- 只改左边，看能不能等于右边
- 只改右边，看能不能等于左边
- 在左边改一个，在右边改一个，能不能改成相等的
就是这个分治让此题变得毒瘤了起来。。
C++ 代码及注释
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack> // 栈用于计算表达式的值
using namespace std;
const bool Gturn[10][10]= // 记录数字 a 是否能通过只修改一根木棒变成 b
{
// 0 1 2 3 4 5 6 7 8 9
{0,0,0,0,0,0,1,0,0,1}, // 0
{0,0,0,0,0,0,0,0,0,0}, // 1
{0,0,0,1,0,1,0,0,0,0}, // 2
{0,0,1,0,0,1,0,0,0,0}, // 3
{0,0,0,0,0,0,0,0,0,0}, // 4
{0,0,1,1,0,0,0,0,0,0}, // 5
{1,0,0,0,0,0,0,0,0,1}, // 6
{0,0,0,0,0,0,0,0,0,0}, // 7
{0,0,0,0,0,0,0,0,0,0}, // 8
{1,0,0,0,0,0,1,0,0,0} // 9
};
const bool Gadd[11][11]= // 记录数字 a 是否能通过只增加一根木棒变成 b
{
// 0 1 2 3 4 5 6 7 8 9
{0,0,0,0,0,0,0,0,1,0}, // 0
{0,0,0,0,0,0,0,1,0,0}, // 1
{0,0,0,0,0,0,0,0,0,0}, // 2
{0,0,0,0,0,0,0,0,0,1}, // 3
{0,0,0,0,0,0,0,0,0,0}, // 4
{0,0,0,0,0,0,1,0,0,1}, // 5
{0,0,0,0,0,0,0,0,1,0}, // 6
{0,0,0,0,0,0,0,0,0,0}, // 7
{0,0,0,0,0,0,0,0,0,0}, // 8
{0,0,0,0,0,0,0,0,1,0} // 9
};
string str; // 存输入的字符串
string l,r; // 分别存左边的等式和右边的等式
int pos,pos_end; // pos 存等号的位置，pos_end 存井号的位置
void calc(stack<int> &nums,stack<char> &ops) // 将 nums 的栈顶两个元素做 ops.top() 操作
{
char op=ops.top();ops.pop(); // 将 ops.top() 取出
if(nums.size()<2)return; // 如果 nums 中不足两个数，那么不做处理，直接返回
int a=nums.top();nums.pop(); // 将 nums 的栈顶两个元素取出
int b=nums.top();nums.pop();
if(op=='-')nums.push(b-a); // 如果 ops.top() 操作是减，那么将 b - a 的结果存入 nums 中
else nums.push(a+b); // 否则说明 ops.top() 操作是加，那么将 b + a 的结果存入 nums 中
}
int get_num(string str) // 求出字符串表达式 str 的值
{
stack<int> nums; // 存 str 中的数字
stack<char> ops; // 存 str 中的操作符
for(int i=0;i<str.size();i++)
{
if(str[i]>47&&str[i]<58) // 如果 str[i] 是数字（48 是 '0' 的 ASCII 码，57 是 '9' 的 ASCII 码）
{
int j=i,t=0; // 计算该位数字，加入 nums 中。并将 i 跳到该位数字末端
while(j<str.size()&&str[j]>47&&str[j]<58)t=t*10+(str[j++]^48);
nums.push(t),i=j-1;
}
else if(str[i]=='+') // 如果 str[i] 是加号，
{
while(ops.size())calc(nums,ops); // 那么要计算其前面表达式的值，
ops.push(str[i]); // 并将加号存入 ops 中
}
// 否则说明是 '-'，分两种情况。1. str[i] 是负号 2. str[i] 是减号
else if(i&&!(str[i-1]>47&&str[i-1]<58)) // 如果 '-' 前面不是数字，那么说明是负号
{
int j=i+1,t=0; // 计算其后面数字的值，将其相反数加入 nums 中。并将 i 跳到该位数字末端
while(j<str.size()&&str[j]>47&&str[j]<58)t=t*10+(str[j++]^48);
nums.push(-t),i=j-1;
}
else // 否则说明是减号，计算其前面表达式的值，并将减号存入 ops
{
while(ops.size())calc(nums,ops);
ops.push(str[i]);
}
}
while(ops.size())calc(nums,ops); // 如果 ops 中还有剩余，说明表达式未计算完。
return nums.top(); // nums 中所剩下的唯一元素即为该表达式的值
}
bool to(string &str,int num) // 检查 str 的值能否变为 num
{
string l=str; // 将 str 复制到 l 中
for(int i=0;i<l.size();i++) // 枚举每一位
if(l[i]>47&&l[i]<58) // 如果该位是数字
for(int j=0;j<10;j++)// 那么枚举 0 ~ 9 十个数字
if(Gturn[l[i]^48][j]) // 若该位能变成 j，
{
char tmp=l[i];
l[i]=j^48; // 那么将其该位 j
if(get_num(l)==num) // 并计算改完之后的值是否为 num
{
str=l; // 如果是，那么将 str 该为 l，并返回 true
return true;
}
l[i]=tmp; // 否则将该位改回来，继续枚举其它方案
}
for(int i=0;i<l.size();i++) // 枚举每两位
if(l[i]>47&&l[i]<58)
for(int j=i+1;j<l.size();j++)
if(l[j]>47&&l[j]<58)
{
// 处理将 l[i] 与 l[j] 上的一根木棒互换的情况
if(Gadd[l[i]^48][l[j]^48]||Gadd[l[j]^48][l[i]^48]) // 如果说 l[i] 能通过加一根木棍变为 l[j] 且 l[j] 能通过减一根木棒变成 l[i]，说可以通过只移动一根木棒将 l[i] 和 l[j] 互换
{
char tmp=l[i]; // 那么将这两位互换
l[i]=l[j];
l[j]=tmp;
if(get_num(l)==num) // 如果表达式的值为 num，那么将 str 改为 l，返回 true
{
str=l;
return true;
}
l[j]=l[i]; // 否则换回来，继续枚举其它方案
l[i]=tmp;
}
// 处理将 l[j] 中的一根木棒移到 l[i] 上的情况
for(int k=0;k<10;k++) // 枚举 k 和 u
for(int u=0;u<10;u++)
if(Gadd[l[i]^48][k]&&Gadd[u][l[j]^48]) // 如果 l[i] 能通过加一根木棒变成 k，且 l[j] 能通过减一根木棒变成 u
{
char tl=l[i],tr=l[j]; // 那么执行该操作
l[i]=k^48,l[j]=u^48;
if(get_num(l)==num) // 如果执行完后，表达式 l 的值等于 num，
{
str=l; // 那么将 str 该位 l，返回 true
return true;
}
l[i]=tl,l[j]=tr; // 否则改回来，继续枚举其它方案
}
else if(Gadd[l[j]^48][k]&&Gadd[u][l[i]^48]) // 同上，将 l[i] 和 l[j] 反着做一遍
{
char tl=l[i],tr=l[j];
l[i]=u^48,l[j]=k^48;
if(get_num(l)==num)
{
str=l;
return true;
}
l[i]=tl,l[j]=tr;
}
}
return false; // 如果都枚举完了，还没有找到一组合法方案，那么返回 false
}
bool str_turn(string &left,string &right) // 处理将 left 和 right 中移动一根木棒的情况
{
string l=left,r=right;
for(int i=0;i<l.size();i++) // 枚举 left 的每一位
if(l[i]>47&&l[i]<58) // 如果该位是数字
for(int j=0;j<r.size();j++) // 那么枚举 right 的每一位
if(r[j]>47&&r[j]<58) // 如果该位是数字
{
if(Gadd[r[j]^48][l[i]^48]||Gadd[l[i]^48][r[j]^48]) // 那么和上面的 枚举两位 的情况一样，这里不再注释了。。累死了。。
{
char tmp=l[i];
l[i]=r[j];
r[j]=tmp;
if(get_num(l)==get_num(r))
{
left=l,right=r;
return true;
}
r[j]=l[i];
l[i]=tmp;
}
for(int k=0;k<10;k++)
for(int u=0;u<10;u++)
if(Gadd[l[i]^48][k]&&Gadd[u][r[j]^48])
{
char tl=l[i],tr=r[j];
l[i]=k^48,r[j]=u^48;
if(get_num(l)==get_num(r))
{
left=l,right=r;
return true;
}
l[i]=tl,r[j]=tr;
}
}
return false; // 没找到合法情况，返回 false
}
int main()
{
cin>>str;
for(int i=0;i<str.size();i++) // 枚举 str 的每一位
if(str[i]=='=')pos=i; // 如果该位为等号，让 pos 指向该位
else if(str[i]=='#')pos_end=i; // 如果该位为井号，让 end_pos 指向该位
l=str.substr(0,pos); // 找到等式左边
r=str.substr(pos+1,pos_end-pos-1); // 找到等式右边
int num_l=get_num(l),num_r=get_num(r); // 分别计算左边和右边的值
if(to(l,num_r))cout<<l<<'='<<r<<'#'; // 如果 l 能变成 num_r，那么输出该方案
else if(to(r,num_l))cout<<l<<'='<<r<<'#'; // 否则如果 r 能变成 num_l，那么输出该方案
else if(str_turn(l,r))cout<<l<<'='<<r<<'#'; // 否则如果 l 和 r 中移动一根木棒能让等式成立，那么输出该方案
else puts("No"); // 否则输出 No
return 0;
}
好不容易写完这两百行的代码了。。交上去一看，诶，咋还TLE了呢。。
当场心态就崩了。。
仔细看下是哪的问题，注意到每次get_num是 $\mathcal O(n)$ 的，而每次改一个数字都会被调用一次，引起的超时。
由于我们每次只会改一个数字，那么只要在求好的num中将原数减去，然后加上所改的值即可。详见代码及注释。
C++ 代码及注释
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;
typedef long long ll;
const bool Gturn[10][10]=
{
// 0 1 2 3 4 5 6 7 8 9
{0,0,0,0,0,0,1,0,0,1}, // 0
{0,0,0,0,0,0,0,0,0,0}, // 1
{0,0,0,1,0,1,0,0,0,0}, // 2
{0,0,1,0,0,1,0,0,0,0}, // 3
{0,0,0,0,0,0,0,0,0,0}, // 4
{0,0,1,1,0,0,0,0,0,0}, // 5
{1,0,0,0,0,0,0,0,0,1}, // 6
{0,0,0,0,0,0,0,0,0,0}, // 7
{0,0,0,0,0,0,0,0,0,0}, // 8
{1,0,0,0,0,0,1,0,0,0} // 9
};
const bool Gadd[11][11]=
{
// 0 1 2 3 4 5 6 7 8 9
{0,0,0,0,0,0,0,0,1,0}, // 0
{0,0,0,0,0,0,0,1,0,0}, // 1
{0,0,0,0,0,0,0,0,0,0}, // 2
{0,0,0,0,0,0,0,0,0,1}, // 3
{0,0,0,0,0,0,0,0,0,0}, // 4
{0,0,0,0,0,0,1,0,0,1}, // 5
{0,0,0,0,0,0,0,0,1,0}, // 6
{0,0,0,0,0,0,0,0,0,0}, // 7
{0,0,0,0,0,0,0,0,0,0}, // 8
{0,0,0,0,0,0,0,0,1,0} // 9
};
string str;
string l,r;
int pos,pos_end;
vector<int> head[10]; // 预处理一下每个数能变成的数，存在 head 里面，访问的时候更快。
bool getv(string &str,int p)
{
while(p&&str[--p]>47&&str[p]<58);
return str[p]=='-';
}
void calc(stack<ll> &nums,stack<char> &ops)
{
char op=ops.top();ops.pop();
if(nums.size()<2)return;
ll a=nums.top();nums.pop();
ll b=nums.top();nums.pop();
if(op=='-')nums.push(b-a);
else nums.push(a+b);
}
ll get_num(string &str)
{
stack<ll> nums;
stack<char> ops;
for(int i=0;i<str.size();i++)
{
if(str[i]>47&&str[i]<58)
{
ll j=i,t=0;
while(j<str.size()&&str[j]>47&&str[j]<58)t=t*10+(str[j++]^48);
nums.push(t),i=j-1;
}
else if(str[i]=='+')
{
while(ops.size())calc(nums,ops);
ops.push(str[i]);
}
else if(i&&!(str[i-1]>47&&str[i-1]<58))
{
ll j=i+1,t=0;
while(j<str.size()&&str[j]>47&&str[j]<58)t=t*10+(str[j++]^48);
nums.push(-t),i=j-1;
}
else
{
while(ops.size())calc(nums,ops);
ops.push(str[i]);
}
}
while(ops.size())calc(nums,ops);
return nums.top();
}
bool to(string &str,ll num_str,ll num)
{
string l=str;
for(int i=0;i<l.size();i++)
if(l[i]>47&&l[i]<58)
for(int j=0;j<10;j++)
if(Gturn[l[i]^48][j])
{
char tmp=l[i];
l[i]=j^48;
if(get_num(l)==num)
{
str=l;
return true;
}
l[i]=tmp;
}
for(int i=0;i<l.size();i++)
if(l[i]>47&&l[i]<58)
for(int j=0;j<l.size();j++)
if(l[j]>47&&l[j]<58)
{
if(i<j&&(Gadd[l[i]^48][l[j]^48]||Gadd[l[j]^48][l[i]^48]))
{
char tmp=l[i];
l[i]=l[j];
l[j]=tmp;
if(get_num(l)==num)
{
str=l;
return true;
}
l[j]=l[i];
l[i]=tmp;
}
for(int k=0;k<head[l[i]^48].size();k++)
for(int u=0;u<10;u++)
if(Gadd[u][l[j]^48])
{
int p=i;
ll t1=head[l[i]^48][k],t2=u; // 取出改的数字
ll r1=l[i]^48,r2=l[j]^48; // 取出原数
while(p<l.size()&&l[++p]>47&&l[p]<58)r1*=10,t1*=10; // 计算表达式中原数
t1-=r1; // 计算增加的结果
if(getv(str,p-1))t1=-t1; // 如果前面的符号是负号，那么该数要转成负的
p=j;
while(p<l.size()&&l[++p]>47&&l[p]<58)r2*=10,t2*=10; // 计算原数
t2-=r2; // 同上
if(getv(str,p-1))t2=-t2;
if(num_str+t1+t2==num) // 如果改完后正好是 num，那么返回 true
{
l[i]=head[l[i]^48][k]^48,l[j]=u^48;
str=l;
return true;
}
}
}
return false;
}
bool str_turn(string &left,ll num_l,string &right,ll num_r)
{
string l=left,r=right;
for(int i=0;i<l.size();i++)
if(l[i]>47&&l[i]<58)
for(int j=0;j<r.size();j++)
if(r[j]>47&&r[j]<58)
{
if(Gadd[r[j]^48][l[i]^48]||Gadd[l[i]^48][r[j]^48])
{
char tmp=l[i];
l[i]=r[j];
r[j]=tmp;
if(get_num(l)==get_num(r))
{
left=l,right=r;
return true;
}
r[j]=l[i];
l[i]=tmp;
}
for(int k=0;k<head[l[i]^48].size();k++) // 同上述注释部分
for(int u=0;u<10;u++)
if(Gadd[u][r[j]^48])
{
int p=i;
ll t1=head[l[i]^48][k],t2=u;
ll r1=l[i]^48,r2=r[j]^48;
while(p<l.size()&&l[++p]>47&&l[p]<58)r1*=10,t1*=10;
t1-=r1;
if(getv(l,p-1))t1=-t1;
p=j;
while(p<r.size()&&r[++p]>47&&r[p]<58)r2*=10,t2*=10;
t2-=r2;
if(getv(r,p-1))t2=-t2;
if(num_l+t1==num_r+t2)
{
l[i]=head[l[i]^48][k]^48,r[j]=u^48;
left=l,right=r;
return true;
}
}
}
return false;
}
int main()
{
for(int i=0;i<10;i++) // 预处理 head
for(int j=0;j<10;j++)
if(Gadd[i][j])
head[i].push_back(j);
cin>>str;
for(int i=0;i<str.size();i++)
if(str[i]=='=')pos=i;
else if(str[i]=='#')pos_end=i;
l=str.substr(0,pos),r=str.substr(pos+1,pos_end-pos-1);
ll num_l=get_num(l),num_r=get_num(r);
if(to(l,num_l,num_r))cout<<l<<'='<<r<<'#';
else if(to(r,num_r,num_l))cout<<l<<'='<<r<<'#';
else if(str_turn(l,num_l,r,num_r))cout<<l<<'='<<r<<'#';
else puts("No");
return 0;
}
emmm以前的题解都是写一大堆文字，然后代码没几行，题解一共也就200行左右。。
这回这次贴一份代码就200行了。。
emmmmm,我好像发现了第二个bug，就是你在让一个数字多一根一个数字少一根的时候，你的代码写法要求了前面的数字也就是i那个必须是增加，j的为减少，我测试了0+7=9#是ok的，但是7+0=9#输出了No
$fixed.$
你好，我似乎发现你这个代码好像有bug，我测试了下-1+1=0#的输入结果输出了No，原因好像出自你get_num那里判断为负号而不是减号的地方，当-在第一位时i=0
-1+1=0不应该输出No嘛？不然怎么移木棒嘞？是我理解错啦，不好意思，大佬
#
tql比200行更爽的当然就是再来一遍$\underline{手打}$$为什么这题挑战模式时间限制只有五分钟啊。。卡的太紧了吧。。$
$换y总五分钟应该是可以写完两百行的，但是一般人应该都做不到吧。。$
$还是说是只有我太菜了，其它所有人都能五分钟写完两百行鸭$
tql