自动搬运

查看原文

来自洛谷，原作者为

	银河AI **

搬运于2025-08-24 22:28:21，当前版本为作者最后更新于2021-01-22 21:28:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

正解（?）：桶（?）

看完题目后，第一眼就发现，这不就是道水模拟吗（雾）

由于数据范围小的很 $n\le100$

所以我们考虑用一个桶来记录 $Mirko$ 不喜欢的配料，代码如下：

for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[a[i]]=1;

接下来，当输入披萨的配料时，用一个标记来说明当前披萨有无 $Mirko$ 不喜欢的配料，如果当前披萨无他不喜欢的配料，那么就ans++

for(int j=1;j<=k;j++){
	scanf("%d",&x);
	if(t[x]) trap=1;
}

没错就是这么简单，接下来放出AC代码

时间复杂度 $O(mk+n)$，空间复杂度 $O(max(A_{i}))$

AC代码（有注释）

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
int a[105],b[105],t[105];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),t[a[i]]=1;//输入Mirko不喜欢的配料，并用桶标记 
	scanf("%d",&m);
	for(int i=1;i<=m;i++){
		int k,x,trap=0;scanf("%d",&k);//k代表当前披萨有几个配料，x代表是哪种配料，trap标记当前披萨有无Mirko不喜欢的配料 
		for(int j=1;j<=k;j++){
			scanf("%d",&x);
			if(t[x]) trap=1;//如果当前配料Mirko不喜欢，则标记为1
		}
		if(trap==0) ans++;//如果没有被标记，则ans++ 
	}
	printf("%d",ans);
}

蒟蒻的第一篇题解，望管理员通过