【SWTR-01】Sweet Round 01 T2 Ethan and sets

Alex_Wei · 2019-10-02 21:14:15 · 题解

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

官方题解

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

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

这题应该还算简单，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