Do You Know Your ABCs? (USACO Silver 2021 Open)

Do You Know Your ABCs? (USACO Silver 2021 Open)

这也是个算法简单，但实现细节比较多的题目。

根据条件，大部分顺序可以排出来：

1≤A≤B≤C or A+B≤A+C≤B+C≤A+B+C1 \leq A \leq B \leq C \text{ or } A+B \leq A+C \leq B+C \leq A+B+C

所以只有CC和A+BA+B的顺序无法确定，其它所有值的顺序都是固定的。有了这个结论之后，我们的做法，就是按顺序要求生成所有可能的方程（7个元素选NN个，这个生成办法可以用bit mask枚举）。

对于得到的方程组，通过“迭代推导”这样的方式，可以有一个相对通用简洁的求解办法。我们需要仔细检查，保证不漏掉能解出来的情况。这个比更通用的高期消元法要简单，但是需要小心操作顺序保证不漏掉解。

最后我们将结果再代回原来所有方程中演算，如果成立，就将这个解加入结果集合，最后打印解的数量。

注意，A,B,CA,B,C最大是10910^9，所以A+B+CA+B+C会越int界，需要用long long。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int t,n;
ll x[10];
 
set<pair<ll, pair<ll, ll>>> ans;    // A,B,C
 
// v[i]: A,B,C,A+B,A+C,B+C,A+B+C 的值
//       如果是0，表示对应方程不存在
void solve(vector<ll> v) {
    ll a = v[0], b = v[1], c = v[2];
    ll ab = v[3], ac = v[4], bc = v[5];
    ll abc = v[6];
    if (a && b) ab = a + b;     // 迭代推导求a,b,c
    if (a && c) ac = a + c;
    if (b && c) bc = b + c;
    if (a && ab) b = ab - a;
    if (a && ac) c = ac - a;
    if (b && ab) a = ab - b;
    if (b && bc) c = bc - b;
    if (c && ac) a = ac - c;
    if (c && bc) b = bc - c;
    if (ab && ac && bc) abc = (ab + bc + ac) / 2;
    if (abc && ab) c = abc - ab;
    if (abc && ac) b = abc - ac;
    if (abc && bc) a = abc - bc;
 
    if (!(a >= 1 && b >= a && c >= b)) return;
    if (v[0] && a != v[0]) return;    // 下面检查a,b,c是否正确
    if (v[1] && b != v[1]) return;
    if (v[2] && c != v[2]) return;
    if (v[3] && a + b != v[3]) return;
    if (v[4] && a + c != v[4]) return;
    if (v[5] && b + c != v[5]) return;
    if (v[6] && a + b + c != v[6]) return;
    ans.insert({a, {b, c}});
}
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &x[i]);
        }
        sort(x, x+n);
        ans.clear();
        for (int i = 0; i < (1 << 7); i++) {  // 枚举所有可能的子集位置
            if (__builtin_popcount(i) != n) continue;
            int k = 0;
            vector<ll> v(7, 0LL);
            for (int j = 0; j < 7; j++)
                if (i & (1 << j))
                    v[j] = x[k++];
            solve(v);               // 情况1: A,B,C,A+B,...
            if (v[2] != v[3]) {     // 情况2: 交换C和A+B，重新求解
                swap(v[2], v[3]);
                solve(v);
            }
        }
        printf("%d\n", (int)ans.size());
    }
    return 0;
}