Happy Matt Friends（HDU5119 + dp）

题目链接：

　　http://acm.hdu.edu.cn/showproblem.php?pid=5119

题目：

题意：

　　求选择任意个数，使其异或和大于等于m的方案数。

思路：

　　每个数有选和不选两种方案，显然是背包思想。dp[i][j]表示前i个物品异或和为j时的方案数，转移方程为dp[i][j] = dp[i-1][j] + dp[i-1][j^a[i]]。这题可以考虑用滚动数组滚动掉一维，当然了，不滚动也是可以过滴～

代码实现如下：

 

1 #include <set> 2 #include <map> 3 #include <deque> 4 #include <ctime> 5 #include <stack> 6 #include <cmath> 7 #include <queue> 8 #include <string> 9 #include <cstdio> 10 #include <vector> 11 #include <iomanip> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 using namespace std; 16 17 typedef long long LL; 18 typedef pair<LL, LL> pll; 19 typedef pair<LL, int> pli; 20 typedef pair<int, int> pii; 21 typedef unsigned long long uLL; 22 23 #define lson rt<<1 24 #define rson rt<<1|1 25 #define name2str(name)(#name) 26 #define bug printf("**********\n"); 27 #define IO ios::sync_with_stdio(false); 28 #define debug(x) cout<<#x<<"=["<<x<<"]"<<endl; 29 #define FIN freopen("/home/dillonh/CLionProjects/in.txt","r",stdin); 30 31 const double eps = 1e-8; 32 const int maxn = (1<<20) + 7; 33 const int inf = 0x3f3f3f3f; 34 const double pi = acos(-1.0); 35 const LL INF = 0x3f3f3f3f3f3f3f3fLL; 36 37 int t, n, m; 38 int a[45], dp[2][maxn]; 39 40 int main() { 41 #ifndef ONLINE_JUDGE 42 FIN; 43 #endif 44 int icase = 0; 45 scanf("%d", &t); 46 while(t--) { 47 scanf("%d%d", &n, &m); 48 int mx = 0, cnt = 0; 49 for(int i = 1; i <= n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]); 50 memset(dp, 0, sizeof(dp)); 51 dp[0][0] = 1; 52 while(mx) cnt++,mx >>= 1; 53 for(int i = 1; i <= n; i++) { 54 for(int j = 0; j <= (1<<cnt); j++) { 55 dp[i&1][j] = dp[(i-1)&1][j] + dp[(i-1)&1][j^a[i]]; 56 } 57 } 58 LL ans = 0; 59 for(int i = m; i < maxn; i++) ans += dp[n&1][i]; 60 printf("Case #%d: %lld\n", ++icase, ans); 61 } 62 return 0; 63 }

 

转载于:https://www.cnblogs.com/Dillonh/p/9747444.html

总结

以上是生活随笔为你收集整理的Happy Matt Friends（HDU5119 + dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。