C++信奥之径，锻炼思维，扎实算法——暴力枚举(4)

小 Y 拼木棒

题目描述

算法解析

首先分析题目，想要用4根木棒拼成一个正三角形，一定是a=b=c+d的组合。

（1）由于4根木棒中有2根是一样的，因此在输入木棍长度时，要运用类似计数排序的技巧，记录每种长度木棍的个数；

（2）然后枚举边长的所有可能性，理论上的范围是2~5000，但是可以通过在输入长度时记录木棍长度的最小值和最大值来缩小范围；

（3）首先判断当前枚举的边长i是否有2根及以上的木棍。如果没有，直接枚举下一边长；如果有，那么从n根木棍中选出2根的所有方案数为n*(n-1)/2；

（4）接下来枚举2根木棒搭边的情况，假设一根木棍长j，那么另一根木棍就是i-j，那么搭出这条边的木棒选择方案数就为长为j的木棍数*长为i-j的木棍数。

在这里要特别注意，为了组成方案不重复，j最多枚举到i/2，并且如果出现了j=i-j的情况，那么公式就变成了

长j的木棒数*(长j的木棒数-1)/2

（5）每一次的枚举结果都要与n*(n-1)/2，即前2根长木棒方案数相乘，但由于结果较大，在计算的每一步都要对100000007（题目要求）取模，以防万一爆数据。

【参考代码】

#include
using namespace std; 
const int mod=1000000007;
int t[5005];
int ans=0;
int main(){
    //ios::sync_with_stdio(0); //加快cin和cout速度
    int n;
    cin>>n;
    for(int i=0;i>a;
        t[a]++;
    }
    int tmp;
    for(int i=2;i<=5000;i++){
        if(t[i]<2)continue;
        else{
            tmp=(t[i]*(t[i]-1)/2)%mod;
            for(int j=1;j<=i/2;j++){
                if(j==i-j && t[j]>=2)ans=(ans+tmp*(t[j]*(t[j]-1)/2))%mod;
                else if(t[j]&&t[i-j] && j!=i-j)ans=(ans+tmp*t[j]*t[i-j])%mod;
            }
        }
        ans%=mod;
    }
    cout<<ans;
    return 0;
} 

运行结果