求助!只过了前三个点
查看原帖
求助!只过了前三个点
1022761
wuuk楼主2023/9/5 17:37

我的思路是:

  1. 统计不同长度的木棒出现的次数,找到大于等于2次的,从中取两根,作为正三角形的两条边。

  2. 找剩余两根木棒,使其长度之和等于正三角形的边

  3. 对第一步和第二步用乘法原理得到取法总数。

代码如下:

#include <iostream>
using namespace std;
int a[5010], n, x;
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        a[x]++;
    }
    int ans = 0;
    for (int i = 1; i  <= 5000; i++)
    {
        if (a[i] >= 2)
        {
            int step1 = a[i] * (a[i] - 1) / 2;
            int step2 = 0;
            for (int j = 1; j <= i/2; j++)
            {
                if (a[j] && a[i - j] && i != j + j)
                {
                    step2 += a[i - j] * a[j];
                }
                if (a[j] && i == j + j)
                {
                    step2 += a[j] * (a[j] - 1) / 2;
                }
            }
            ans += step1 * step2;
        }
    }
    cout << ans % 1000000007;
    return 0;
}

2023/9/5 17:37
加载中...