首页 > 代码库 > topcoder srm: NumbersChallenge

topcoder srm: NumbersChallenge

2024-07-07 03:11:34   225人阅读

用bit mask来做枚举还挺方便的

这个大概是给你一个vector<int> array，求出这个array里任意几个元素加和所不能得到最小的整数。

元素个数最大20个，每个元素不超过100000

比如[1,2,4]，那么就应该返回8. （因为3=1+1, 5=1+4等等）

所以枚举这个array的所有子集求和，之后从1开始查看哪个数没有命中然后返回就好。

tc上给出的题解如下：

static const int MAX = 100000 * 20 + 1; 
bool poss[MAX];
 
int MinNumber(vector<int> S)
{
    fill(poss, poss + MAX, false);
    int n = S.size();
    // All subsets:
    for (int mask = 0; mask < (1<<n); mask++) {
        int sum = 0;
        for (int i = 0; i < S.size(); i++) {
            if (mask & (1<<i)) {
                sum += S[i];
            }
        }
        poss[sum] = true;
    }
    int x = 1;
    while (poss[x]) {
        x++;
    }
    return x;
}

我自己又用dp小优化了下

static const int MAX = 100000 * 20 + 1;
     int MinNumber(vector<int> array) {
        int len = array.size();
        vector<int> buf(1<<len,0);
        bool res[MAX];
        fill(res,res+MAX,false);
        for(int mask = 1;mask<1<<len;mask++) {
            int tmp = mask;
            int maxBit = 0;
            while(tmp>>1) {
                maxBit++;
                tmp = tmp>>1;
            }
            buf[mask] = array[maxBit]+buf[mask&~(1<<maxBit)];
            res[buf[mask]] = true;
        }
        for(int i=1;i<MAX;i++) {
            if(res[i]==false) {
                
                return i;
            }
            
        }
        return MAX;
    }

 


联系
我们