讨论 题解

· · 题解

看到这道题有一个显然的想法，就是先将集合按大小从小到大排序。然后遍历每个集合，每个集合都塞进集合中每个元素所对应的桶。显然一个桶中的所有集合都包含着这个桶所对应的元素，之后只需要判断一个桶中是否有互相不包含的两个集合即可。

记一个桶中的集合分别是 a_1,a_2,a_3 ... 如果集合 a_i 和集合 a_j 是答案，并且 i < j 且 a_i \subseteqq a_{i+1} 那么 a_{i+1} 和 a_j 也是答案。这里你会发现一个结论，你只需要判断桶中相邻长度的两个集合是否可行即可。

但是这里会出现一个问题。由于一个集合被塞进了很多个桶里面，所以一个集合最多可能会判断 k 次。怎么解决这个问题呢？你会发现，有很多个集合都被塞进了多个桶里，这就导致在不同桶中，有一个集合可能会与另一个集合多次进行判断。这时，可以开一个哈希表判断同样的两个集合是否被判断过，如果是，跳过即可。

这个的复杂度是 O(t(n\log n+m))

代码如下

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

const int Mod1 = 1e7 + 7;
const int Mod2 = 1e7 + 9;

int t;

int n;

bool mp1[Mod1],mp2[Mod2];

void Hash(long long val)
{
    mp1[val % Mod1] = 1;
    mp2[val % Mod2] = 1;
}

bool in_hash(long long val)
{
    return mp1[val % Mod1] && mp2[val % Mod2];
}

struct node
{
    int k,id;
    vector<int> ve;
    void clear()
    {
        k = 0;
        ve.clear();
    }
}a[N];

vector<int> ve[N];

bool cmp(const node &x,const node &y)
{
    return x.k < y.k;
}

bool check(const node &x,const node &y)
{
    int i = 0,j = 0;
    while(i < x.k)
    {
        if(x.ve[i] == y.ve[j])
        {
            i++;
        }
        else
        {
            j++;
            if(j >= y.k)
            {
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(mp1,0,sizeof(mp1));
        memset(mp2,0,sizeof(mp2));
        for(int i = 1;i <= n;i++)
        {
            a[i].clear();
            ve[i].clear();
            scanf("%d",&a[i].k);
            a[i].id = i;
            bool flag = 0;
            for(int j = 1;j <= a[i].k;j++)
            {
                int val;
                scanf("%d",&val);
                a[i].ve.push_back(val);
            }
            for(int j = 1;j < a[i].k;j++)
            {
                if(a[i].ve[j] < a[i].ve[j - 1])
                {
                    flag = 0;
                    break;
                }
            }
            if(!flag) sort(a[i].ve.begin(),a[i].ve.end());
        }
        sort(a + 1,a + n + 1,cmp);
        for(int i = 1;i <= n;i++)
        {
            for(int j = 0;j < a[i].k;j++)
            {
                ve[a[i].ve[j]].push_back(i);
            }
        }
        int ans1 = 0,ans2 = 0;
        for(int i = 1;i <= n;i++)
        {
            int len = ve[i].size();
            len--;
            for(int j = 0;j < len;j++)
            {
                long long x = 1ll * ve[i][j] * N + ve[i][j + 1];
                if(in_hash(x))
                {
                    continue;
                }
                Hash(x);
                if(check(a[ve[i][j]],a[ve[i][j + 1]]))
                {
                    ans1 = ve[i][j];
                    ans2 = ve[i][j + 1];
                    break;
                }
            }
            if(ans1)
            {
                break;
            }
        }
        if(ans1)
        {
            printf("YES\n%d %d\n",a[ans1].id,a[ans2].id);
        }
        else
        {
            printf("NO\n");
        }
    }
    return 0;
}