此文章是vip文章,如何查看?  

1,点击链接获取密钥 http://nicethemes.cn/product/view29882.html

2,在下方输入文章查看密钥即可立即查看当前vip文章


洛谷[P3799 妖梦拼木棒] {暴力枚举} 奋斗的珂珂~

  • 时间:
  • 浏览:
  • 来源:互联网

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

题目背景

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

题目描述

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

答案对 10910^9+7 取模。

输入格式

第一行一个整数 n。

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

输出格式

一行一个整数代表答案。

输入输出样例

输入
4
1 1 2 2
输出
1

说明/提示

数据规模与约定
对于 30% 的数据,保证 n≤5×10310^3
对于 100% 的数据,保证 1≤n≤10510^5 ,0≤ai ≤5×10310^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;
 } 

本文链接http://element-ui.cn/news/show-713726.aspx