题解：CF1819D Misha and Apples

hoko · 2025-08-19 10:24:07 · 题解

题目传送门

题目大意

给出 n 个集合 S_i，每个集合有一个大小 siz_i 和集合中的数，如果 siz_i=0 表示这个集合可以为 1\sim m 的任意可空子集。现在有一个操作，从第一个集合开始，依次把集合中的数存到一个可重集 S 中，如果这个集合中有相同的元素，则情况集合，问怎么安排 siz_i=0 的集合，使得做完所有的操作后，集合 S 的大小最大。

解题思路

我们考虑贪心，我们定义 f_i 为以第 i 位为结尾，上一次清空的位置最早可以再哪一位。而 flag_i 表示第 i 位是否可以被清空，pos_i 记录集合中每一个数字最晚出现的位置，maxn 表示当前集合中所有数字中最晚出现的位置。

很明显答案就是区间 (f_n,n] 中所有集合的 siz 之和。如果这段区间中有 siz_i=0 的位置，那么答案就是 m，因为我们可以让 siz_i=0 的集合为 1\sim m 的任意可空子集。

现在考虑怎么求 f_i，我们先转移 flag_i。

• 如果上一次清空的位置也就是 f_{i} < maxn，那么说明第 i 个位置一定会被清空，因为出现了重复的数字，所以 flag_i=1。
• 如果 f_{i}\ge maxn 并且在 (f_{i},i] 这段区间内存在 siz_i=0 的集合，那么 flag_i=1。
• 否则 flag_i=0。

判断一个区间内是否有 siz_i=0 的集合，我们可以用前缀和维护。

现在考虑如何转移 f_{i+1}。

• 首先继承上一次最晚清空的位置，可以证明这个清空位置是不降的，f_{i+1}=f_{i}
• 如果 f_{i+1}<maxn，那就让 f_{i+1}=maxn，因为我们要求的是最晚清空的位置尽可能的早，如果 f_{i+1}<maxn，那么在 i 位置一定会被清空，所以 f_{i+1} 可以直接跳到 maxn。
• 之后我们要找到一个最先 flag_{f_{i+1}}=1 的位置，说明这个位置可以被清空，而且从这个位置到 i+1 中途不会出现有位置被清空的情况，且一定满足最早。所以 f_{i+1} 要跳到这个位置。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=510101;
ll T,n,m,siz[N],sum[N],pos[N],flag[N],f[N];
vector<ll>g[N];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll T;
    cin>>T;
    while(T--){
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>siz[i];
            if(!siz[i])sum[i]=1;
            sum[i]+=sum[i-1];
            for(int j=1;j<=siz[i];j++){
                ll x;
                cin>>x;
                g[i].push_back(x);
            }
        }
        ll h=0;
        flag[0]=1;
        for(int i=1;i<=n;i++){
            ll maxn=0;
            for(int j=0;j<siz[i];j++)maxn=max(maxn,pos[g[i][j]]);
            for(int j=0;j<siz[i];j++)pos[g[i][j]]=i;
            if(f[i-1]<maxn)flag[i]=1;
            else if(maxn<=f[i-1]&&sum[i]-sum[f[i-1]])flag[i]=1;
            f[i]=f[i-1];
            while(!flag[f[i]]||f[i]<maxn)f[i]++;
        }
        if(sum[n]-sum[f[n]])cout<<m<<"\n";
        else{
            ll ans=0;
            for(int i=f[n]+1;i<=n;i++)ans+=siz[i];
            cout<<ans<<"\n";
        }
        for(int i=0;i<=n;i++){
            for(int j=0;j<siz[i];j++)pos[g[i][j]]=0;
            sum[i]=siz[i]=flag[i]=f[i]=0;
            g[i].clear();
        }
    }
    return 0;
}