1738 - 拼火柴
有一天，小明心血来潮到化学实验室做实验，实验中要用到火柴，但是桌上没有，于是小明到别处翻箱倒柜找到了一袋子火柴，但是里面的火柴有的长度相等，有的长度不等。当小明做完实验的时候看着这些火柴突然想用它们拼正方形玩。
现在请你判断，小明随手拿出几根火柴，这些火柴能否按照头尾相接的方式拼成一个正方形，火柴不能折断来使用，并且每根火柴都必须使用上。
Input
输入的第一行为一个整数n（1<=n<=100），表示测试数据的组数。
接下来n行，每行先输入一个整数m（4<=m<=20），表示小明拿出的火柴个数，然后输入m个整数，每个数表示一根火柴的长度，火柴长度范围为[1,10000]。
Output
对于每组输入，如果能够拼成正方形，输出“yes”，否则输出“no”。
Examples
Input
3 4 1 1 1 1 5 10 20 30 40 50 8 1 7 2 6 4 4 3 5
Output
yes no yes
Solution C
#include<stdio.h> #include<stdlib.h> int a[21],flog=0,sum,n,vis[21]; int cmp(const void *c,const void *d) { return *(int *)d-*(int *)c; } void dfs(int cur,int k,int l,int t) { int i; if(cur==4) { flog=1; return ; } if(t>n-3) return ; for(i=k;i<n;i++) { if(flog) break; if(!vis[i]&&l<=sum) { vis[i]=1; l+=a[i]; if(l==sum) { dfs(cur+1,1,0,1); } dfs(cur,i,l,t+1); vis[i]=0; l-=a[i]; } } } int main() { int T; scanf("%d",&T); for(;T>0;T--) { int i; flog=0; sum=0; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d",&a[i]); sum+=a[i]; vis[i]=0; } if(sum%4)//木棒总长应为4的倍数 printf("no\n"); else { qsort(a,n,sizeof(a[0]),cmp); sum/=4; if(a[n-1]>sum) printf("no\n"); else { dfs(1,0,0,1); if(flog==1) printf("yes\n"); else printf("no\n"); } } } return 0; }
Solution C++
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; int a[20], u[20], side, S, E; bool cmp(int a, int b) { return a > b; } int dfs(int s, int l, int k) { if (l == side) { k++; l = 0; s = S; } if (k == 4) return 1; for (int i = s; i <= E; i++) if (!u[i] && l + a[i] <= side) { u[i] = 1; if (dfs(i + 1, l + a[i], k)) return 1; u[i] = 0; } return 0; } int main() { int n, m, i, k; scanf("%d", &n); while (n--) { scanf("%d", &m); for (side = i = 0; i < m; i++) { scanf("%d", &a[i]); side += a[i]; } if (side % 4) { puts("no"); continue; } side /= 4; sort(a, a + m, cmp); memset(u, 0, sizeof(u)); for (S = k = i = 0; i < m; i++) if (a[i] > side) break; else if (a[i] == side) { k++; S = i + 1; u[i] = 1; } if (i < m) { puts("no"); continue; } if (k == 3 || k == 4) { puts("yes"); continue; } E = m - 1; if (dfs(S, 0, k)) puts("yes"); else puts("no"); } return 0; }