自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:12:12，当前版本为作者最后更新于2019-10-02 21:14:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$\color{#00ff00}T2.\ Ethan\ and\ sets$

$\color{#00ff00}\text{题面}$

官方题解

$Sol\ 1\ :\ 20-50\ pts$

暴力求解，应该能拿到 $20\%$（毕竟是 $subtask$ 制）

（说不定用 $bitset$ 优化能拿到 $50\%$）

$Sol\ 2\ :\ 100\ pts$

$\large{Two-pointers}$

这题应该还算简单，$Two-pointers$ 模拟即可

直接上代码（详细注释）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,m,g,s[50005],cnt[1005],c[3005][1005],num[50005],p[50005];
bool found=0;
ll ansb=1e18,anss,ansl,ansr;
int main()
{
	cin>>n>>m>>g;
	for(int i=1;i<=g;i++){
		ll x;
		scanf("%lld",&x);
		p[x]=1;//标记为喜欢
	}
	for(ll i=1;i<=n;i++){
		scanf("%lld%lld",&s[i],&num[i]);
		for(ll j=1;j<=num[i];j++)
			scanf("%lld",&c[i][j]);
	}
	ll l=1,r=1,sum=0,sumb=0;//当前区间为 [l,r) , sum = [l,r) 的魔力值之和 , sumb = [l,r) 中不喜欢的数的个数
	while(l<=n){
		while(r<=n){
			bool flag=1,check=1;//flag: 是否有不喜欢的数 (1=NO,0=YES) , check: 是否全部包含了所有 Ethan 喜欢的数
			for(ll i=1;i<=num[r];i++)
				if(!p[c[r][i]])
					flag=0;
			for(ll i=1;i<=m;i++)
				if(p[i]&&!cnt[i])//喜欢但不包含的数
					check=0;
			if(check&&!flag)break;//如果包含了所有喜欢的数 , 且 [l,r-1] 比 [l,r] " 不喜欢的数的个数 " 少 ( 集合 r 有不喜欢的数 ) , 那就选 [l,r-1] , 退出
			for(ll i=1;i<=num[r];i++){//右端点往右移 , 加上集合 r 的所有属性
				if(!p[c[r][i]])sumb++;
				cnt[c[r][i]]++;
			}
			sum+=s[r];
			r++;//右端点 ++ 
		}
		bool check=1;//这边还要再判断一下是否有全部喜欢的数 , 可能是 r>n 从上一个 whlie 循环退出来的
		for(ll i=1;i<=m;i++)
			if(p[i]&&!cnt[i])
				check=0;
		if(check){
			found=1;//标记一下找到了
			if(ansb>sumb||sumb==ansb&&anss<sum)//如果满足更新条件
				ansb=sumb,anss=sum,ansl=l,ansr=r-1;//更新 
		}
		for(ll i=1;i<=num[l];i++){//左端点往右移 , 把集合 l 的所有属性减掉 ( 可以和上面的右端点往右移对比一下 )
			cnt[c[l][i]]--;
			if(!p[c[l][i]])sumb--;
		}
		sum-=s[l]; 
		l++;//左端点 ++
	}
	if(!found) puts("-1");//没找到输出 -1 
	else cout<<ansl<<" "<<ansr<<endl;
}
/*
3 3 2
1 2
5 2 1 2
5 2 1 2
5 2 1 2
*/

求赞 $qwq$