牛牛吃米粒

题目链接:nowcoder 225271

到主站看:https://blog.csdn.net/weixin_43346722/article/details/120505244

题目大意

给你一些数,从 ,但中间缺失了一些数,缺失的会告诉你是哪些。
问你是否能凑出数 s。

思路

你考虑都是 ,不难想到二进制。

那这些二进制是不会进位的,因为每个的个数都是

那我们就看每个缺失的是否恰好是 二进制上要的。
还有一种不行的情况就是 的位数大于 ,那后面大于的那些位就凑不了了。

代码

#include<map>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll unsigned long long

using namespace std;

ll n, k, s;
ll a[101];

int main() {
    scanf("%lld %lld %lld", &n, &k, &s);
    if (n != 64 && s > (1ll << n) - 1) {//处理这些数就算都有也构不成的情况(需要的位数更大)
        printf("NO");
        return 0;
    }
    for (int i = 1; i <= k; i++) {
        scanf("%lld", &a[i]);
        if ((s >> (a[i] - 1ll)) & 1) {//这个缺的恰好要用来拼
            printf("NO");
            return 0;
        }
    }
    printf("YES");

    return 0;
}