锐客网

  1. 首页 > 睿知 > it技术 > >

Happy Matt Friends(DP)

IT知识friendFriendshappy

今日长缨在手，何时缚住苍龙。这篇文章主要讲述Happy Matt Friends(DP)相关的知识，希望能为你提供帮助。
Happy Matt Friends
Time Limit: 6000/6000 MS (java/Others)        Memory Limit: 510000/510000 K (Java/Others)
Total Submission(s): 3700        Accepted Submission(s): 1407



Problem Description
Matt has N friends. They are playing a game together.

Each of Matt’ s friends has a magic number. In the game, Matt selects some (could be zero) of his friends. If the xor (exclusive-or) sum of the selected friends’ magic numbers is no less than M , Matt wins.

Matt wants to know the number of ways to win.
 
 
Input
The first line contains only one integer T , which indicates the number of test cases.

For each test case, the first line contains two integers N, M (1 ≤ N ≤ 40, 0 ≤ M ≤ 106).

In the second line, there are N integers ki (0 ≤ ki  ≤ 106), indicating the i-th friend’ s magic number.
 
 
Output
For each test case, output a single line “ Case #x: y” , where x is the case number (starting from 1) and y indicates the number of ways where Matt can win.
 
 
Sample Input
23 21 2 3 3 31 2 3【Happy Matt Friends(DP)】 
 
Sample Output
Case #1: 4Case #2: 2   HintIn the ?rst sample, Matt can win by selecting: friend with number 1 and friend with number 2. The xor sum is 3. friend with number 1 and friend with number 3. The xor sum is 2. friend with number 2. The xor sum is 2. friend with number 3. The xor sum is 3. Hence, the answer is 4.   Source
2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）
 
 
//题意:第一行T,然后是2个整数 n,m ,然后给出n个数字，问这些数字任意组合，求异或和大于等于m的组合个数
t题解:暴力DP即可 dp[i][j] 为前 i 个数可以组成异或和等于 j 的个数
dp[i][j] = dp [i-1][j] + dp[i-1][j^num[i]]
可以滚动，可以不滚动

Happy Matt Friends(DP)

文章图片
Happy Matt Friends(DP)

文章图片
1 #include < iostream> 2 #include < stdio.h> 3 #include < string.h> 4 using namespace std; 5 #define LL long long 6 #define MX 1000005 7 8 int Scan() {//输入外挂 9int res = 0, flag = 0; 10char ch; 11if((ch = getchar()) == ‘-‘) flag = 1; 12else if(ch > = ‘0‘ & & ch < = ‘9‘) res = ch - ‘0‘; 13while((ch = getchar()) > = ‘0‘ & & ch < = ‘9‘) 14res = res * 10 + (ch - ‘0‘); 15return flag ? -res : res; 16 } 17 18 void Out(int a) {//输出外挂 19if(a < 0) { putchar(‘-‘); a = -a; } 20if(a > = 10) Out(a / 10); 21putchar(a % 10 + ‘0‘); 22 } 23 24 int n,m; 25 int dp[2][1< < 21]; // i 个数异或和为 j 个数 26 int num[MX]; 27 28 int main() 29 { 30int T; 31cin> > T; 32for(int cnt=1; cnt< =T; cnt++) 33{ 34n=Scan(),m=Scan(); 35for (int i=1; i< =n; i++) 36scanf("%d",& num[i]); 37memset(dp,0,sizeof(dp)); 38dp[0][0]=1; 39for (int i=1; i< =n; i++) 40{ 41for (int j=0; j< MX; j++) 42{ 43dp[i& 1][j]=dp[(i-1)& 1][j]+dp[(i-1)& 1][j^num[i]]; 44} 45} 46LL ans =0; 47for (int i=m; i< MX; i++) 48ans += dp[n& 1][i]; 49printf("Case #%d: %I64d\n",cnt,ans); 50} 51return 0; 52 }

View Code 

    推荐阅读


    上一篇：android不同机型上界面适配问题

    下一篇：Android攻城狮布局动画