hdu 5339 Untitled

　　这题很明显是签到题，可我比赛时却没做出，赤裸裸的爆零了，真悲剧……

　　看了题解后才知道直接暴搜就行，只是需要把它们从大到小排序后再搜，我当时就没想到。。。不想再多说了

一开始我直接枚举所有情况：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int b[23],a;
 8 
 9 inline bool ok(const vector<int> &v, int a) {
10     int len = v.size();
11     for(int i = len - 1; i >= 0; --i)
12         if(a % v[i] == 0)   return 1;
13         else    a %= v[i];
14     return 0;
15 }
16 
17 int main() {
18     int t,n;
19     scanf("%d",&t);
20     while(t--) {
21         scanf("%d %d",&n,&a);
22         for(int i = 0; i < n; ++i)
23             scanf("%d",b + i);
24         sort(b, b + n);
25         int limit = (1 << n) - 1;
26         bool flag = 0;
27         for(int i = 1; i <= limit; ++i) {
28             vector<int> v;
29             for(int j = 0; (1 << j) <= i; ++j)
30                 if(i & (1 << j))    v.push_back(b[j]);
31             if(ok(v, a)) {
32                 printf("%d
",v.size());
33                 flag = 1;
34                 break;
35             }
36         }
37         if(flag == 0)   puts("-1");
38     }
39     return 0;
40 }

View Code

　　可是却发现 700+ms，出奇的慢，于是我试下直接的深搜，竟然 78ms，果然够快！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<vector>
 4 #include<algorithm>
 5 using namespace std;
 6 const int inf = 0x3fffffff;
 7 
 8 int b[23],ans,n;
 9 
10 void dfs(int id, int num, int a) {
11     if(a == 0) {
12         ans = min(ans, num);
13         return ;
14     }
15     if(id > n)  return ;
16 
17     dfs(id + 1, num + 1, a % b[id]);
18     dfs(id + 1, num, a);
19 }
20 
21 inline bool cmp(int x, int y) {
22     return x > y;
23 }
24 
25 int main() {
26     int t, a;
27     scanf("%d",&t);
28     while(t--) {
29         scanf("%d %d",&n,&a);
30         for(int i = 1; i <= n; ++i)
31             scanf("%d",b + i);
32         sort(b + 1, b + n + 1, cmp);
33         ans = inf;
34         dfs(1, 0, a);
35         printf("%d
",ans == inf ? -1: ans);
36     }
37     return 0;
38 }

View Code

　　在网上看到有个位压的比我第一个版本快多了：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 int const MAX = 1 << 22;
 6 int const INF = 0x3fffffff;
 7 int b[25], sta[MAX];
 8 
 9 int lowbit(int x)
10 {
11     return x & (-x);
12 }
13 
14 bool cmp(int a, int b)
15 {
16     return a > b;
17 }
18 
19 int main()
20 {
21     int T;
22     scanf("%d", &T);
23     while(T --)
24     {
25         memset(sta, 0, sizeof(sta));
26         int n, a;
27         scanf("%d %d", &n, &a);
28         for(int i = 1; i <= n; i++)
29             scanf("%d", &b[i]);
30         sort(b + 1, b + n + 1, cmp);
31         for(int i = 1; i <= n; i++)
32             sta[1 << (i - 1)] = b[i];
33         int cnt, ans = INF;
34         for(int i = 1; i < (1 << n); i++)
35         {
36             int tmp = a;
37             cnt = 0;
38             for(int j = i; j > 0; j -= lowbit(j))
39             {
40                 tmp %= sta[lowbit(j)];
41                 cnt ++;
42             }
43             if(tmp == 0)
44                 ans = min(ans, cnt);
45         }
46         if(ans == INF)
47             printf("-1
");
48         else
49             printf("%d
", ans);
50     }
51 }

View Code

　　虽然爆零，但比赛还是得坚持打。