哈哈哈！我爱月赛。
第一次月赛拿到分呢。
（卡掉卡掉）
题目描述
你正在看混凝土数学，这时旁边的工地开工了，你觉得看他们施工更有意思，于是你向窗外望去，注意到了一些长度不同的木棍。具体而言，你看到了 nn 条木棍编号为 1,2,3,\ldots,n1,2,3,…,n，长度为 a_1,a_2,a_3,\ldots,a_na1,a2,a3,…,an。你突发奇想：有多少拿出其中 33 条木棍的方案满足它们能构成等腰三角形呢？你不想要输出的数太大，所以最后的方案要对 998244353998244353 取模。
给出等腰三角形的要求：任意两边之和大于第三边且至少有两条边边长相等。
例如，如果木棍长度分别为 \{3,3,2,2,4,5\}{3,3,2,2,4,5}，你就有 66 种方法，选取的木棍编号分别为：\{1,2,3\}{1,2,3}，\{1,2,4\}{1,2,4}，\{1,2,5\}{1,2,5}，\{1,2,6\}{1,2,6}，\{1,3,4\}{1,3,4}，\{2,3,4\}{2,3,4}。
我考试时的思路：
三重for循环！！！
30分代码奉上：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10000];//因为只想骗分所以就只开了10000
int flag=0;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
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[i]+a[j]>a[k])||a[j]==a[k]) flag++;//是否组成等腰
}
}
}
cout<<flag;
return 0;
}
骗到分欢天喜地
优化方法：
这道题也不用什么算法，只要想到优化办法就很简单了。
从边来思考，一个遍重复出现过2次以上才有可能当腰。
怎么记录一个边出现的次数呢？
桶。
用一个a数组记录每个边出现的次数：
for(int i=1;i<=n;i++)
{
scanf("%d",&x);
a[x]++;
}
在寻找时，一共有两种情况：
构成等腰三角形，构成等边三角形。
1.等腰三角形
一共有x条长度为y的边，选腰一共有x*(x-1)/2种情况（注意要除2）
那底呢？
因为三角形两辫子和大于第三边，
所以底小于2y。
把长度1-2y的边都遍历一遍，记个数即可：
for(int j=1;j<2*i;j++)
{
k=k+a[j];
}
总共有x*(x-1)*(k-x)/2种情况（注意，要去掉等边的情况）
2.等边三角形
共有x*(x-1)*(x-2)种情况
然后把两种情况加起来，就做完啦~：
#include<bits/stdc++.h>
using namespace std;
long long a[2000001];//十年OI一场空，不开long long见祖宗
int n;
int x;
int j=1;
long long ans=0;//记录总方案数
int k=0;
int maxn=0;
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&x);//快读
a[x]++;//桶，记录边数
if(x>maxn) maxn=x;//这里用了个maxn来储存最大的边当做循环边界
}
for(int i=1;i<=maxn;i++)
{
for(;j<2*i&&j<=maxn;j++)
{
k=k+a[j];//这里是一大坑点，如果每次j都从1开始，是O(n²)的复杂度，会超时，运用记忆化的思想，在上一种下寻找新的组合，复杂度便可以降到O(n)。
}
ans=(ans+a[i]*(a[i]-1)*(k-a[i])/2+a[i]*(a[i]-1)*(a[i]-2)/6)%998244353;//这里不用分类讨论，因为不符合要求（小于3）会有一个乘数为0，不影响结果
}
printf("%lld",ans%998244353);//记得取余
return 0;
}
还有一些细节已在代码中说明，maxn和记忆化不考虑可是会爆零的（别问我是怎么知道的）
陈老看完留个言吧！！