题意:
超市里共有N件商品,每件商品有一个价格Pi和Ci个功能,功能1<=Fi,j<=M,问是否存在一件商品是另一件商品的上位替代:i是j的上位替代指 Pi<Pj且i具有j的所有功能,或Pi==Pj时且i拥有j的所有功能的前提下i还具有至少一个j没有的功能。
bitset类似于数组,但每个元素只能是0或1且仅用1bit的空间
1.bitset<4> a; //申请一个名为a长度为4的bitset,默认每位为0
2.bitset<8> b(12); //长度为8,将12二进制保存在b中,前面位补0
3.string s = "10010";
bitset<10> c(s); //长度为10,将s二进制保存在c中,前面位补0
bitset<8> s("10011011");
s.count(); //5 返回s中1的个数,s中有5个
s.size(); //8 返回s的位数,s为8位
s.test(0); //true 检查下标为0的元素(最低位)是0还是1,0返回flase,1返回true
s.any(); //true 检查s中是否有1
s.none(); //flase 检查s中是否没有1
s.all(); //flase 检查s中是否全为1
s.flip(); //01100100 不传参则将s的每一位取反
s.flip(2); //10011111 传参则将s的下标为2处取反
s.set(); //11111111 不传参则将s的每一位 置1
s.set(3); //10011011 传一个参数将s的下标为3的位 置1
s.set(3,0); //10010011 传两个参数将s的下标为3的位 置0(第二个参数)
s.reset(); //00000000 不传参则将s的每一位 置0
s.reset(3); //10010011 传参则将s的下标为3的位 置0
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int p[N]; //money
bitset<101>a[N];
void solved()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, c; i <= n; ++i)
{
scanf("%d%d", &p[i], &c);
for (int j = 1, x; j <= c; ++j)
{
scanf("%d", &x);
a[i][x] = 1;
}
}
for(int i = 1; i <= n; i ++)
{
for(int j = 1; j <= n; j ++)
{
if(i == j) continue;
if(p[i] >= p[j])
{
bitset<101>t = a[i] & a[j]; //全1才为1
/*
2.j必须有i的所有功能,因为全1才是1,所以如果满足,t需要等于a[i]
3.必须保证价格大于,或者,j比i功能多,只要t!=a[j],就可以满足这个情况
因为如果不满足这个情况,a[i]==a[j],所以在满足2的同时,t != a[j],
就一定可以满足
*/
if(t == a[i] && (p[i] > p[j] || t != a[j]))
{
cout << "Yes" << endl;
return;
}
}
}
}
cout << "No" << endl;
}
int main()
{
solved();
return 0;
}