本文共 1804 字，大约阅读时间需要 6 分钟。
2015北京区域赛现场赛第2题。
题面：
OJ链接：
题意：给4个矩形的宽和高，问能否选出3个拼成一个大矩形。
解法：可以称之为构造、暴力、枚举、搜索
当时场上写了个很无脑的版本，变量a,b,c一个个枚举，没有可扩展性。
其实稍加分析，把判断和枚举的两个模块独立开来：
1. 判断的过程每次都只针对一个由3*2个数构成的序列，实现比较直观，只有两种构造方法，见代码；
2. 一共有(4!) * (2^3)个不同的序列，所以枚举的过程可转化为两个独立的子问题：求4个数的全排列和3个二值量所有取值向量。
全排列可借助next_permutation方便地得到。k个二值量的所有取值向量可以通过[0,2^k]的整数的二进制表示得到。
由于是二值量，直接先swap再交换回来即可。注意swap传引用。
1 #include2 #include 3 using namespace std; 4 5 struct Rec{ 6 int w, h; 7 Rec& operator = (Rec& r){ 8 w = r.w; 9 h = r.h;10 return *this;11 }12 }rec[4];13 14 int n;15 int index[4];16 17 void swap(Rec& r){ //注意传引用 18 int temp = r.w;19 r.w = r.h;20 r.h = temp;21 }22 23 void reverse(int x){24 for(int i=0; i<3; i++){25 if(x&1){26 swap(rec[index[i]]);27 }28 x >>= 1;29 }30 }31 32 33 bool judge(){ 34 int ans = false;35 36 if(rec[index[0]].w == rec[index[1]].w 37 && rec[index[1]].w == rec[index[2]].w )38 ans = true;39 else if(rec[index[1]].w == rec[index[2]].w 40 && rec[index[0]].h == rec[index[1]].h + rec[index[2]].h) 41 ans = true;42 43 return ans;44 }45 46 int main()47 {48 scanf("%d", &n);49 while(n--){50 for(int i=0; i<4; i++){51 scanf("%d%d", &rec[i].w, &rec[i].h);52 index[i] = i;53 }54 int flag = 0;55 do{56 for(int i=0; i<8; i++){57 reverse(i);58 if(judge()){59 flag = 1;60 break;61 }62 reverse(i); 63 }64 if(flag) break;65 }while(next_permutation(index, index+4));66 printf("%s\n", flag ? "Yes" : "No");67 }68 return 0;69 }
转载地址：http://qhsso.baihongyu.com/