离散10

深碍√TFBOYSˉ_ 2022-06-15 07:07 122阅读 0赞

#### Problem Description ####

给定一个数学函数F和两个集合A,B,写一个程序来确定函数是满射。 如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在A中都有一个或一个以上的原像)，或者说值域任何元素都有至少有一个变量与之对应，那这个映射就叫做满射。

![58ad4f47b948b.png][]

#### Input ####

多组输入直到文件结束，对于每组输入，第一行先输入一个n（A集合里的元素个数），m（B集合里的元素个数），k（F数学函数关系的条数）。

0 < n,m < 10000, 0 < k < n;

第二行输入有n个元素，分别为a1到an；

第三行输入有m个元素，分别为b1到bn；

接下来输入有k行，分别为集合A到B的关系

#### Output ####

（一组答案占一行）

当满足满射关系时输出Yes。

不满足关系时输出No。

#### Example Input ####

5 3 5
    1 3 5 7 8 
    2 5 6 
    1 2 
    3 6 
    5 5 
    7 2 
    8 6

#### Example Output ####

Yes

代码：\#include <stdio.h>  
int main()  
\{  
int n,m,k,i;  
while (~scanf("%d%d%d",&m,&n,&k))  
\{  
int a,b\[10000\]=\{0\};  
for(i=0;i<=m-1;i++)  
\{  
scanf("%d",&a);  
b\[a\]=1;  
\}  
int c\[10000\],d\[10000\];  
for(i=0;i<=n-1;i++)  
\{  
scanf("%d",&c\[i\]);  
d\[c\[i\]\]=0;  
\}  
int flag=0,e,f;  
for(i=0;i<=k-1;i++)  
\{  
scanf("%d%d",&e,&f);  
if(b\[e\]==1)  
flag++;  
d\[f\]++;  
  
  
\}  
int h=0;  
for(i=0;i<=n-1;i++)  
\{  
if(d\[c\[i\]\]>0)  
h++;  
\}  
if(flag==k&&h==n)  
printf("Yes\\n");  
else  
printf("No\\n");  
\}  
return 0;  
\}

总觉得还有好多方面没想到，但是竟然AC了。。然后做的前几次样例就错了，最后把最后一个for循环k-1改成了n-1，因为，这个for循环要看的是值域是否都取到。

思路。。一方面看左边的值是否在定义域内，另一方面看，值域是否都取到了。

[58ad4f47b948b.png]: http://acm.sdut.edu.cn/image/58ad4f47b948b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，122人围观）

还没有评论，来说两句吧...

相关阅读

相关离散题目3

think: 1暴力for循环 2初级桶排序思想 [sdut题目链接][sdut] 离散题目3 Time Limit: 1000MS Memory Limit:

迈不过友情╰/ 2022年09月30日 13:52/ 0 赞/ 155 阅读

相关 Educational Codeforces Round 10D 离散化+树状数组

[点击打开链接][Link 1] [ ][Link 1] 题意: 有n条线段, n<=200000, 每条线段有左端点l 和右端点r, -1e9 <= l<r<1e9,

太过爱你忘了你带给我的痛/ 2022年07月28日 01:05/ 0 赞/ 180 阅读

相关离散题目12

think: 1getline()+ string + stringstream 2自己初始代码超时原因——此题目后台评测数据中可能出现输入结束后空格回车情况 [sd

ゞ浴缸里的玫瑰/ 2022年06月18日 09:41/ 0 赞/ 193 阅读

相关离散10

Problem Description 给定一个数学函数F和两个集合A,B,写一个程序来确定函数是满射。如果每个可能的像至少有一个变量映射其上(即像集合B中的每个元素在

深碍√TFBOYSˉ_/ 2022年06月15日 07:07/ 0 赞/ 123 阅读

相关离散7

离散题目7 Time Limit: 1000MS Memory Limit: 65536KB [Submit][] [Statistic][] Probl

客官°小女子只卖身不卖艺/ 2022年06月15日 04:24/ 0 赞/ 124 阅读

相关【离散化】【转载】

如果说今年这时候OIBH问得最多的问题是二分图，那么去年这时候问得最多的算是离散化了。对于“什么是离散化”，搜索帖子你会发现有各种说法，比如“排序后处理”、“对坐标的近似处理”

迷南。/ 2022年06月10日 09:46/ 0 赞/ 250 阅读

相关【离散化】

\ 离散化 |||离散化就是三句话，sort，unique，lower\_bound||| 1.专业术语：把无限空间中有限的个体映射到有限的空间中去，以此提高算法的

心已赠人/ 2021年10月30日 06:52/ 0 赞/ 377 阅读

相关离散化总结

离散化是一种很常见的数据处理方式。最近也是学了一下(才学的我还有救么QAQ)，一学就懂，但发现在题目中好像也并没有怎么想到这东西，，所以在这里简单总结一下我对离散化的

梦里梦外;/ 2021年10月26日 13:34/ 0 赞/ 414 阅读

相关 # 离散化

离散化值得注意的是：unique()函数去重之后并不是把重复元素放在最末尾，而是类似于删除了这个数，然后末尾元素保持不变，比如`1 2 2 3`去重之后是`1 2

￡神魔★判官ぃ/ 2021年10月25日 12:50/ 0 赞/ 375 阅读

相关离散数学

第一章命题和命题公式推理概念：由一个或几个已知的前提，推导出一个未知结论的思维过程基本要素：表达这些前提的一些陈述句真值概念：成立或不成立可以看作是这个...

红太狼/ 2021年04月19日 14:50/ 1 赞/ 1329 阅读