自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:30:58，当前版本为作者最后更新于2022-11-01 17:25:55，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题题意比较清楚，就不解释了。

先进行分析，题目已经告诉我们，$1 \le A \le B \le C$，所以可以分析出 $1 \le A \le B \le A+B,C \le A+C \le B+C \le A+B+C$，除了$A+B$ 和 $C$ 其它大小关系都是可以确定的。

我们把每一个进行二进制编号，$A$ 放在第一位，$B$ 放在第二位，$C$ 放在第三位，所以上述字母编号分别对应着 $1,2,3,4,5,6,7$，但其中 $3$ 和 $4$ 的大小关系无法确定。

所以只要枚举每个式子对应的数字，进行加减操作求解，注意只有互相包含的两个数字可以进行操作。

因为可能解出相同的解，注意最后要对解进行去重。

代码：

#include <bits/stdc++.h>
using namespace std;
template<typename T>inline void read(register T &x)
{
	register T p = 1,num = 0;
	char c = getchar();
	while(c < '0'||c > '9')
	{
		if(c == '-') p = -1;
		c = getchar();
	}
	while('0' <= c&&c <= '9')
	{
		num = (num<<3)+(num<<1)+(c^48);
		c = getchar();
	}
	x = p * num;
}
template<typename T>inline void write(register T x)
{
	if(x < 0) putchar('-'),x = -x;
	if(x > 9) write(x/10);
	putchar(x%10^48);
}
int a[10],b[10],num[10];
//1:A 2:B 3:A+B 4:C 5:A+C 6:B+C 7:A+B+C
int T,n,ans;
bitset<10> vis;
vector<int> g[10],h[10]; 
set<long long> pt;
void dfs(int u)
{
	if(u > n) 
	{
		memset(num,0,sizeof(num));
		for(int i = 1;i <= n;++i)  num[b[i]] = a[i];
		bool flag = 0;
		for(int o = 1;o <= 3;++o)
			for(int i = 1;i <= 7;++i)
			{
				for(auto j:g[i]) 
				{
					if(!num[j]||!num[i-j]) continue;
					if(num[i]&&num[i] != num[j] + num[i-j]) 
						return;	
					num[i] = num[j] + num[i-j];	
				}
				for(auto j:h[i])
				{
					if(!num[j]||!num[j-i]) continue;
					if(num[i]&&num[i] != num[j] - num[j-i]) 
						return;	
					num[i] = num[j] - num[j-i];	
				}
			}
		if(num[1] >= 1&&num[2] >= num[1]&&num[4] >= num[2]) pt.insert(114514ll*114514ll*num[1]+114514ll*num[2]+num[4]);
		return;
	}
	for(int i = 1;i <= 7;++i)
	{
		if(vis[i]) continue;
		b[u] = i;
		bitset<10> tp = vis;
		bool flag = 0;
		if(i == 4&&!vis[3]) flag = 1;
		for(int j = 1;j <= i;++j) vis[j] = 1;
		if(flag) vis[3] = 0;
		dfs(u+1);
		vis = tp; 
	}
}
int main()
{
	g[3].push_back(1),g[3].push_back(2);
	g[5].push_back(1),g[5].push_back(4);
	g[6].push_back(2),g[6].push_back(4);
	for(int i = 1;i <= 6;++i) g[7].push_back(i);
	h[1].push_back(3),h[1].push_back(5),h[1].push_back(7);
	h[2].push_back(3),h[2].push_back(6),h[2].push_back(7);
	h[3].push_back(7); 
	h[4].push_back(5),h[4].push_back(6),h[4].push_back(7);
	h[5].push_back(7);
	h[6].push_back(7);
	read(T);
	while(T--)
	{
		read(n);
		for(int i = 1;i <= n;++i) read(a[i]);
		sort(&a[1],&a[n+1]);
		vis = 0;
		pt.clear();
		dfs(1);
		write(pt.size());
		putchar('\n');
	}
	return 0;
}