【BZOJ4927】第一题

Description

给定n根直的木棍，要从中选出6根木棍，满足：能用这6根木棍拼

出一个正方形。注意木棍不能弯折。问方案数。

正方形：四条边都相等、四个角都是直角的四边形。

Input

第一行一个整数n。

第二行包含n个整数ai，代表每根木棍的长度。

n ≤ 5000, 1 ≤ ai ≤ 10^7

Output

一行一个整数，代表方案数。

Sample Input

8
4 5 1 5 1 9 4 5

Sample Output

题解：这。。。这不是沈阳集训的原题吗？（xqz说是山东集训的原题）

由于题目让你拼的是正方形，那么这个正方形的组成显然只有两种情况：3+1+1+1或2+2+1+1（这里指的是正方形的四条边），那么我们分类讨论这两种情况。

如果是2+2+1+1，那么我们可以枚举最长的那2根木棍（也就是两个1的长度）。显然要先排序，并将长度相同的木棍合在一起。然后我们已知正方形的边长，那么问题就变成了如何选出4根木棍a,b,c,d使得a+b=c+d=这个边长。这里我采用的是双指针法。两个指针从两段向中间移动，就可以顺便统计出有多少对木棍符合条件。于是ans+=C(最长的木棍的条数，2)*C（符合条件的对数，2），当然，别忘了去重！

如果是3+1+1+1，我们依旧是枚举最长的那3根木棍。然后问题就变成了如何在一堆木棍中选出3根使得长度之和为一个定值。这个显然是O(n³)的背包啊，而我们要的是O(n²)的复杂度，怎么办？

看来我们枚举最长棍的做法不太可行，那么我们可以换个角度，枚举3条短棍中最长的那一条。那么我们可以用s[i]表示在之前的木棍中，选出两根使得长度之和为i的方案数。这样，我们在枚举到i的时候，先枚举i后面的所有木棍j，判断一下j能否成为最长的木棍，也就是判断s[j的长度-i的长度]是否为0。如果是，则更新答案；枚举完j后，我们再用i来更新s数组，这就变成了一个背包问题。

然而考试的时候大佬们都是用容斥来处理的3+1+1+1，感觉容斥学的不好，没太听懂~

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef long long ll;int n,m;ll ans,sum,cnt;int v[5010],val[5010],num[5010],bel[5010];int s[10000010];int main(){	//freopen("yist.in","r",stdin);	//freopen("yist.out","w",stdout);	scanf("%d",&n);	int i,j,l,r;	for(i=1;i<=n;i++)	scanf("%d",&v[i]);	sort(v+1,v+n+1);	for(i=1;i<=n;i++)	{		if(v[i]>v[i-1])	val[++m]=v[i];		num[m]++,bel[i]=m;	}	for(i=1;i<=m;i++)	{		if(num[i]>=2)		{			sum=cnt=0;			for(l=1,r=i-1;l<=r;l++)			{				while(l<=r&&val[l]+val[r]>val[i])	r--;				if(val[l]+val[r]!=val[i]||l>r)	continue;				if(l==r)				{					if(num[l]>=4)	cnt+=(ll)num[l]*(num[l]-1)*(num[l]-2)*(num[l]-3)/2/3/4;					cnt+=(ll)num[l]*(num[l]-1)/2*sum;				}				else				{					if(num[l]>=2&&num[r]>=2)	cnt+=(ll)num[l]*(num[l]-1)/2*num[r]*(num[r]-1)/2;					cnt+=(ll)num[l]*num[r]*sum;					sum+=(ll)num[l]*num[r];				}			}			ans+=cnt*num[i]*(num[i]-1)/2;		}	}	for(i=1;i<=n;i++)	{		for(j=bel[i]+1;j<=m;j++)	if(num[j]>=3)	ans+=(ll)num[j]*(num[j]-1)*(num[j]-2)/2/3*(s[val[j]-v[i]]);		for(j=1;j<i;j++)	if(v[j]+v[i]<=v[n])	s[v[j]+v[i]]++;	}	printf("%lld",ans);	return 0;}

【BZOJ4927】第一题双指针+DP（容斥？）

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 【BZOJ4927】第一题 双指针+DP（容斥？）