Square
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19923 Accepted Submission(s): 6272Problem DescriptionGiven a set of sticks of various lengths, is it possible to join them end-to-end to form a square?
InputThe first line of input contains N, the number of test cases. Each test case begins with an integer 4 <= M <= 20, the number of sticks. M integers follow; each gives the length of a stick - an integer between 1 and 10,000.
OutputFor each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".
Sample Input34 1 1 1 15 10 20 30 40 508 1 7 2 6 4 4 3 5
Sample Outputyesnoyes
Source
RecommendLL
题解:第一行给测试询问数m
接下来m行,第一个数字是棍子数量n,接下来n个数字是棍子长度。
假如这些棍子能够首尾相接,形成一个正方形,则输出yes,否则no。
我一看这题,就感觉和POJ 1011 Sticks非常像。
于是我这么把POJ的代码胡乱一改,果然——只能输出no,我也不知道咋肥四~~~留一个坑。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 5 using namespace std; 6 int a[25];//被截断的棍子长度集 7 int vis[25]; //标记是否使用过该棍子 8 //int num;//被截断后的棍子数 9 int cnt,sum,flag; 10 int n; 11 bool cmp(int a,int b) 12 { 13 return a>b;//降序 14 } 15 int dfs(int rest,int n) 16 { 17 if(rest==0&&n==0) 18 { 19 cnt++; 20 return cnt; 21 } 22 if(rest==0) 23 rest=sum/4; 24 for(int i=1;i<=n;i++) 25 { 26 if(vis[i])//如果这个数已经被检测过了,跳过 27 continue; 28 if(rest>=a[i]) 29 { 30 vis[i]=1; 31 if(dfs(rest-a[i],n-1))//因为dfs函数有返回值,使得目标长度成立 32 { 33 cnt++; 34 return cnt; 35 } 36 vis[i]=0; 37 if(a[i]==rest||sum/4==rest)// 38 break; 39 while(a[i]==a[i+1])//因为是降序排列的,如果这个数不满足,那么下一位和它相等的数肯定也不满足 40 i++; 41 } 42 } 43 return 0; 44 } 45 46 47 int main() 48 { 49 int m; 50 while(scanf("%d",&m)) 51 { 52 while(m--) 53 { 54 int i; 55 cnt=0; 56 flag=0; 57 sum=0; 58 scanf("%d",&n); 59 for(i=1;i<=n;i++) 60 { 61 scanf("%d",&a[i]); 62 sum=sum+a[i]; 63 } 64 sort(a+1,a+n+1,cmp); 65 memset(vis,0,sizeof(vis)); 66 flag=dfs(0,n); 67 if(flag==4) 68 printf("yes\n"); 69 else 70 printf("no\n"); 71 } 72 } 73 // system("pause"); 74 return 0; 75 }