专栏文章

题解：CF1819D Misha and Apples

hhoko
CF1819D题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio93par
此快照首次捕获于
2025/12/02 15:22
3 个月前
此快照最后确认于
2025/12/02 15:22
3 个月前
查看原文

题目传送门

题目大意

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

解题思路

我们考虑贪心，我们定义 fif_i 为以第 ii 位为结尾，上一次清空的位置最早可以再哪一位。而 flagiflag_i 表示第 ii 位是否可以被清空，posipos_i 记录集合中每一个数字最晚出现的位置，maxnmaxn 表示当前集合中所有数字中最晚出现的位置。
很明显答案就是区间 (fn,n](f_n,n] 中所有集合的 sizsiz 之和。如果这段区间中有 sizi=0siz_i=0 的位置，那么答案就是 mm，因为我们可以让 sizi=0siz_i=0 的集合为 1∼m1\sim m 的任意可空子集。
现在考虑怎么求 fif_i，我们先转移 flagiflag_i。
  • 如果上一次清空的位置也就是 fi<maxnf_{i} < maxn，那么说明第 ii 个位置一定会被清空，因为出现了重复的数字，所以 flagi=1flag_i=1。
  • 如果 fi≥maxnf_{i}\ge maxn 并且在 (fi,i](f_{i},i] 这段区间内存在 sizi=0siz_i=0 的集合，那么 flagi=1flag_i=1。
  • 否则 flagi=0flag_i=0。
判断一个区间内是否有 sizi=0siz_i=0 的集合，我们可以用前缀和维护。
现在考虑如何转移 fi+1f_{i+1}。
  • 首先继承上一次最晚清空的位置，可以证明这个清空位置是不降的，fi+1=fif_{i+1}=f_{i}
  • 如果 fi+1<maxnf_{i+1}<maxn，那就让 fi+1=maxnf_{i+1}=maxn，因为我们要求的是最晚清空的位置尽可能的早，如果 fi+1<maxnf_{i+1}<maxn，那么在 ii 位置一定会被清空，所以 fi+1f_{i+1} 可以直接跳到 maxnmaxn。
  • 之后我们要找到一个最先 flagfi+1=1flag_{f_{i+1}}=1 的位置，说明这个位置可以被清空，而且从这个位置到 i+1i+1 中途不会出现有位置被清空的情况，且一定满足最早。所以 fi+1f_{i+1} 要跳到这个位置。

代码

CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...