bitset容器有点类似于vector<bool>,但整体性能远优于vector和bool
它可以有效地优化 背包 的运行效率
此外,bitset也可以直接使用常规位运算符进行操作
> * 注意细节:初始化时,最右侧字符,会对应BITSET的最低位(下标为0的位)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例题.卡片之和(官方题库无此题)
题目描述
小明有 nnn 张数字卡片,第 i 张卡片上的数字为 aia_iai 。
对于每次询问,小明可以从这些卡片中任意选择若干张,每张卡片最多选择一次。请判断所选卡片上的数字之和能否恰好等于给定的目标值 xxx。
每次询问相互独立,不会消耗卡片。
特别地,可以一张卡片都不选,因此目标值 000 一定可以得到。
输入格式
第一行输入一个整数 nnn,表示数字卡片的数量。
第二行输入 nnn 个正整数 a1,a2...ana_1,a_2 ... a_na1 ,a2 ...an ,表示每张卡片上的数。
第三行输入一个整数 qqq,表示询问次数。
接下来 qqq 行,每行输入一个整数 xxx,表示本次询问的目标值。
输出格式
对于每次询问:
* 如果能够选择若干张卡片,使数字之和恰好为 xxx,输出 Yes;
* 否则输出 No。
每个询问的答案单独占一行。
输入输出样例
输入#1
输出#1
数据范围
对于全部测试数据:
1≤n≤5000,1≤ai≤105,1≤q≤105,0≤x≤1051≤n≤5000,1≤a_i≤10^5,1≤q≤10^5,0≤x≤10^51≤n≤5000,1≤ai ≤105,1≤q≤105,0≤x≤105。
所有输入均为整数。
* BITSET代码
* 背包代码
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
不喜勿喷~