【每日一题】2021年5月7日题目 奇怪的背包问题增加了

题号 NC204441
名称H-奇怪的背包问题增加了
来源 [牛客小白月赛23]

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

有一个容量为的背包，和m件物品，第i件物品的体积为，你需要从中选出若干件，使得选出的物品的体积恰好等于背包容量。这些物品有一个奇怪的特性，那就是，其中，即所有都是2的幂。

样例

输入
2
4
29 1 28 28
7
0 0 1 2 3 4 15
输出
1011
impossible

算法1

(数学)

分析

题目要求我们从一堆数中找一堆数能恰好相加成

我们发现的二进制表示只有一位是1

现在有两个数和

如果,则 （可以得到二进制表示只有一位是1的数）

如果则（不可以得到二进制表示只有一位是1的数）

所以如果有一堆2的次方数，其中存在一些无法找到配对的数(指数相同的数)那么他们对于求取答案是没有作用的

求解

我们用一个数据结构维护这些数让我们可以快速找到相同的数（只要用能动态维护这些数从小到大排列的数据结构，然后找相邻的即可）

我们可以用小根堆或者set（这里用堆）

1. 循环只要堆的大小>=2就不断执行如下操作
2. 每次取堆顶的两个元素判断值的大小是否相同
3. 如果相同将这两个数合并的结果重新放入堆中(合并就是指数+1)
4. 不相同就将大的那个元素重新放入堆中，舍弃小的
5. 如果堆顶元素等于30了可以直接退出循环

最后判断堆顶元素是否等于30，等于30有解否则无解

求方案

我们再记录元素值的同时维护每个元素并查集所在连通块的根节点是多少

每次合并结果同时用并查集将两个元素合并

最后根据堆顶元素（有解的前提下）的根节点编号判断哪些元素在这个连通块中

联通块的元素就是需要选择的元素

时间复杂度

参考文献

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <queue>
#include <set>
#include <bitset>
#include <cmath>
#include <map>

#define P 131

#define lc u << 1
#define rc u << 1 | 1

using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 100010;
int p[N];
int n;

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++ ) p[i] = i;
    priority_queue<PII,vector<PII>,greater<PII>> heap;
    for(int i = 1;i <= n;i ++)
    {
        int k;
        scanf("%d",&k);
        heap.push(make_pair(k,i));
    }
    while(heap.size() > 1)
    {
        PII a = heap.top();
        heap.pop();
        if(a.first == (heap.top()).first)
        {
            a.first ++;
            p[find((heap.top()).second)] = find(a.second);
            heap.pop();
            heap.push(a);
        }
        if((heap.top()).first == 30) break; 
    }
    if((heap.top()).first != 30) puts("impossible");
    else
    {
        int anc = (heap.top()).second;
        for(int i = 1;i <= n;i ++)
            if(find(i) == find(anc))
                printf("1");
            else 
                printf("0");
        puts("");
    }
}

int main()
{
    int T = 1;
    // init(100000);
    scanf("%d",&T);
    while(T --)
    {
        // scanf("%lld%lld",&n,&m);
        solve();
        // test();
    }
    return 0;
}