最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • Merging the Sets

    正文概述 陈老师   2026-01-20 15:14:47  

    Merging the Sets

    题目描述

    给你 nn 个集合 S1,S2,…,SnS_1, S_2, \ldots, S_n,其中每个集合里的元素是 11 到 mm 之间的整数。

    你需要选择一些集合(可以一个都不选,也可以全选),使得从 11 到 mm 的每个整数至少在一个被选中的集合中出现。

    请判断是否有至少三种不同的方式选择集合,使上述条件成立。

    输入格式

    每组测试数据包含多组测试用例。第一行为测试用例组数 tt(1≤t≤1041 \le t \le 10^4)。接下来是各组测试数据。

    每个测试用例的第一行为两个整数 nn 和 mm(2≤n≤5⋅1042 \leq n \leq 5 \cdot 10^4,1≤m≤1051 \le m \leq 10^5),分别表示集合数和整数范围上界。

    接下来有 nn 行,第 ii 行首先包含一个整数 lil_i(1≤li≤m1\le l_i \le m),表示第 ii 个集合的大小。

    接下来接 lil_i 个整数 Si,1,Si,2,…,Si,liS_{i,1}, S_{i,2}, \ldots, S_{i, l_i}(1≤Si,1<Si,2<⋯<Si,li≤m1\le S_{i,1} < S_{i,2} < \cdots < S_{i, l_i} \le m),表示 SiS_i 的元素。

    记 L=∑i=1nliL=\sum\limits_{i=1}^n l_i。保证:

    • 所有测试用例中 nn 的总和不超过 5⋅1045 \cdot 10^4;
    • 所有测试用例中 mm 的总和不超过 10510^5;
    • 所有测试用例中 LL 的总和不超过 2⋅1052 \cdot 10^5。

    输出格式

    对于每个测试用例,如果存在至少三种不同的选择集合的方案,输出 YES,否则输出 NO。

    样例

    6
    3 2
    2 1 2
    1 1
    1 2
    4 10
    3 1 2 3
    2 4 5
    1 6
    4 7 8 9 10
    2 5
    4 1 2 3 4
    4 1 2 3 4
    5 5
    5 1 2 3 4 5
    5 1 2 3 4 5
    5 1 2 3 4 5
    5 1 2 3 4 5
    5 1 2 3 4 5
    5 10
    4 1 2 3 4
    5 1 2 5 6 7
    5 2 6 7 8 9
    4 6 7 8 9
    2 9 10
    5 5
    1 1
    1 2
    1 3
    2 4 5
    1 5
    
    YES
    NO
    NO
    YES
    YES
    NO
    

    提示

    在第一个测试用例中,存在 5≥35 \ge 3 种选择方案:

    • 只选 S1S_1 — 11 和 22 都包含在 S1S_1 中;
    • 选 S1S_1 和 S2S_2 — 11 包含在 S1S_1 和 S2S_2,22 包含在 S1S_1;
    • 选 S1S_1 和 S3S_3 — 11 包含在 S1S_1,22 包含在 S1S_1 和 S3S_3;
    • 选 S2S_2 和 S3S_3 — 11 包含在 S2S_2,22 包含在 S3S_3;
    • 选 S1S_1、S2S_2 和 S3S_3 — 11 包含在 S1S_1 和 S2S_2,22 包含在 S1S_1 和 S3S_3。

    注意,单独选 S2S_2 是不合法的,因为 22 不包含在 S2S_2 中。

    在第二个测试用例中,只有唯一的一种方式就是全部选上所有集合。

    在第三个测试用例中,55 没有出现在任意一个集合中,因此无法选择满足条件的集合。

    在第四个测试用例中,任选非空的集合组合都满足条件,所以方案数为 25−1=31≥32^5-1=31\ge3。

    数据范围

    见题面。

    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » Merging the Sets