首页 > 代码库 > 【SRM】600#div2 B 枚举

【SRM】600#div2 B 枚举

2024-07-17 14:12:38   218人阅读

题意：有一个集合和一个目标态goal，现在的状态是X=0，现在在集合中有一些数，经过每次X=X|a[i] 这种异或运算后，能使得X=goal，即达到目标态。问：最少删除集合中多少个元素，使得初始X=0，不能达到目标态。

思路：SRM600 #div2 的A题做了好一会儿，主要是不知道怎么直接计算出那个shuttle的数量，突然发现暴力枚举可行。

因此做B题的时候也受枚举思想的影响。刚开始我想枚举子集再决定删除多少个，但真不好决定。接着又想枚举goal的每一位（二进制），显然可行！但是由于思路不严密，也好一会儿没得到正确答案。final思路整理：对goal的每一位，分两种情况：1，为0时，则集合中那些这位为1的数字一定可以不删；2，为1时，则集合中那些这位为1的数字可能都得删（原因：把这位的有1的数都给删了，他一定不能到达目标态）。但是这样还不够！我们得先把一定可以不删的数字排除了，再来枚举第二种情况，然后取一下为1位需要删的最小值。

#include<bits/stdc++.h>using namespace std;class ORSolitaireDiv2{public:    int getMinimum(vector <int>, int);};int ORSolitaireDiv2::getMinimum(vector <int> num, int aim){    //枚举aim的每一位，要先确定那些一定可以不删的，再来确定那些最少删多少的    int ans=33;    bool f[33];    int cnt=0;    memset(f,false,sizeof(f));    for(int i=0;i<33;i++)        if(!(aim&(1<<i)))    {        for(int j=0;j<num.size();j++)            if(num[j]&(1<<i)) f[j]=true;    }    for(int i=0;i<33;i++)        if(aim&(1<<i))    {        cnt=0;        for(int j=0;j<num.size();j++)            if((num[j]&(1<<i))&&!f[j]) cnt++;        ans=min(ans,cnt);    }    cnt=0;    for(int i=0;i<num.size();i++)        if(f[i]) cnt++;    ans=min((int)num.size()-cnt,ans);    return ans;}

 


联系
我们