首页 > 代码库 > bzoj 4927: 第一题
bzoj 4927: 第一题
Description
给定n根直的木棍，要从中选出6根木棍，满足：能用这6根木棍拼
出一个正方形。注意木棍不能弯折。问方案数。
正方形：四条边都相等、四个角都是直角的四边形。
Input
第一行一个整数n。
第二行包含n个整数ai，代表每根木棍的长度。
n ≤ 5000, 1 ≤ ai ≤ 10^7
Output
一行一个整数，代表方案数。
考虑正方形每条边由几条木棍组成，只有1122和1113两种情况，分别枚举统计一下
#include<bits/stdc++.h>typedef long long i64;int n,a[5007],ap=0,as[5007],at[5007],t[10000007];i64 ans=0,c3[5007];int main(){ scanf("%d",&n); for(int i=1;i<=n;++i)scanf("%d",a+i); std::sort(a+1,a+n+1); for(int i=1,j=1;i<=n;i=j){ int x=a[i]; for(;j<=n&&a[j]==x;++j); c3[ap]=i64(j-i)*(j-i-1)*(j-i-2)/6; as[ap]=x; at[ap++]=j-i; } for(int i=1;i<=n;++i){ for(int j=0;j<ap;++j)if(as[j]>a[i]){ ans+=c3[j]*t[as[j]-a[i]]; } for(int j=1;j<i&&a[i]+a[j]<=10000000;++j)++t[a[i]+a[j]]; } for(int i=0,l,r;i<ap;++i)if(at[i]>=2){ i64 s=0,s0=0,s1; for(r=i-1,l=0;r>=l;--r){ for(;r>=l&&as[l]+as[r]<as[i];++l); if(r<l||as[l]+as[r]!=as[i])continue; int x=at[l]; if(r==l){ s1=x*(x-1)/2; s+=s1*(x-2)*(x-3)/12; }else{ int y=at[r]; s1=x*y; s+=s1*(x-1)*(y-1)/4; } s+=s0*s1; s0+=s1; } ans+=at[i]*(at[i]-1)/2*s; } printf("%lld\n",ans); return 0;}
bzoj 4927: 第一题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。