P6686 混凝土数学

哈哈哈!我爱月赛。

第一次月赛拿到分呢。

(卡掉卡掉)

题目描述

你正在看混凝土数学,这时旁边的工地开工了,你觉得看他们施工更有意思,于是你向窗外望去,注意到了一些长度不同的木棍。具体而言,你看到了 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和记忆化不考虑可是会爆零的(别问我是怎么知道的)

陈老看完留个言吧!!

上一篇:洛谷2019 3月月赛 T1


下一篇:WPF 用 DataTemplate 合并DataGrid列表列头<类似报表设计>及行头列头样式 - 学习