hdu 5119 dp

忘是亡心i 2022-08-08 14:52 191阅读 0赞

# Happy Matt Friends #

**Time Limit: 6000/6000 MS (Java/Others)    Memory Limit: 510000/510000 K (Java/Others)  
Total Submission(s): 1349    Accepted Submission(s): 534**

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 ≤ 10 6).  
  
In the second line, there are N integers ki (0 ≤ k i ≤ 10 6), 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

2
    3 2
    1 2 3
    3 3
    1 2 3

Sample Output

Case #1: 4
    Case #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.

Source

[2014ACM/ICPC亚洲区北京站-重现赛（感谢北师和上交）][2014ACM_ICPC_-]  
  
  
题意： 给你n个数，随意选择一些数进行异或，如果异或的值大于等于m，那么Matt就赢，输出Matt赢的方案数。  
  
分析： 虽然只有40个数，但是这40个数的组合数太多了，所以不能暴力。仔细一想可以利用dp记录前面所有方案数的结果（即前面所有排列组合的异或值和对应的数目），等到第i项的时候在用第i项分别与这些结果异或。  
  
  
开始用的map，感觉太慢了。。5500ms险过。

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    const int N=100010;
    
    map<int,ll> dp;
    pii v[1000010];
    map<int,ll> :: iterator it;
    int a[44];
    
    int main()
    {
        int T=in();
        int ii=1;
        while(T--)
        {
            dp.clear();
            dp[0]=1;
            int n=in(),m=in();
            for(int i=0;i<n;i++)
            {
                scanf("%d",&a[i]);
            }
            for(int i=0;i<n;i++)
            {
                int cnt=0;
                for(it=dp.begin();it!=dp.end();it++)
                {
    
                     v[cnt++]=(pii((it->first^a[i]),it->second)); //不能在这里直接更改dp，先把结果存在数组中
    
                }
                for(int j=0;j<cnt;j++)
                {
                    dp[v[j].first]+=v[j].second;     //从数组中更新dp
    
                }
            }
            ll ans=0;
            for(it=dp.lower_bound(m);it!=dp.end();it++)
            {
                ans+=it->second;
                //cout<<it->first<<" "<<it->second<<endl;
            }
            printf("Case #%d: ",ii++);
            printf("%I64d\n",ans);
        }
        return 0;
    }

后来果断抛弃了map，用数组做，效率急速提升！600+ms；

#include<bitset>
    #include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=1<<20;
    
    int dp[N];
    pii v[N];
    int a[44];
    
    
    int main()
    {
        int T;
        scanf("%d",&T);
        int ii=1,cnt,n,m;
        while(T--)
        {
    
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&a[i]);
            }
            mem(dp,0);
            dp[0]=1;
            for(int i=1;i<=n;i++)
            {
                cnt=0;
                for(int j=0;j<N;j++)
                {
                    if(dp[j]) v[cnt++]=pii(j^a[i],dp[j]);
                }
                for(int j=0;j<cnt;j++)
                {
                    dp[v[j].first] += v[j].second;
                }
            }
            ll ans=0;
            for(int i=m;i<N;i++)
            {
                ans+=dp[i];
            }
            printf("Case #%d: %I64d\n",ii++,ans);
    
        }
        return 0;
    }

[2014ACM_ICPC_-]: http://acm.hdu.edu.cn/search.php?field=problem&key=2014ACM%2FICPC%D1%C7%D6%DE%C7%F8%B1%B1%BE%A9%D5%BE-%D6%D8%CF%D6%C8%FC%A3%A8%B8%D0%D0%BB%B1%B1%CA%A6%BA%CD%C9%CF%BD%BB%A3%A9&source=1&searchmode=source