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 }

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 }

相关推荐