HDU 1518 Square

Square

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 19923 Accepted Submission(s): 6272

Problem Description

Given a set of sticks of various lengths, is it possible to join them end-to-end to form a square?

Input

The 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.

Output

For each case, output a line containing "yes" if is is possible to form a square; otherwise output "no".

Sample Input

3

4 1 1 1 1

5 10 20 30 40 50

8 1 7 2 6 4 4 3 5

Sample Output

yes

no

yes

Source

University of Waterloo Local Contest 2002.09.21

Recommend

LL

题解：第一行给测试询问数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
");
69                 else
70                     printf("no
");         
71         }
72      } 
73   //   system("pause");
74     return 0;
75 }