牛牛吃米粒

NC225271. 牛牛吃米粒

描述

牛牛很喜欢吃米饭，他的一顿饭是有 s 个米粒组成。一个偶然的机会，他找到了一条直线，这条直线上有 n 个格子，第一个格子有1个米粒，第二个格子有2个米粒，第三个格子有4个米粒……依次类推，第 n 个格子有 2^n-1个米粒。但由于有 k 个格子存在问题，会导致放在这些格子上的米粒全部丢失。现在想从剩下的 n-k 个格子中选出某些格子，拿走选中的格子上的全部米粒，问是否有恰好选出s个米粒的方案？

输入描述

第一行三个整数 n 、 k 、s
第二行 k 个整数， ,,..., 表示有问题的格子的标号(格子标号从1开始)

输出描述

能组成一个数量为 s 的米粒堆输出  YES，否则输出  NO

示例1

输入:

6 0 20

输出:

YES

示例2

输入:

7 2 35
2 3

输出:

NO

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2021-09-24 22:37:58

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
signed main(){
	ll n,k,s;
	cin>>n>>k>>s;
	while(k--){
		ll a;
		cin>>a;
		if(s>>(a-1)&1) return puts("NO"),0;
	}
	puts("YES");
}

Python3 解法, 执行用时: 42ms, 内存消耗: 7004K, 提交时间: 2021-09-24 19:32:11

n, k, s = map(int, input().split())
count = (1 << n) - 1;
if k != 0:
    for missing in map(int, input().split()):
        count ^= 1 << (missing - 1)
print('YES' if (count & s) == s else 'NO')