飞行棋 总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 65536kB
描述 给出圆周上的若干个点，已知点与点之间的弧长，其值均为正整数，并依圆周顺序排列。 请找出这些点中有没有可以围成矩形的，并希望在最短时间内找出所有不重复矩形
输入 第一行为正整数N，表示点的个数，接下来N行分别为这N个点所分割的各个圆弧长度
输出 所构成不重复矩形的个数
样例输入 8 1 2 2 3 1 1 3 3
样例输出 3
数据规模 N <= 20
注意到，如果两组对边对应的弧长相等，那么可以形成一个正方形。由于N<=20，我们就可以枚举所有可能的点。注意一维和数组的使用。
参考代码
#include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <string> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <queue> #include <deque> #include <map> #include <set> using std::cin; using std::cout; using std::endl; inline int readIn() { int a; scanf("%d",&a); return a; } int n; int cLength; //所有弧长的和 std::vector<int> arcLength; //第一段到第n段弧长的总和 std::vector<int> res; //用于保存4个点 int ans; namespace Regular { bool isRect() { int interval[4]= {0}; interval[0]=cLength-arcLength[res[3]] + arcLength[res[0]]; //画图看看就明白了 interval[1]=arcLength[res[1]]-arcLength[res[0]]; interval[2]=arcLength[res[2]]-arcLength[res[1]]; interval[3]=arcLength[res[3]]-arcLength[res[2]]; return interval[0]==interval[2] && interval[1]==interval[3]; } void dfs(int iStart = 1) //由于要求不重复，所以需要保存一个起始点 { if(res.size()==4) { ans+=isRect(); return; } for(int i = iStart; i <= n; i++) { res.push_back(i); dfs(i+1); //只能从第i+1个点继续搜 //这样一不需要vis数组，二不需要处理同点不同序的情况 res.pop_back(); } } void run() { dfs(); printf("%d",ans); } void input() { n=readIn(); arcLength.resize(n+1); for(int i=1; i<=n; i++) { int t = readIn(); cLength+=t; arcLength[i]=arcLength[i-1] + t; //和数组 } } } int main() { Regular::input(); Regular::run(); return 0; }由于这道题数据规模小，后来才发现其实4层for也是可以的。 由组合数可以得知，这道题的情况最多只有 4 C 20 = 4845 种，所以不存在效率问题。即使每次都从1而不是 i+1 开始搜索，也只需枚举 4 A 20 种情况。
