洛谷[P3799 妖梦拼木棒] {暴力枚举}

题目背景

上道题中，妖梦斩了一地的木棒，现在她想要将木棒拼起来。

题目描述

有 n 根木棒，现在从中选 4 根，想要组成一个正三角形，问有几种选法？

答案对 $10^9$+7 取模。

输入格式

第一行一个整数 n。

第二行 n个整数，第 i 个整数 a_i代表第 i 根木棒的长度。

输出格式

一行一个整数代表答案。

输入输出样例

输入 4 1 1 2 2 输出 1

说明/提示

数据规模与约定 对于 30% 的数据，保证 n≤5×$10^3$。 对于 100% 的数据，保证 1≤n≤$10^5$ ，0≤a_i ≤5×$10^3$。

解题思路

1、首先计算每一个数字的出现个数，有点映射的思想。 2、然后如果一个数字x出现大于等于两次则说明这个数字可能作为正三角形的两条边。 3、然后再假设j是选择的四个数中除相等的两个数之外较小的那个数，则其一定小于等于(x/2)，此时另外一个数字就是x-j。然后就进行比遍历，寻找满足条件的结果，计算可能的值。

注意

正三角形就是等边三角形。

取模运算时不要使用+=，要写成正常形式，否则会溢出。

完整代码

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10; const int mod=1e9+7; int a[maxn]; int sum[maxn]; int C(int x,int c) { if(c==1) return x; else return (x*(x-1)/2)%mod; } int main() { int m; int maxa; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d",&a[i]); sum[a[i]]++; maxa=max(maxa,a[i]);//找出最大的那个数，作为之后循环的边界 } int ans=0; for(int i=1;i<=maxa;i++) { if(sum[i]>=2)//如果个数大于两个说明可以选择其中的两个作为正三角形的两边 { int fang=C(sum[i],2); for(int j=1;j<=i/2;j++)//强制使得j是小的那一部分 { if(j!=i-j&&sum[j]>=1&&sum[i-j]>=1) { ans=(ans+fang*C(sum[j],1)*C(sum[i-j],1)%mod)%mod; } if(j==i-j&&sum[j]>=2) { ans=(ans+fang*C(sum[j],2)%mod)%mod;//注意相加不能使用+= } } } } printf("%d",ans); return 0; }