2015北京区域赛现场赛第2题。
题面：http://media.hihocoder.com/contests/icpcbeijing2015/problems.pdf
OJ链接：http://hihocoder.com/problemset/problem/1255
题意：给4个矩形的宽和高，问能否选出3个拼成一个大矩形。
解法：可以称之为构造、暴力、枚举、搜索
当时场上写了个很无脑的版本，变量a,b,c一个个枚举，没有可扩展性。
其实稍加分析，把判断和枚举的两个模块独立开来：
1. 判断的过程每次都只针对一个由3*2个数构成的序列，实现比较直观，只有两种构造方法，见代码；
2. 一共有(4!) * (2^3)个不同的序列，所以枚举的过程可转化为两个独立的子问题：求4个数的全排列和3个二值量所有取值向量。
全排列可借助next_permutation方便地得到。k个二值量的所有取值向量可以通过[0,2^k]的整数的二进制表示得到。
由于是二值量，直接先swap再交换回来即可。注意swap传引用。
1 #include <cstdio> 2 #include <algorithm> 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 }
