Discussion


Bananas are the favoured food of monkeys. 
In the forest, there is a Banana Company that provides bananas from different places. 
The company has two lists. 
The first list records the types of bananas preferred by different monkeys, and the 
second one records the types of bananas from different places. 
Now, the supplier wants to know, whether a monkey can accept at least one type of 
bananas from a place. 
Remenber that, there could be more than one types of bananas from a place, and there 
also could be more than one types of bananas of a monkey’s preference.

Input Format

The first line contains an integer T, indicating that there are T test cases. 
For each test case, the first line contains two integers N and M, representing the 
length of the first and the second lists respectively. 
In the each line of following N lines, two positive integers i, j indicate that the i-th 
monkey favours the j-th type of banana. 
In the each line of following M lines, two positive integers j, k indicate that the j-th 
type of banana could be find in the k-th place. 
All integers of the input are less than 50.

Output Format

For each test case, output all the pairs x, y that the x-the monkey can accept at least 
one type of bananas from the y-th place. 
These pairs should be outputted as ascending order. That is say that a pair of x, y 
which owns a smaller x should be output first. 
If two pairs own the same x, output the one who has a smaller y first. 
And there should be an empty line after each test case.

Sample Input

1 
6 4 
1 1 
1 2 
2 1 
2 3 
3 3 
4 1 
1 1 
1 3 
2 2 
3 3

Sample Output

1 1 
1 2 
1 3 
2 1 
2 2 
2 3 
3 3 
4 1 
4 3

题意：

输入n和m，n行每行表示第i只猴子喜欢第j种香蕉，m行每行表示第i种香蕉来自第j个地区；
问哪些猴子在哪些地区有喜欢的香蕉，按猴子序号（若同则按地区）升序输出。

思路：

通过观察，可把每对数据当作一个二元关系，由n行部分和m行部分的二元关系通过关系复合（离散数学）得到结果。这里可通过 vector 和 map 的实现。

code：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int maxn = 55;
vector<int >nm[maxn];
int map[maxn][maxn];

int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n, m, moky, bana, pls;
        for(int i=0;i<=50;i++)
            nm[i].clear();
        memset(map,0,sizeof(map));
        scanf("%d %d",&n, &m);
        for(int i = 0; i < n; i ++)
        {
            scanf("%d %d",&moky, &bana);
            nm[bana].push_back(moky);
        }
        for(int i = 0; i < m; i ++)
        {
            scanf("%d %d",&bana, &pls);
            for(unsigned int j = 0; j < nm[bana].size(); j ++)
                map[nm[bana][j]][pls] = 1;
        }
        for(int i = 1; i <= 50; i ++)
        {
            for(int j = 1; j <= 50; j ++)
                if(map[i][j])
                    printf("%d %d\n",i,j);
        }
        printf("\n");
    }
}

Logo
GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/

avatar GitCode 开源社区
cover

用C++实现4种YOLO目标检测（内附完整代码）

avatar GitCode 开源社区
cover

静态时序分析：SDC约束命令create_generated_clock详解（上）

avatar GitCode 开源社区