题解 P6686 【混凝土数学】

· · 题解

思路：

这道题目只要枚举，然后优化一下就可以通过了

我们首先把每个长度的棍子的个数都记录下来

我们可以枚举每一个腰的长度，然后我们就要计算能和这两根木棍形成三角形的个数。

当两条边的长度和小于等于第三条边时，三根木棒就能形成三角形

因为两根木棍的长度相同，第三条边的长度一定是一个正整数，所以不存在一个腰加上第三条边的长度和小于另一个腰

所以只有一种情况不能形成三角形：当第三条边的长度大于等于两条腰的和才不能形成三角形

想求出不能和这个长度为腰形成三角形的边的个数，有两种方法

第一种就是从这两条边的长度和开始，一直到最长长度，把它们加起来

显然复杂度过高，会时间超限

第二种方法就是一开始没有能形成三角形的，因为我们的循环枚举腰是从短边开始，所以如果前面的长度和第三条边成立那么后面的长度也和第三条边成立，最后再加上前面的和第三条边不成立，后面的和第三条边成立的个数，最多也就两个

现在我们知道了这个长度的腰能和多少根棍子形成三角形的个数了，我们就可以用乘法原理算出答案了

乘法原理要分类讨论：

等边三角形的个数 和 等腰三角形的个数

假设我们有 x 根相等长度的棍子 y 根能和它们形成三角形个数的棍子

我们先把腰的符合的方案数算出来，再把它乘上 y-x 就可以了，之所以乘上 y-x 是因为我们要求的是等腰三角形 y 中也包括了和这个长度相等的那些棍子，我们要把它减掉

我们取第一根棍子有 x 种方法,取第二根棍子就只有 x-1 种方法了，是因为第一根棍子被取走了，没法再取了

然后算出来 x(x-1) ,但是要除二，因为这两根棍子交换顺序也是同一种方案

最后我们算出来 x(x-1)÷2

乘上 y-x 后就是 x(x-1)(y-x)÷2

接着我们算等边三角形的个数，依旧假设有 x 个

那么取第一根有 x 种，第二根有 x-1 因为已经取走一根不能再取了，第三根有 x-2 种，因为前面已经取走两根，这两根不能再取了

我们得到式子 x(x-1)(x-2),但是这不是最终答案

我们取这几根棒子也有顺序，顺序不同，但还是一种方案

取第一根有 3 种方法，取第二根有 2 方法，因为取过第一根就不能再取了,第三根只有 1 种方法，因为取了两根只剩最后一根，只能选它了

于是我们推出式子 x(x-1)(x-2)÷(1×2×3)

化简得到 x(x-1)(x-2)÷6 当然也可以是 (x^3-3x^2+2x)÷6

加起来就是 x(x-1)(x-2)÷6+x(x-1)(y-x)÷2

除了上面那些还有可以优化的

我们只要枚举到最长的木棍就行了，最好不要看都不看直接一到二十万循环，那些小数据的也会慢

最后提醒一下，每个木棍的长度个数和答案最好用 long long ，假设全是一个长度比如二十万个 1 ，就是 200000×199999×199998÷6 ，超过 10^{15} ,而 int 也就大约 2.1×10^9 ,肯定不够

代码：

代码基本上是目前最短的了，加上快读就是目前最优解

#include <stdio.h>//C语言代码
long long f[200001],ans;//分别是每个长度的个数和答案
int main()
{   
    int n,m=0,k=0,l=1,a;//分别为木棍个数，最长木棍，符合条件的木棍数，符合条件的最长木棍，木棍长度
    scanf("%d",&n);//输入木棍个数
    for(int i=1;i<=n;i++)//循环木棍个数次
    {
        scanf("%d",&a);//输入木棍长度
        f[a]++;//这个长度的木棍多了一个
        m=m<a?a:m;//更新最长木棍的长度
    }
    for(int i=1;i<=m;i++)//枚举每一个长度为腰，也不用判断是否是零或者一，因为木棍如果是这些数的话，后面的乘法会让它们变成零
    {
        for(;l<i*2&&l<=m;l++)//枚举到符合条件的木棍长度
            k+=f[l];//符合条件的木棍数加上这个长度的木棍个数
        ans+=(f[i]-1)*f[i]*(k-f[i])/2+(f[i]-2)*(f[i]-1)*f[i]/6;//乘法原理
    }
    printf("%lld",ans%998244353);//输出取模后的答案
    return 0;//别忘了
}

谢谢管理审核和大家观赏！