【ACGO巅峰赛#19】T6 24点题解

这题其实就类似于算24点，做法很多，这里提供一种几乎不用动脑子的做法（？

首先我们将4个数形成一个列表，比如样例的 $(1,2,3,4)$。接着我们枚举任意两个数，对这两个数进行加/减/乘/除/反向加/反向减的操作，并将操作后的数放在两个数的任意一个，另外一个数置为 $-1$ 表示此位置已经没有数。比如我们选的这两个数是 $1,3$，那么进行这六种操作后分别为 $1+3,1-3,1\times 3,1/3,3-1,3/1$，若我们选择 $1+3(=4)$，则操作后的列表为 $(4,2,-1,4)$。接着递归处理（即回溯dfs）这个数列，直到列表中只剩下一个数时，我们检查这个数是否是 $24$ 的倍数即可。

那么假如我们发现最后的数满足条件，如何根据此生成一个符合的表达式呢？我们只需记录每一步操作的两个数的位置编号以及操作编号 ($1,2,3,4,5,6$ 分别代表 加/减/乘/除/反向减/反向除)，接着倒序递归输出即可。如果当前的这个编号的数是原序列中的（即之前没有操作过这个编号的数），那么直接输出之即可。否则需要递归到上一次处理的位置重复这个操作。比如，拿 $(1,2,3,4)$ 来说，假设我们记录的位置编号及操作编号分别为：

	操作数1	操作数2	操作编号
$1$	$1$	$2$	$1(+)$
$2$	$3$	$4$	$3(\times)$
$3$	$1$	$3$	$3(\times)$

那么我们先考虑最后一行。发现第一个操作数 $1$ 不是原始序列的数，因为第一行操作又用到了 $1$，所以先加个左括号，之后递归考虑第一行，发现第一行使用的编号 $1$ 的数确实是原始序列的，编号 $2$ 的数也是。因此直接输出原始数 $1+2$ 即可。此处递归结束后接着加入右括号，即变成 $(1+2)$。

第一个数考虑完后在中间加入运算符号 $\times$。同理继续考虑第二个操作数 $3$，发现他也在第二行出现过，不是原始数。于是递归考虑第二行，得 $(3 \times 4)$。

于是最终结果 $(1+2) \times (3 \times 4)$，这个不是 $24$ 的倍数，只是为了展示递归输出的机理。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5+10;
int n,m;
int a,b,c,d;
int num[6];
int bf[6];
int ans[5];
int c1[N],c2[N];
char tab[7] = {'0','+','-','*','/','-','/'}; //1,2,3,4分别代表加减乘除，5,6分别代表反向减和反向除 
bool flag = 0;
vector<int> vec[5];

inline int cal(int x,int y,int mode){ //
	if(mode==1) return x+y;
	if(mode==2) return x-y;
	if(mode==3) return x*y;
	if(mode==4){
		if(y==0) return -2;
		if(x%y) return -2;
		return x/y;
	}
}

inline void dfs(int dth,int tmp[]){
	if(dth==4){
		if(tmp[1]%24==0){ // 每次都把操作后的数放在小的那项上，不难证明最终剩下的那个数一定在第一项 
			flag = 1;
		}
		return;
	}
	for(int i=1;i<=4;i++){
		if(tmp[i]==-1) continue; // -1代表没有数 
		for(int j=i+1;j<=4;j++){
			if(tmp[j]==-1) continue;
			c1[dth] = i,c2[dth] = j;
			int temp = tmp[i],t2 = tmp[j];
			tmp[j] = -1;
			for(int k=1;k<=4;k++){ // 先处理正向加减乘除 
				tmp[i] = cal(temp,t2,k);
				ans[dth] = k;
				if(tmp[i]!=-2) dfs(dth+1,tmp);
				if(flag) return;
			}
			tmp[i] = cal(t2,temp,2); // 后处理逆向减和除 
			ans[dth] = 5;
			if(tmp[i]!=-2) dfs(dth+1,tmp);
			if(flag) return;
			tmp[i] = cal(t2,temp,4);
			ans[dth] = 6;
			if(tmp[i]!=-2) dfs(dth+1,tmp);
			if(flag) return;
			
			tmp[i] = temp;
			tmp[j] = t2; // 回溯 
		}
	}
}
inline void print(int dth){ // 倒序考虑最终的数 形式为 c1[dth] op c2[dth]，如果其中某个不是原始数（即一开始给的数），那么递归得到原始数。 
	if(dth==0) return;
	int op = ans[dth];
	char s = tab[op];
	if(op>=5) swap(c1[dth],c2[dth]);
	bool ifind = 0;
	for(int i=dth-1;i;i--){
		if(c1[i]==c1[dth]){
			cout<<'(';print(i);cout<<')';
			ifind = 1;
			break;
		}
	}
	if(!ifind){
		cout<<bf[c1[dth]];
	}
	cout<<s;
	
	ifind = 0;
	for(int i=dth-1;i;i--){
		if(c2[dth]==c1[i]){
			cout<<'(';print(i);cout<<')';
			ifind = 1;
			break;
		}
	}
	if(!ifind){
		cout<<bf[c2[dth]];
	}
	
}

signed main(){
	ios::sync_with_stdio(false);
	cin>>n;
	int idx = 0;
	for(int i=1;i<=n;i++){
		flag = 0;
		cin>>num[1]>>num[2]>>num[3]>>num[4];
		for(int j=1;j<=4;j++){
			bf[j] = num[j];
		}
		dfs(1,num);
		if(!flag){
			cout<<"Impossible\n";
			continue;
		}
		print(3);
		cout<<endl;
	}
	
	return 0;
}