ZOJ 3706 Break Standard Weight：模擬枚舉求最大可稱重量種類數

題目大意

有兩個標準砝碼（質量為整數），可將其中一個敲碎成兩塊（質量和不變，均為整數）。三塊砝碼可放天平左右兩邊，求最多能稱出多少種不同重量（不含 0）。

解題思路：暴力枚舉 + 集合去重

操作分析

三塊砝碼 a, b, c，每塊可放左、右、不放，共 3³=27 種組合，但對稱情況實際只有 13 種非零淨重量：
a, b, c, a+b, a+c, b+c, a-b, a-c, b-c, a+b+c, a+b-c, a+c-b, b+c-a

算法流程

1. 枚舉敲碎第一塊：i = 1..a/2，得到 (i, a-i, b)。
2. 枚舉敲碎第二塊：i = 1..b/2，得到 (i, b-i, a)。
3. 對每種分法，計算上述 13 種重量的絕對值，存入 set 去重，刪除 0。
4. 記錄最大集合大小。

完整代碼

#include <iostream>
#include <cstdio>
#include <set>
#include <cmath>
using namespace std;
int cal(int a, int b, int c) {
    set<int> cnt;
    cnt.insert(abs(a)); cnt.insert(abs(b)); cnt.insert(abs(c));
    cnt.insert(abs(a+b)); cnt.insert(abs(a+c)); cnt.insert(abs(b+c));
    cnt.insert(abs(a-b)); cnt.insert(abs(a-c)); cnt.insert(abs(b-c));
    cnt.insert(abs(a+b+c)); cnt.insert(abs(a+b-c));
    cnt.insert(abs(a+c-b)); cnt.insert(abs(b+c-a));
    cnt.erase(0);
    return cnt.size();
}
int main() {
    int t, a, b, maxx;
    scanf("%d", &t);
    while (t--) {
        maxx = 0;
        scanf("%d%d", &a, &b);
        for (int i = 1; i <= a/2; i++)
            maxx = max(maxx, cal(i, a-i, b));
        for (int i = 1; i <= b/2; i++)
            maxx = max(maxx, cal(i, b-i, a));
        printf("%d\n", maxx);
    }
    return 0;
}

複雜度分析

• 枚舉次數：a/2 + b/2 ≤ 100（砝碼質量 ≤ 200）。
• 每次計算 13 次插入 set，log 因子極小。
• 總時間遠小於 1ms，極其高效。

關鍵細節

• 用 abs 取絕對值，天平左右對稱。
• set 自動去重，最後 erase(0) 排除 0 重量。
• 枚舉上限 a/2 避免重複（交換兩塊碎片等價）。