题解：AT_abc402_c [ABC402C] Dislike Foods

yyycj · 2025-04-26 17:28:59 · 题解

题目简述

AtCoder 餐厅有 N 种食材，M 道菜，第 i 道菜由 K_{i} 种食材 A_{i,1} \sim A_{i,K_{i}} 组成。

Snuke 一开始讨厌所有 N 道食材，接下来 N 天，他将在第 i 天克服第 B_{i} 种食材，当一道菜品中的所有食材都被克服后，Snuke 可以吃这道菜。

求对于 i \in [1,n]，第 i 天可以吃几道菜。

主要思路

由于一道菜必须所有食材克服后才能吃，所以某道菜首次能吃的时间就是这道菜中的每种食材最后出现在 B 中的下标。

记录整数数组 cnt，cnt_{i} 表示有 cnt_{i} 道菜在今天被克服。记录完后，将 cnt 进行一次前缀和便是此题的答案。

AC Code

#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
typedef long double db;
const int N = 3e5 + 10;
const int INT_INF = 0x3f3f3f3f;
const ll LL_INF = 0x3f3f3f3f3f3f3f3f;
// ----------------------------

// ----------------------------
int pos[N], ans[N];
vector<int> vec[N];
// ----------------------------

int main() {
    int n, m, k, a, b; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> k;
        for (int _ = 1; _ <= k; _++) {
            cin >> a;
            vec[i].push_back(a);
        }
    }
    for (int i = 1; i <= n; i++) {
        cin >> b;
        pos[b] = i;
    }
    // ----------------------------
    int maxn;
    for (int i = 1; i <= m; i++) {
        maxn = 0;
        for (int j : vec[i]) maxn = max(maxn, pos[j]);
        ans[maxn]++;
    }
    // ----------------------------
    for (int i = 1; i <= n; i++) {
        ans[i] += ans[i - 1];
        cout << ans[i] << endl;
    }
    return 0;
}