首页 > 代码库 > BZOJ 1800 AHOI2009 fly 飞行棋 暴力
BZOJ 1800 AHOI2009 fly 飞行棋 暴力
题目大意:给定圆弧上的一些点,求有多少个矩形
矩形的对角线一定是直径 所以问题转化为求直径 若直径数量为x 则答案为C(x,2)
这东西用不用啥数据结构维护一下……手贱去看了下数据范围……
其实线性做法巨好写 为何看到那么多版本都是O(n^2)的
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 30 using namespace std; int n,sum,temp,ans,a[M]; int main() { int i,j; cin>>n; for(i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i]; if(sum&1) return puts("0"),0; sum>>=1; for(i=j=1;i<n;i++) { temp+=a[i]; while(temp>sum) temp-=a[j++]; if(temp==sum) ++ans; } cout<<(ans*(ans-1)>>1)<<endl; }
BZOJ 1800 AHOI2009 fly 飞行棋 暴力
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。