【BZOJ1800】[AHOI2009]飞行棋（暴力）

题面

BZOJ

洛谷

题解

预处理一下前缀和就可以\(O(1)\)计算两点间的距离了，直接\(O(n^4)\)暴力枚举即可。

#include<iostream>

#include<cstdio>

using namespace std;

int n,s[50],ans;

int Dis(int l,int r){if(r<l)r+=n;return s[r]-s[l];}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;++i)scanf("%d",&s[i]);

	for(int i=1;i<=n;++i)s[i+n]=s[i];

	for(int i=1;i<=n+n;++i)s[i]+=s[i-1];

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			for(int k=1;k<=n;++k)

				for(int l=1;l<=n;++l)

				{

					if(i==j||i==k||i==l)continue;

					if(j==k||j==l||k==l)continue;

					if(Dis(i,j)==Dis(k,l)&&Dis(j,k)==Dis(l,i))++ans;

				}

	printf("%d\n",ans/8);

	return 0;

}