「乌鸦坐飞机」乌鸦坐飞机

乌鸦坐飞机

Problem F: 乌鸦坐飞机

Time limit: 2 Sec Memory Limit: 128 MB

Submit: 140 Solved: 19

[Submit][Status][Web Board]

Description

社会我福哥，为了揍成龙去玩了玩集合。

有n个集合，每个集合有m个数。

有q个询问，每次询问两个数a,b，问是否存在集合包含这两个数。

Input

多组测试数据(≤10)。

第一行一个n。(1≤n≤1000)

接下来n行，每行一个mi，后面有mi个数num. (1≤num,mi≤10000)

第n+2行一个整数q，表示有q次查询(1≤q≤200000)

接下来q行，每行两个整数a,b.(1≤a,b≤10000)

Output

每组数据输出q行。存在输出"Yes",否则输出"No"(不包含双引号)

Sample Input

3 1 2 3

3 1 2 5

1 10

1 3

1 5

3 5

1 10

Sample Output

Yes

[分析]

一开始开arr记录每个集合的数字，然后每次遍历每个集合，超时了。

然后观察了一下数据，发现m和num都挺小的，而且memory给了128M

所以思路就清晰了。

询问次数有6位数，一定要减少遍历的次数。

所以不能遍历所有的集合。既然找的是a和b都存在的集合，那为什么不在有a的集合中看看有没有b呢？

所以在输入的时候不经要保存某个组有哪些数字，还要保存某个数字在那些组中出现过。

之后的事情就简单了，遍历有a的集合，看看有没有b，有yes，没有no。

[后记]

ac之后还做了一个优化，就是当有a的集合较多时，遍历有b的集合找a

（就是代码中交换的一部分），但是只优化了十多毫秒。

[代码]

#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int main()
{
    int n, cnt, wen, a, b;
    int arr[1005][10005];
    while (scanf("%d", &n) != EOF)
    {
        vector<int>v[10005];
        memset(arr, 0, sizeof(arr));
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &cnt);
            for (int j = 0; j < cnt; j++)
            {
                int x;
                scanf("%d", &x);
                arr[i][x]++;
                v[x].push_back(i);
            }
        }
        scanf("%d", &wen);
        for (int i = 0; i < wen; i++)
        {
            scanf("%d%d", &a, &b);
            if (v[a].size() > v[b].size())
            {
                int c = a;
                a = b;
                b = c;
            }
            if (v[b].size() == 0)goto out1;
            for (int j = 0; j < v[a].size(); j++)
            {
                if (arr[v[a][j]][b] > 0)
                {
                    printf("Yes\n");
                    goto out;
                }
            }
        out1:;
            printf("No\n");
        out:;
        }
    }
}

文章最后发布于: 2017-08-14 18:44:00

乌鸦坐飞机

乌鸦坐飞机

相关阅读

栏目导航

推荐阅读

热门阅读