题解 P3799 【妖梦拼木棒】

· · 题解

因为聪明，所以我才橙名。小学生又来发题解了！

题号：P3799

算法：枚举，暴力，数组计数

难度：★★★

开课了！

这道题虽然只是一道枚举的题目，但也还是有点难的。先给大家介绍一下枚举。

枚举，在一个有限的区间里面逐个查找。这里强调一下有限的区间，如：1~100中的正整数，这是一个有限的区间。而1~10中的小数，是一个无限的区间。

这题很容易让人想到四重循环暴力枚举，但是数据不饶人，这样子时间复杂度是O(n^4)，而n最大是100000，所以很显然这是不行的。

我们又从数据发现，ai好像比较小，所以我们就应该从ai入手。正三角形他的三条边都一样长，我们要挑四条木棒，说明至少有两条边的长度相等，另外两条边的长度之和等于四条边总长度的三分之一。至于为什么，想必大家都可以自己推理出来。

我们要找哪两根或以上的木棍长度先等，就要使用到数组计数。ai当中从最小的到最大的循环，如果当前位置数组的量大于等于2，就开始从最小的ai到i枚举。至于具体怎样做，大家可以看我的代码上的批注。

注意：统计的时候就要边统计边求余了，不然可能会爆掉。

课讲完了，上代码：

#include<iostream>
#include<fstream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<string>
#include<cstring>
#include<string.h>
#include<algorithm>
#include<iomanip>
using namespace std;
int n,b[5010],a[1000010],minn=1e9,maxx;
long long ans;
const int mod=1e9+7;
int main()
{
    cin>>n;
    for(int i=1; i<=n; i++)
    {
        cin>>a[i];//输入
        minn=min(minn,a[i]);//找出最小的ai
        maxx=max(maxx,a[i]);//找出最大的ai
        b[a[i]]++;//数组计数
    }
    for(int i=minn+1; i<=maxx; i++)//这里从最小量+1开始枚举，是因为最小量不可能有两个比它更小的两组成
    {
        if(b[i]>1)//如果这个数字有一个以上
            for(int j=minn; j<=i/2; j++)//开始枚举
                if(b[j]>=1&&b[i-j]>=1)//如果他可以被两个比他小的两组成
                {
                    if(j*2!=i)ans=(ans+(b[i]*(b[i]-1)/2)*b[j]*b[i-j]%mod)%mod;//统计
                    else if(b[j]>1)ans=(ans+((b[i]*(b[i]-1)/2)*(b[j]*(b[j]-1)/2)%mod)%mod)%mod;//统计
                }
    }
    cout<<ans%mod;//输出
    return 0;
}

祝大家能AC!