首页 > 试题广场 >

集合问题

[编程题]集合问题
  • 热度指数：3 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

给你a,b和n个数p[i]，问你如何分配这n个数给A,B集合，并且满足：

若x在集合A中，则a-x必须也在集合A中。

若x在集合B中，则b-x必须也在集合B中。


输入描述:
第一行 三个数 n a b  1<=n<=1e5  1<=a,b<=1e9
第二行 n个数 p1 p2 p3...pn 1<=pi<=1e9


输出描述:
如果某个数只出现一次, 它也可以同时分配给A、B集合，只要所有数字都可以被分配到集合中，那么就输出YES
然后第二行输出 n个数 分别代表pi 是哪个集合的  0 代表是A集合 1代表是B 集合
不行就输出NO
放在哪个集合都可以的时候优先放B
示例1

输入

4 5 9
2 3 4 5

输出

YES
0 0 1 1
示例2

输入

3 3 4
1 2 4

输出

NO
算法知识视频讲解
开通博客
头像 hrdate
发表于 2020-07-04 22:00:36
首先知道p[i]≥1，所以不存在p[i]大于等于max(a,b)用map<ll,ll>mp记录下每个p[i]出现的下标，每次找到b-p[i]或a-p[i]都进行一次连接因为考虑优先放入到b中，所以在YES的前提下，if判断是否放在b的条件放在前面。需要注意的输出格式问题，就是最后没有多余 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 冰雅
发表于 2022-09-04 12:23:07
题目描述 给你a,b和n个数p[i]，问你如何分配这n个数给A,B集合，并且满足： 若x在集合A中，则a-x必须也在集合A中。 若x在集合B中，则b-x必须也在集合B中。 思路 因为p[i]是正数，所以一定要小于max(a,b) 用map<ll,ll> mp记录p[i]的下标 i 如果a 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 -符拉迪沃斯托克-
发表于 2021-08-19 20:52:18
首先最大的数字一定小于给定的，否则必须有或者负值存在。 显然数对一定是存在于两个集合中的某一个。 所以对于每个给的数，若中任意一个出现，就必须配对。 这样就变成了并查集，即能配对的数对合并并查集。 每个数字用出现的位置来代替，相当于一个没有去重的离散化。 这个用什么二分啊，平衡树啊，啊啥的都行，复杂 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

并查集
上传者：牛客303862号
难度：
0条回答 10浏览

热门推荐

通过挑战的用户

查看代码

相关试题

集合问题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号