CWOI S C0176B 木棒

给定 12 根木棒的长度，每个木棒至多用一次，求最多组成多少个三角形。

首先我们用 $n^3$ 把三个木棒所有组合算出来，存到集合 $S$ 和 $T$ 中，分别表示可形成三角形的组合和不可形成三角形的组合。 $|S| + |T| = \binom{12}{3} = 1320$。令 $c = 1320$。

利用双向搜索的思想：$O(c^2)$ 处理出一个 $S$ 中元素和一个 $T$ 中元素无公共木棒的组合，存到 $U$，同时处理出两个 $S$ 中元素无公共木棒的组合，存到 $V$。此时已经可以判断答案是否大于等于 1 或 2。对于 3 或 4，枚举 $U$ 中元素，求出它的反元素，再在 $U$ 和 $V$ 中匹配。

可以使用状压和平衡树以优化。

bool check_triangle(int a, int b, int c) {
    return a + b > c && b + c > a && a + c > b;
}

void solve()
{
    std::vector<int> a(12);
    for (auto &i : a) scanf("%d", &i);
    int ans = 0;
    std::vector<int> ok, bad;
    for (int i = 0; i < 12; i++) {
        for (int j = i + 1; j < 12; j++) {
            for (int k = j + 1; k < 12; k++) {
                if (check_triangle(a[i], a[j], a[k])) {
                    ok.emplace_back((1 << i) + (1 << j) + (1 << k));
                    ans = std::max(1, ans);
                } else {
                    bad.emplace_back((1 << i) + (1 << j) + (1 << k));
                }
            }
        }
    }
    std::map<int, int> okcnt; // double ok
    for (unsigned int i = 0; i < ok.size(); i++) {
        for (unsigned int j = i + 1; j < ok.size(); j++) {
            if ((ok[i] & ok[j]) == 0) {
                ans = std::max(2, ans);
                okcnt[ok[i] | ok[j]]++;
            }
        }
    }
    std::map<int, int> badcnt; // 1 ok and 1 bad
    for (unsigned int i = 0; i < ok.size(); i++) {
        for (unsigned int j = 0; j < bad.size(); j++) {
            if ((ok[i] & bad[j]) == 0) {
                badcnt[ok[i] | bad[j]]++;
            }
        }
    }
    for (auto [i, _] : okcnt) {
        int j = 0xfff ^ i;
        if (okcnt.contains(j)) {
            puts("4");
            return ;
        } else if (badcnt.contains(j)) {
            ans = std::max(ans, 3);
        }
    }
    printf("%d\n", ans);
}