BZOJ1800:fly 飞行棋 (双指针 组合数)

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

sol:很可能被数据量误导,以为是个难题。 以为圆内接矩形的对角线经过圆中间,所以我们枚举对角线,然后组合数即可。  求过圆心的对角线可以暴力或者双指针。

#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const double pi=acos(-1.0);
ll sum[maxn],a[maxn],Now,ans;
int main()
{
int N,head=;
scanf("%d",&N);
rep(i,,N){
scanf("%lld",&a[i]);
sum[i]=sum[i-]+a[i];
}
rep(i,,N-)
rep(j,i,N-) {
if((sum[j]-sum[i-])*==sum[N]) ans++;
}
ans=ans*(ans-)/;
printf("%lld\n",ans);
return ;
}
上一篇:Python入门笔记(5):对象


下一篇:个人Python常用Package及其安装