Misha and Apples
只能做做评分虚高的题了,头痛浪费了一节晚自习。
但是为什么机房的同学们都觉得2500~2800算水题呢?
最终的答案一定是 \([S_1,S_x]\) 被清空,\([S_{x+1},S_n]\) 被全部放入集合。
若 \(\exists i\in[x+1,n],k_i=0\),答案为 m,否则为 \(\sum_{i=x+1}^nk_i\)。
枚举到 i 时 x 的最小值,则上式的 x 即 i=n 时的 x。
设 \(f_i\) 表示加入 \(S_i\) 后集合是否能清空,\(ma\) 表示 \(S_i\) 中的数上一次出现最晚的位置。
设 \(x<ma\),此时 \([S_x,S_{i-1}]\) 加入 \(S_i\) 后可以清空,\(f_i=1\)。
否则如果 \(\exists j\in[x+1,i-1],k_j=0\),这个商店可以加入 \(S_i\) 中的数使其清空,\(f_i=1\)。
考虑 x 的移动,当 \(x<ma\) 或 \(f_x=0\) 时,x++。
#include<cstdio>
#include<vector>
#include<iostream>
using namespace std;
const int MAXN=2e5+5;
int T,n,m,wz,id[MAXN],pre[MAXN];
bool f[MAXN];
vector<int> v[MAXN];
int main(){
scanf("%d",&T);f[0]=1;
while(T--){
scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) f[i]=0;wz=0;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);v[i].clear();
pre[i]=pre[i-1]+(x==0);
for(int j=1,y;j<=x;j++){
scanf("%d",&y);id[y]=0;v[i].push_back(y);
}
}
for(int i=1;i<=n;i++){
int ma=0;
for(int j=0;j<v[i].size();j++){
int u=v[i][j];ma=max(ma,id[u]);id[u]=i;
}
f[i]=(wz<ma)||(pre[i]!=pre[wz]);
while(wz<ma||(!f[wz])) wz++;
}
if(pre[wz]!=pre[n]){printf("%d\n",m);continue;}
int tmp=0;
for(int i=wz+1;i<=n;i++) tmp+=(int)v[i].size();
printf("%d\n",tmp);
}
return 0;
}