下了#6数据,输入为3 4 5 6,输出为
⎩⎨⎧4−3=15−1=46∗4=24我的程序输出为
⎩⎨⎧5−4=11+3=46∗4=24想知道为什么错,看了题面好像没问题,但就是过不去。
以下是程序部分:
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#define ps(x) push_back(x)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define f first
#define s second
using namespace std;
const int MAXN=1005;
int a,b,c,d;
bool check=false;
int num[4],que[MAXN];
bitset<4> vis,arc[MAXN][50];
vector<char> ans[MAXN][50];
vector<pii> stk;
inline int read()
{
char x=getchar();int t=0;
while(!isdigit(x))x=getchar();
while(isdigit(x))t=(t<<3)+(t<<1)+(x^48),x=getchar();
return t;
}
bool cmp(int x,int y){return x>y;}
void putin(int x,int y,int val,int inv)
{
int cnt=++que[val];
if(x>10)ans[val][cnt].ps(x/10+'0');
ans[val][cnt].ps(x%10+'0');
char ch;
switch(inv){
case 1:ch='+';break;
case 2:ch='-';break;
case 3:ch='*';break;
case 4:ch='/';break;
}
ans[val][cnt].ps(ch);
ans[val][cnt].ps(y+'0');
ans[val][cnt].ps('=');
if(val>10)ans[val][cnt].ps(val/10+'0');
ans[val][cnt].ps(val%10+'0');
ans[val][cnt].ps('\n');
// printf("%d%c%d=%d\n",x,ch,y,val);
}//原有数两两运算
void putin2(int x,int y,int val,int inv,int last)
{
int cnt=++que[val];
ans[val][cnt]=ans[x][last];
if(x>10)ans[val][cnt].ps(x/10+'0');
ans[val][cnt].ps(x%10+'0');
char ch;
switch(inv){
case 1:ch='+';break;
case 2:ch='-';break;
case 3:ch='*';break;
case 4:ch='/';break;
}
ans[val][cnt].ps(ch);
ans[val][cnt].ps(y+'0');
ans[val][cnt].ps('=');
if(val>10)ans[val][cnt].ps(val/10+'0');
ans[val][cnt].ps(val%10+'0');
ans[val][cnt].ps('\n');
}//处理后的结果与原有数运算
void update(int x,int y,int val)
{
int cnt=que[val];
arc[val][cnt].reset();
arc[val][cnt]|=(1<<x);
arc[val][cnt]|=(1<<y);
stk.push_back(mp(val,cnt));
}//处理使用过的数
void print(int x,int y,int dx,int dy,char inv)
{
for(auto ch:ans[x][dx])printf("%c",ch);
for(auto ch:ans[y][dy])printf("%c",ch);
printf("%d%c%d=24\n",max(x,y),inv,min(x,y));
}//输出的结果
bool get_ans(int x,int y,char inv)
{
for(int i=1;i<=que[x]&&!check;++i)
{
for(int j=1;j<=que[y]&&!check;++j)
{
if((arc[x][i]^arc[y][j]).all())
{
print(x,y,i,j,inv);
return check=true;
}
}
}
return false;
}//查找哪两个能够组合起来
int main()
{
for(int i=0;i<4;++i)num[i]=read();
sort(num,num+4,cmp);
for(int i=0;i<4;++i)
{
arc[num[i]][++que[num[i]]]=(1<<i);
for(int j=i+1;j<4;++j)
{
int x=num[i],y=num[j];
putin(x,y,x+y,1);update(i,j,x+y);
putin(x,y,x-y,2);update(i,j,x-y);
putin(x,y,x*y,3);update(i,j,x*y);
if(x%y==0)putin(x,y,x/y,4),update(i,j,x/y);
}
}
for(int i=0;i<stk.size();++i)
{
for(int j=0;j<4;++j)
{
int x1=stk[i].f,x2=stk[i].s;
if(arc[x1][x2][j])continue;
int x=stk[i].f,y=num[j];
int z;
putin2(x,y,x+y,1,x2);
//x+y
z=que[x+y];
arc[x+y][z]=arc[x1][x2];
arc[x+y][z]|=(1<<j);
//x-y
if(x>y)
{
putin2(x,y,x-y,2,x2);z=que[x-y];
arc[x-y][z]=arc[x1][x2];
arc[x-y][z]|=(1<<j);
}
//x*y
putin2(x,y,x*y,3,x2);z=que[x*y];
arc[x*y][z]=arc[x1][x2];
arc[x*y][z]|=(1<<j);
//x/y
if(x%y==0)
{
putin2(x,y,x/y,4,x2);z=que[x/y];
arc[x/y][z]=arc[x1][x2];
arc[x/y][z]|=(1<<j);
}
}
}
for(int i=0;i<=12&&!check;++i)
if(get_ans(i,24-i,'+'))break;
//x-y
for(int i=24;i<=105&&!check;++i)
if(get_ans(i,i-24,'-'))break;
//x*y
for(int i=1;i<=12&&!check;++i)
if(24%i==0)
if(get_ans(i,24/i,'*'))break;
//x/y
for(int i=1;i<=81&&!check;++i)
if(get_ans(i*24,i,'/'))break;
if(!check)puts("No answer!");
return 0;
}