P7556 题解
Wangxun
·
·
题解
这题题意比较清楚，就不解释了。
先进行分析，题目已经告诉我们，1 \le A \le B \le C，所以可以分析出
我们把每一个进行二进制编号，$A$ 放在第一位，$B$ 放在第二位，$C$ 放在第三位，所以上述字母编号分别对应着 $1,2,3,4,5,6,7$，**但其中 $3$ 和 $4$ 的大小关系无法确定**。
所以只要枚举每个式子对应的数字，进行加减操作求解，注意只有互相包含的两个数字可以进行操作。
因为可能解出相同的解，注意最后要对解进行**去重**。
代码：
```cpp
#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;
}
```