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

【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
",ans/8);
	return 0;
}