想了好久,只是计算顺序不同,为什么错了,求大佬解惑
查看原帖
想了好久,只是计算顺序不同,为什么错了,求大佬解惑
112041
GeorgeHu楼主2020/11/12 23:12

先是错误的代码,求大佬解惑

int main(void)
{
    int bucket[5050]={0, };
    long long int ans=0, tmp;
    int i, j, n, max=-99999999;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &j);
        if (max < j)
            max = j;
        bucket[j]++;
    }

    //枚举可能的边长
    for (i = 1; i <= max; i++)
    {
        //最长边至少需要两根
        if (bucket[i] < 2)
            continue;
        //对最长边的选择方案数
        //C(bucket[i], 2)
        tmp = bucket[i] * (bucket[i] - 1) / 2;
        //枚举需要拼接的两根火柴中较小的那根,(保证它是较小的)防止重复枚举
        //到i/2即可,例如2+5=7,5+2=7
        for (j = 1; j*2 <= i; j++)
        {
            //特殊处理i为偶数导致的3+3=6这样的拼接
            if (j*2 == i && bucket[j] >= 2)
                tmp *= bucket[j]*(bucket[j]-1) / 2;
            else if (bucket[j]*bucket[i-j] != 0)
                //C(bucket[j], 1)*C(bucket[i-j], 1)
                tmp *= bucket[j]*bucket[i-j];
            tmp = tmp * (bucket[i] * (bucket[i] - 1)) / 2;
            ans = (ans + tmp) % 1000000007;
        }
    }
    printf("%lld", ans % 1000000007);

    return 0;
}

下面是改过后的代码,是对的:

int main(void)
{
    int bucket[5050]={0, };
    long long int ans=0, tmp;
    int i, j, n, max=-99999999;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
    {
        scanf("%d", &j);
        if (max < j)
            max = j;
        bucket[j]++;
    }

    //枚举可能的边长
    for (i = 1; i <= max; i++)
    {
        //枚举需要拼接的两根火柴中较小的那根,(保证它是较小的)防止重复枚举
        //到i/2即可,例如2+5=7,5+2=7
        for (j = 1; j <= i / 2; j++)
        {
            //特殊处理i为偶数导致的3+3=6这样的拼接
            if (j*2 == i)
                tmp = bucket[j]*(bucket[j]-1)/2;
            else
                //C(bucket[j], 1)*C(bucket[i-j], 1)
                tmp = (bucket[j]*bucket[i-j]);
            ans = (ans + tmp * (bucket[i] * (bucket[i] - 1)) / 2) % 1000000007;
        }
    }
    printf("%lld", ans);

    return 0;
}
2020/11/12 23:12
加载中...