洛谷：P3799：小Y拼木棒

题目

P3799：小Y拼木棒

分析

等边三角形三条边等长，但题目允许用4根木棒拼出三条边，因此只能出现“有一条边由两根拼接”的结构。设目标边长为\(a\)，那么四根木棒长度只能是a, a, c, d，并且满足\(c+d=a\)（\(c\)可等于\(d\)）。除此以外没有其他可行分配。

因此可以按如下思路计数：

1. 统计每个长度出现的次数count[x]。
2. 枚举\(a\)作为“单根边”的长度，至少需要两根长度为\(a\)的木棒。
3. 对固定的\(a\)，枚举\(c\)，令\(d=a-c\)，只需遍历\(c\in[1,\lfloor a/2\rfloor]\)以避免重复。
4. 根据\(c=d\)或\(c\neq d\)分别计算组合数。

因为\(a_i\le5000\)，双层枚举的复杂度为\(O(M^2)\)（\(M\)为最大长度），足够通过。

首先，输入木棍的数量和各自的长度（并同时记录最大的长度），并统计长度出现的次数：

int n;
cin >> n;

vector<int> count(MAX_LENGTH, 0);
int max_length = 0;

// 读入木棒长度并统计
for (int i = 0; i < n; ++i) {
    int length;
    cin >> length;
    count[length]++;
    max_length = max(max_length, length);
    ...
}

其次，遍历所有长度作为独立的两根木棍，如果这个长度的木棍数量少于2根就不用继续，否则计算可能的选择数量\(C_{count[i]}^2\)。

// 枚举两根相等的木棒长度 a
    for (int a = 1; a <= max_length; ++a) 
    {
        if (count[a] < 2) continue;

        // 选择两根长度为 a 的木棒作为两条边
        long long ways = combination(count[a], 2) % MOD;

然后，针对这个长度，选择另外两根配对的木棍，c+d=a。这里，c和d可能相等，也可能不等，分别处理。

    // 枚举另外两根木棒的长度组合 c + d = a
        for (int c = 1; c <= a / 2; ++c) 
        {
            int d = a - c;

            if (c == d) 
            {
                // 如果两根木棒长度相同
                if (count[c] >= 2) 
                {
                    answer = (answer + ways * combination(count[c], 2)) % MOD;
                }
            } 
            else 
            {
                // 如果两根木棒长度不同
                if (count[c] > 0 && count[d] > 0) 
                {
                    answer = (answer + ways * count[c] * count[d]) % MOD;
                }
            }
        }
    }

这里出现了一个辅助函数combination，是用来进行组合计算的。本题因为只能选择1根或者2根，所以可以简化函数过程。

// 计算组合数C(n,k)，这里k只能是1或2
inline long long combination(long long n, int k)
{
    if (k == 1)
        return n;
    return n * (n - 1) / 2;
}

答案

思考

这是一道挺有趣的题目。前期分析很重要！