题解 P7280 【[COCI2020-2021#4] Pizza】

· · 题解

思路

正解（?）：桶（?）

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

由于数据范围小的很 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);
}

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