CFdiv2-Two Pizzas-(预处理+状态压缩)

F

题意：
就是给你n个人，每个人喜欢一组数字。然后现在有m个披萨，每个披萨就包含一组数字。一个人满意的条件是，选择的披萨中包含的所有数字，可以组成自己喜欢的那一组。 每个披萨有各自的价钱。现在让你选择两个披萨，尽量让最多的人满意，当满意人数相同的时候，尽量花的钱最小。现在问你选哪两个披萨？n和m都是1e5，不过每个人喜欢的一组数字最多9个，每个数字也<=9，披萨包含的数字也一样。

思考：

1. 看完题就感觉这题目描述的，无语。然后人和披萨都很多，刚开始我还没看清每个人最多喜欢9个数，喜欢的数字也很小，就感觉这怎么做，又不能枚举，难道是先选一个披萨再怎么怎么样？然后还是不行，然后才发现数据范围很小。
2. 既然看到了数据范围很小才9个，又是那种思想，只要数据很小，我就可以二进制枚举。所以每个人的状态我可以都压缩成个数字，然后最多也就2⁹ = 512个状态，每个状态多少人就行了。对于披萨呢，如果状态相同的话，我肯定选价钱最小的呀，所以和昨天的绵阳题一样，相同状态的取最优的。
3. 那么我就可以任意枚举两种披萨状态，看看这两个披萨组成的状态，可以包含多少状态。然后包含的所有状态的人都可以算上。那么这里该怎么操作，复杂度到底是多少？这里说3种方法：
   第一种：枚举两种披萨后，看看现在的值是多少，比如为sum，从0到sum枚举一下这个状态i，然后再看看i的某一位如果为1并且sum没有1的话就不行，如果都有就可以，跑完之后ans += cnt[i]。但是这个复杂度很大 = 51251251210 = 1e9了。行不通，我发现我根本没必要那么复杂呀，我先把sum里面是1的位取出来，再二进制枚举每个1是否取就好了。所以有了第二种方法：
   第二种：我先把sum里面是1的位取出来，再二进制枚举每个1是否取这一位，然后ans += cnt[res]。
   第三种：枚举披萨1的状态a和匹萨2的状态b后，再枚举人的状态i，如果i&(a|b)==i。也就是i所有1的位a或者b有，那么这个状态i就可以取。复杂度512512*512 = 2e7。
4. 然后提交发现wa了一个点，就是如果相同状态的披萨，你只保留了花费最小的那个。如果披萨1就可以满足所有人的状态，但是别的状态披萨又都很贵，和披萨1相同状态的花费虽然比现在的大一点，但是还是比别的状态的披萨便宜。所以这里最小的花费你就不出来了。所以先枚举选哪一个披萨，然后再选择一个最便宜的披萨，他俩组合就可以了。然后再枚举选两个披萨的情况。
5. 还有要注意的一点就是，一般二进制枚举的时候最好都从第0位开始，因为有时候你不从第0位，把第0位空下了，以后你枚举某些东西的时候，可能就得多枚举一倍。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 2e5+10,M = 2010;

struct Node{
	int a,b,c;
}node[N];

int T,n,m,k;
PII va[N];
int vb[N];
int idx1,idx2;

map<int,int > cnt;
map<int,PII > mp;

int get(int i,int j)
{
	int sum = (node[i].a|node[j].a),ans = 0;
	idx2 = 0;
	for(int j=1;j<=9;j++) if(sum>>j&1) vb[++idx2] = j;
	for(int i=0;i<(1ll<<idx2);i++)
	{
		int res = 0;
		for(int j=0;j<idx2;j++)
		{
			if(i>>j&1) res |= (1ll<<vb[j+1]);
		}
		ans += cnt[res];
	}
	return ans;
}

signed main()
{
	IOS;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>k;
		int sum = 0;
		while(k--)
		{
			int x;
			cin>>x;
			sum += (1ll<<x);
		}
		cnt[sum]++;
	}
	for(int i=1;i<=m;i++)
	{
		int c;
		cin>>c>>k;
		int sum = 0;
		while(k--)
		{
			int x;
			cin>>x;
			sum += (1ll<<x);
		}
		va[i] = {c,i};
		if(!mp.count(sum)) mp[sum] = {c,i};
		else if(mp[sum].fi>c) mp[sum] = {c,i};
	}
	for(auto t:mp) node[++idx1] = {t.fi,t.se.fi,t.se.se};
	int maxn = 0,res = inf,anw1 = 0,anw2 = 0;
	sort(va+1,va+1+m);
	for(int i=1;i<=idx1;i++)
	{
		int renshu = get(i,i);
		int huafei = node[i].b,t1 = node[i].c,t2 = 0;
		for(int j=1;j<=m;j++)
		{
			if(va[j].se!=node[i].c)
			{
				huafei += va[j].fi;
				t2 = va[j].se;
				break;
			}
		}
		if(maxn<renshu)
		{
			maxn = renshu;
			res = huafei;
			anw1 = t1,anw2 = t2;
		}
		else if(maxn==renshu&&res>huafei)
		{
			res = huafei;
			anw1 = t1,anw2 = t2;
		}
	}
	for(int i=1;i<=idx1;i++)
	{
		for(int j=i+1;j<=idx1;j++)
		{
			int sum = get(i,j);
			if(maxn<sum)
			{
				maxn = sum;
				res = node[i].b+node[j].b;
				anw1 = node[i].c,anw2 = node[j].c;
			}
			else if(maxn==sum&&res>node[i].b+node[j].b)
			{
				res = node[i].b+node[j].b;
				anw1 = node[i].c,anw2 = node[j].c;
			}
		}
	}
	cout<<anw1<<" "<<anw2<<"\n";
	return 0;
}
/* 第一种方法超时
int get(int i,int j)
{
	int sum = (node[i].a|node[j].a),ans = 0;
	for(int i=0;i<=sum;i++)
	{
		int res = 0,suc = 1;
		for(int j=1;j<=9;j++)
		{
			if((i>>j&1)&&!(sum>>j&1))
			{
				suc = 0;
				break;
			}
			if((i>>j&1)&&(sum>>j&1)) res += 1ll<
/*第二种方法
int get(int i,int j)
{
	int sum = (node[i].a|node[j].a),ans = 0;
	idx2 = 0;
	for(int j=1;j<=9;j++) if(sum>>j&1) vb[++idx2] = j;
	for(int i=0;i<(1ll<>j&1) res |= (1ll<
/*第三种方法
int get(int i,int j)
{
	int sum = (node[i].a|node[j].a),ans = 0;
	for(int i=0;i<(1ll<<9);i++)
	{
		if((i&sum)==i) ans += cnt[i];
	}
	return ans;
}
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173

总结：
多多思考。