洛谷7月月赛题解 B P6686

题目

这题题面比较长，稍微总结一下吧：

给你一堆棍棍，第 $i$ 根的长度为 $a_i$

求这些木棍能围成几种等腰三角形。
（注意，木棍有编号）

不清楚可以看原题

Subtask1 (30pts)：$1\leq n\leq200$
Subtask2 (30pts)：$1\leq n\leq2000$
Subtask3 (20pts)：木棍长度全部相等。
Subtask4 (20pts)：无特殊限制。
对于 $100\%$ 的数据满足： $1 \leq n \leq 2 \times 10^5,1 \leq a_i \leq 2 \times 10^5$

解析

这其实是比较基础的排列组合题 （考场上硬是没做出来

考虑等腰三角形，有如下的性质。

1. 两边之和大于第三边
2. 两边之差小于第三边
3. 有两边长相等

所以，我们就可以想到几种方法：

1. 暴力枚举法
   枚举三边边长，并判断是否合法，复杂度 $O(n^3)$
2. 前缀和技巧+排列组合
   开一个桶记录，前缀和，排列组合计算，特判等边三角形。（想一想，为什么）

参考代码

第一种:

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int mod = 998244353;
const int maxn = 2e5+10;
int n,a[maxn],mx;
long long ans;
int main(void)
{
	scanf("%d",&n);
	for(int i = 1;i <= n;i++)
		scanf("%d",a+i);
	for(int i = 1;i <= n;i++)
		for(int j = i + 1;j <= n;j++)
			for(int k = j + 1;k <= n;k++)
				if((a[i] == a[j] && a[k] < a[i] + a[j]) || 
						(a[i] == a[k] && a[j] < a[i] + a[k]) ||
						(a[j] == a[k] && a[i] < a[j] + a[k]))
					ans++;
	cout<<ans;
}

第二种：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int n,a,val[200005],sum[200005],mx;
const int inv2=(mod+1)/2,inv3=(mod+1)/3,inv6=inv2*inv3%mod;

signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a);
		val[a]++;
		mx = max(mx,a);
	}
	for(int i=1;i<=mx;i++)sum[i]=(sum[i-1]+val[i])%mod;
	int ans=0;
	for(int i=1;i<=mx;i++)
	{
		int N=val[i];
		if(N<2)continue;
		ans=(ans+
				N*(N-1)/2%mod*(sum[min(i*2-1,mx)]-N)%mod//普通等腰，不等边
				+N*(N-1)%mod*(N-2)%mod*inv6%mod)%mod;//特判一下等边三角形
	}
	printf("%lld\n",ans);
	return 0;
}