首页 > 代码库 > BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题，n^4大暴力】
BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题，n^4大暴力】
1800: [Ahoi2009]fly 飞行棋
Time Limit: 10 Sec Memory Limit: 64 MBSubmit: 1689 Solved: 1335
[Submit][Status][Discuss]
Description
给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形。
Input
第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
Output
所构成不重复矩形的个数
Sample Input
8
1
2
2
3
1
1
3
3
1
2
2
3
1
1
3
3
Sample Output
3
HINT
N<= 20
Source
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1800
分析：n^4大暴力，随便搞，学卿学姐的，开始写了个O(n)的，WA了QAQ
下面给出AC代码：
1 #include <bits/stdc++.h> 2 using namespace std; 3 int m; 4 int a[30]; 5 int main() 6 { 7 cin>>m; 8 for(int i=1;i<=m;i++) 9 {10 cin>>a[i];11 a[i]+=a[i-1];12 }13 int ans=0;14 for(int i=1;i<=m;i++)15 {16 for(int j=i+1;j<=m;j++)17 {18 for(int k=j+1;k<=m;k++)19 {20 for(int t=k+1;t<=m;t++)21 {22 if((a[j]-a[i]==a[t]-a[k])&&(a[m]+a[i]-a[t]==a[k]-a[j]))23 ans++;24 }25 }26 }27 }28 cout<<ans<<endl;29 return 0;30 }
BZOJ 1800: [Ahoi2009]fly 飞行棋【思维题，n^4大暴力】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。