首页 > 代码库 > Happy Matt Friends (DP)

Happy Matt Friends (DP)

2024-08-05 19:09:31   222人阅读

Happy Matt Friends

Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 510000/510000 K (Java/Others)
Total Submission(s): 418    Accepted Submission(s): 159


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 33 31 2 3
 

 

Sample Output
Case #1: 4Case #2: 2
Hint
In 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.
 
 
题意：
　　matt有N个朋友，现在需要从中选出n个(0<=n<=N)，使得每个朋友的ki值，异或结果（^）大于等于M。
思路：
　　首先注意题目数据范围： N<=40   M<=10^6
　　先排除暴力枚举的情况，
dp思路：
　　与背包类似：  考虑第i+1个人，选或不选
　　f[i][j]表示前i个人，选择其中k个（k<=i），使得异或结果为j。
　　递推式：
　　　　不选第i个人：  f[i+1][j] += f[i][j];   // 这里ans不进行累加，因为两种情况为同一种情况！ 
　　　　选择第i个人：  f[i+1][j^a[i]]  +=  f[i][j];此时，如果当前异或结果（j^a[i]）>=M， 则加入最终ans中： ans += f[i][j];
 
·注意： 本题也可以全部计算出 f[i][j]，使用双重循环，求sum{f[n][j](j>=m)}，即为结果。
 
AC Code:
////  main.cpp//  20141104////  Created by songjs on 14-11-4.//  Copyright (c) 2014年 songjs. All rights reserved.//#include <iostream>#include <stdio.h>#include <algorithm>#include <cstring>#include <string.h>#include <math.h>#include <queue>#include <stack>#include <stdlib.h>#include <map>using namespace std;#define LL long long #define sf(a) scanf("%d",&(a));#define inf 2e9#define INF 2147483647#define N (1<<20)#define PI 3.141592653#define EPS 1e-8#define maxc (1<<20)int f[42][N];int a[41];int main(){    int T;int k=1;    scanf("%d",&T);    while(T--){        int n,m;        scanf("%d %d",&n,&m);        for(int i=0;i<n;i++){            scanf("%d",&a[i]);        }        memset(f,0,sizeof(f));        f[0][0]=1;        LL num=0;        if(m==0) num++;        for(int i=0;i<n;i++){            for(int j=0;j<maxc;j++)            {                //不选的时候，  当前选择状况没变， 不需要 num 加上相应情况值。                f[i+1][j] += f[i][j];                int t = j^a[i];                f[i+1][t] += f[i][j];                if(t >= m) num+=f[i][j]; //注意这里是增加的f[i][j] !!! 把每次累加的加入进来即可！            }        }        printf("Case #%d: ",k++);        printf("%I64d\n",num);    }    return 0;}

 

对  if(m==0) num++;  的理解：（个人理解，如果不对欢迎大家纠错！！）

　　当m为0的时候，一个人都不选，可以为一种情况，加上这种情况。（当m不为0的时候，至少需要选择1个人。）

初始化 f[0][0] = 1; 的理解：

　　前0个人，异或结果为0时，为一种情况，结果为1.（即上面提到的）

　　同时这里因为双重for循环中每次加的都是f[i+1][j]，所以不会计算重复！

　

 

 

 

Happy Matt Friends (DP)


联系
我们