avatar
fireworks99
keep hungry keep foolish

2019牛客暑期多校训练营(第九场)D折半枚举

Description

给出N( <= 36)和一个sum值,给出N个数字,从中选几个和为sum

Analyze

所有数字都有1(选取)、0(不选取)两种选择,所有状态就是2 ^ 36种

枚举所有状态必然超时

我们发现,2 ^ 36,底数为2(0/1两种状态),幂不超过40而接近40

这些都指向->折半枚举

折半枚举适合的题目:每个数字(物品)只有选取与不选取两种选择,数字(物品)数目不超过40但接近于40(2 ^ 20可遍历)

所以要对 (N <=40 、 N:0/1)敏感,反应出这是折半枚举

Code

#include <set> #include <map> #include <stack> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <bitset> #include <string> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> #define eps 1e-8 #define PI acos(-1.0) #define ll long long using namespace std; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; #define Close ios::sync_with_stdio(false); #define Debug cout << "-----------------" << '\n'; int n; ll num, a[40]; bool vis[40]; struct node { vector<int> c; ll sum; bool operator<(const node g)const { return sum < g.sum; } } e[1 << 19]; ll e_copy[1 << 19]; int main() { scanf("%d%lld", &n, &num); for(int i = 0; i < n; ++i) scanf("%lld", &a[i]); int mid = n / 2; for(int i = 0; i < (1 << mid); ++i) { for(int j = 0; j < mid; ++j) if(i >> j & 1) { e[i].c.push_back(j); e[i].sum += a[j]; } } sort(e, e + (1 << mid)); int idx = 1; for(int i = 1; i < (1 << mid); ++i) if(e[i - 1].sum < e[i].sum) e_copy[idx++] = e[i].sum; node tem; int ans; for(int i = 0; i < 1 << (n - mid); ++i) { tem.sum = 0; tem.c.clear(); for(int j = 0; j < n - mid; ++j) if(i >> j & 1) { tem.c.push_back(j); tem.sum += a[j + mid]; } if(tem.sum <= num) { int pos = lower_bound(e_copy, e_copy + idx, num - tem.sum) - e_copy; if(pos != (1 << mid) && e_copy[pos] + tem.sum == num) { ans = pos; break; } } } int sz = tem.c.size(); for(int i = 0; i < sz; ++i) vis[ tem.c[i] + mid ] = 1; sz = e[ans].c.size(); for(int i = 0; i < sz; ++i) vis[ e[ans].c[i] ] = 1; for(int i = 0; i < n; ++i) if(vis[i]) cout << '1'; else cout << '0'; cout << '\n'; return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101

Code of TLE(DFS暴搜)

#include <set> #include <map> #include <stack> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <bitset> #include <string> #include <cstring> #include <sstream> #include <cstdlib> #include <iostream> #include <algorithm> #include <functional> #define eps 1e-8 #define PI acos(-1.0) #define ll long long using namespace std; const int mod = 1e9 + 7; const int INF = 0x3f3f3f3f; #define Close ios::sync_with_stdio(false); #define Debug cout << "-----------------" << '\n'; int n, cnt = -1; bool vis[40], flag; ll sum, a[40]; void DFS(ll rest) { cnt++; if(rest == 0 || flag == 1) { flag = 1; cnt--; return ; } if(cnt >= n || rest < 0) { cnt--; return ; } vis[cnt] = 1; rest -= a[cnt]; DFS(rest); if(flag) { cnt--; return ; } vis[cnt] = 0; rest += a[cnt]; DFS(rest); cnt--; } int main() { scanf("%d%lld", &n, &sum); for(int i = 0; i < n; ++i) scanf("%lld", &a[i]); flag = 0; memset(vis, 0, sizeof(vis)); ll rest = sum; DFS(rest); for(int i = 0; i < n; ++i) if(vis[i]) cout << '1'; else cout << '0'; cout << '\n'; return 0; }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
Site by Baole Zhao | Powered by Hexo | theme PreciousJoy