JZOJ 4.15 1666——【AHOI2009】飞行棋

本文主要是介绍JZOJ 4.15 1666——【AHOI2009】飞行棋，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

　　给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。
　　请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。

Input

　　第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度

Output

　　所构成不重复矩形的个数

Sample Input

8
1
2
2
3
1
1
3
3

Sample Output

3
Hint

　　N<= 20
　　
　　

---

由图可知，其实只是枚举可以形成几个平行四边形
也就是上底==下底，高相等的平行四边形或长方形。
我们可以用前缀合记录前i条弧的长度。
然后四重循环枚举四个顶点的位置，如果满足d[j]-d[i]==d[l]-d[k]&&d[k]-d[j]==abs(d[l]-d[i+n])（也就是判断上底==下底，高是否相等），则ans++

---

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
int main()
{int n,ans=0,a[21],d[41];scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]),d[i]=d[i-1]+a[i];for (int i=n+1;i<=2*n;i++) d[i]=d[i-1]+a[i-n];for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++)for (int k=j+1;k<=n;k++)for (int l=k+1;l<=n;l++)if (d[j]-d[i]==d[l]-d[k]&&d[k]-d[j]==abs(d[l]-d[i+n])) ans++;printf("%d\n",ans);return 0;
}

这篇关于JZOJ 4.15 1666——【AHOI2009】飞行棋的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---