题解：P5583 「SWTR-1」Ethan and Sets

· · 题解

思路

看到题目要输出的 l 和 r 大概会很快想到双指针。

用 cnt_i 统计第 i 项有多少个 Ethan 不喜欢的数，用 book_i 记录 i 出现的次数。\ 用 dl、ml、zl 分别记录下在 l 到 r 的范围内，有 dl 个 Ethan 不喜欢的数，魔力总和为 ml，Ethan 喜欢的数有 zl 种，这样在更新的时候直接比较就可以了。

对于每次 r 的增大，遍历一遍 c_{r,1},c_{r,2},\dots,c_{r,num_r}，再把每个 book_{c_{r, i}} 都加一，如果增大前 book_{c_{r, i}} 的值为 0，那么说明 l 到 r 之间 Ethan 喜欢的数的种类多了一个，即 dl 的值加一。\ 最后看 dl 的值超过 d 了就退出。

每次 l 的增大同 r，只不过每次 l 只增大一次。

如果 ansl 和 ansr 最后都是 0，说明它们没被更新，则无解，输出 -1，否则输出 ansl 和 ansr 的对应值。

最后提醒一下要开 long long。然后记得特判一下，如果 cnt_r 为 0，说明这一项没有 Ethan 讨厌的数，而放入这一项会让魔力值增大，所以这一项必须选，尽管 zl 已经等于 d 了。详见样例三。

其他细节见代码。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m, d, l = 1, r, flag, dl, ml, zl, ansdl = INT_MAX, ansml, ansl, ansr, t[3010], num[3010], c[3010][1010], cnt[3010], like[1010], book[1010];
signed main()
{
    scanf("%lld%lld%lld", &n, &m, &d);
    for (int i = 1, p; i <= d; i++)
        scanf("%lld", &p), like[p] = 1;
    for (int i = 1; i <= n; i++)
    {
        scanf("%lld%lld", &t[i], &num[i]);
        for (int j = 1; j <= num[i]; j++)
            scanf("%lld", &c[i][j]), cnt[i] += !like[c[i][j]];
    }
    while (l <= n)
    {
        while (r < n && (zl < d || !cnt[r + 1]))
        {
            r++, dl += cnt[r], ml += t[r];
            for (int i = 1; i <= num[r]; i++)
                zl += !book[c[r][i]] && like[c[r][i]], book[c[r][i]]++;
        }
        if (zl == d && (dl < ansdl || (dl == ansdl && ml >= ansml)))
            ansdl = dl, ansml = ml, ansl = l, ansr = r;
        for (int i = 1; i <= num[l]; i++) 
            book[c[l][i]]--, zl -= !book[c[l][i]] && like[c[l][i]];
        dl -= cnt[l], ml -= t[l], l++;
    }
    if (!ansl && !ansr)
        printf("-1");
    else
        printf("%lld %lld", ansl, ansr);
    return 0;
}

给个赞再走吧。