bzoj1800 飞行棋
脑筋急转弯。
提示：矩形矩形矩形。O(n)O(n)O(n)。
再提示：直角。
再提示：直径。
代码：
//Serene
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
const int maxn=20+5;
int n,a[maxn],tot,sum;
int aa;char cc;
int read() {
aa=0;cc=getchar();
while(cc<'0'||cc>'9') cc=getchar();
while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();
return aa;
}
int main() {
n=read();
for(int i=1;i<=n;++i) a[i]=read(),tot+=a[i];
if(tot&1) {
printf("0");
return 0;
}
else tot>>=1;
int t=0,now=0;
for(int pos=1;pos<=n;++pos) {
while(now<tot) {
t=t%n+1; now+=a[t];
}
if(now==tot) sum++;
now-=a[pos];
}
sum/=2;
printf("%d",sum*(sum-1)/2);
return 0;
}