WA#6#11,测数据像是对的
查看原帖
WA#6#11,测数据像是对的
353893
彭俊皓123楼主2023/7/23 20:01

下了#6数据,输入为3 4 5 6,输出为

{4−3=15−1=46∗4=24\begin{cases} 4-3=1\\ 5-1=4\\ 6\ast4=24 \end{cases}

我的程序输出为

{5−4=11+3=46∗4=24\begin{cases} 5-4=1\\ 1+3=4\\ 6\ast4=24 \end{cases}

想知道为什么错,看了题面好像没问题,但就是过不去。

以下是程序部分:

#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;
}
2023/7/23 20:01
加载中...