24点

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 492K, 提交时间: 2018-07-20 21:01:30

#include<bits/stdc++.h>
using namespace std;

template <typename T> void chmin(T &x,const T &y)
{
	if(x>y)x=y;
}
#define rep(i,l,r) for(int i=l;i<=r;++i)
const int inf=10000;

int niv_num(int q0[4])
{
	static int q[4];
	rep(i,0,3)q[i]=q0[i];
	int ans=0;
	rep(i,0,3)
	rep(j,0,2)
	if(q[j]>q[j+1]){++ans;swap(q[j],q[j+1]);}
	return ans;
}
int a[4],b[3],c[3],ans;
int F(int t,int a,int b)
{
	t=::b[t];
	if(t==0)return a+b;
	if(t==1)return a^b;
	return (t==2)?(a|b):(a&b);
}
int F021()
{
	return F(1,F(0,a[0],a[1]),F(2,a[2],a[3]));
}
int F012()
{
	return F(2,F(1,F(0,a[0],a[1]),a[2]),a[3]);
}
int F102()
{
	return F(2,F(0,a[0],F(1,a[1],a[2])),a[3]);
}
int F120()
{
	return F(0,a[0],F(2,F(1,a[1],a[2]),a[3]));
}
int F201()
{
	return F021();
}
int F210()
{
	return F(0,a[0],F(1,a[1],F(2,a[2],a[3])));
}
int check0()
{
	if(c[0]<c[1]&&c[1]<c[2])return F012();
	if(c[0]<c[2]&&c[2]<c[1])return F021();
	if(c[1]<c[0]&&c[0]<c[2])return F102();
	if(c[1]<c[2]&&c[2]<c[0])return F120();
	if(c[1]<c[0])return F210();
	return F201();
}
int C(int x)
{
	return (x!=24)*inf;
}
//int base;
void check()
{
	rep(i,0,2)c[i]=-(b[i]&2)*inf+i; 
	chmin(ans,C(check0()));
//	if(base==2&&ans==0)
//		int tmp=1;
	chmin(ans,1+C(c[1]<c[2]?F012():F021()));
	chmin(ans,2+C(F021()));
	chmin(ans,2+C(F012()));
	chmin(ans,1+C(c[0]<c[2]?F102():F120()));
	chmin(ans,2+C(F102()));
	chmin(ans,2+C(F120()));
	chmin(ans,1+C(c[0]<c[1]?F201():F210()));
	chmin(ans,2+C(F210()));
	chmin(ans,1+C(c[0]<c[1]?F012():F102()));
	chmin(ans,1+C(c[1]<c[2]?F120():F210()));
}
void dfs(int x)
{
	if(x==3){check();return ;}
	rep(i,0,3){b[x]=i;dfs(x+1);}
}
int min_cost()
{
	ans=inf;
	dfs(0);
	return ans;	
}

int main()
{
	//freopen("1.in","r",stdin);
	int a[4],q[4];
	rep(i,0,3)cin>>a[i];
	rep(i,0,3)q[i]=i;
	int ans=inf;
	do
	{
		rep(i,0,3)::a[i]=a[q[i]];
		//base=niv_num(q);
		chmin(ans,2*niv_num(q)+min_cost());
	/*	if(ans==2)
		{
			rep(i,0,3)cerr<<::a[i]<<" ";cerr<<endl;
		}*/
	}while(next_permutation(q,q+4));
	if(ans==inf)puts("impossible");
	else cout<<ans;
}

C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 488K, 提交时间: 2018-07-20 21:21:44

#include<bits/stdc++.h>
#define maxn 12345

using namespace std;
int a[4],b[3],d,c[4],ans,r,k,t[4],o[3],ow[3],rt;

int calc(int x,int y,int op){
    if (op==0) return x+y;
    else if (op==1) return x^y;
    else if (op==2) return x|y;
    else return x&y;
}

int main(){
    for (int i=0;i<4;i++) cin >> a[i]; ans=1000;
    for (int i=0;i<4;i++) c[i]=i;
    do{
        rt=0; for (int i=0;i<4;i++) for (int j=i+1;j<4;j++) if (c[i]>c[j]) rt++;
        for (int i=1;i<=3;i++) for (int j=1;j<=2;j++){
            if (i==1&&j==1) b[0]=1,b[1]=2,b[2]=3;
            if (i==1&&j==2) b[0]=1,b[1]=3,b[2]=2;
            if (i==2&&j==1) b[0]=2,b[1]=1,b[2]=3;
            if (i==2&&j==2) b[0]=2,b[1]=3,b[2]=1;
            if (i==3&&j==1) b[0]=3,b[1]=1,b[2]=2;
            if (i==3&&j==2) b[0]=3,b[1]=2,b[2]=1;
            for (int k=0;k<64;k++){
                int tmp=k;
                for (int w=0;w<3;w++) o[w]=tmp%4,ow[w]=o[w]/2,tmp/=4;
                r=0; for (int w=0;w<4;w++) t[w]=a[c[w]];
                for (int w=0;w<3;w++){
                    bool flag=false;
                    for (int v=w+1;v<3;v++) if ((b[v]>b[w]&&ow[w]<ow[v])||(b[v]<b[w]&&ow[w]<=ow[v])) flag=true;
                    if (flag) r++;
                }
                if (i==2&&j==2&&!ow[0]&&!ow[1]&&ow[2]) r--;
                if (i==1&&j==1&&!ow[0]&&!ow[1]&&ow[2]) r--;
                for (int w=0;w<3;w++){
                    int tmp;
                    if (w==0) tmp=i; else if (w==1) tmp=j; else tmp=1;
                    t[tmp-1]=calc(t[tmp-1],t[tmp],o[w]);
                    for (int v=tmp;v<4-w;v++) t[v]=t[v+1];
                }
                if (t[0]==24) {
                    ans=min(ans,r+rt*2);
                }
            }
        }
    }while (next_permutation(c,c+4));
    if (ans==1000) cout << "impossible" << endl; else cout << ans << endl;
    return 0;
}

详情