U137971 公司搬迁 - 并查集

标签:题解   wrap   输入格式   marked   范围   限制   准备   找不到   round   

题目描述

因为人员规模扩大,T公司准备搬到新的写字楼去,写字楼分为A座和B座,n名不同工号的员工x(p1,p2,p3...pn) 按照下面两个规则确定在A座或者B座进行办公:
(1)如果工号为x的员工在A座,那么工号为a-x的员工肯定也在A座(编号为a-x的员工要保证存在,否则不成立)
(2)如果工号为x的员工在B座,那么工号为b-x的员工肯定也在B座(编号为b-x的员工要保证存在,否则不成立)
判断一下是否存在一种方案来分配所有员工的办公地点。如果能够分配全员的办公地点,输出YES;若存在至少一名 员工,找不到规则中与之对应的员工,输出NO。

注意:如果所有员工都在A座或者都在B座也可以。

 

输入格式

第一行输入一个T(1≤T≤10),表示下面有多少组测试数据 对于每组测试数据的2行输入:
第1行有3个整数n,a,b (1≤n≤1e5; 1≤a,b≤1e9) 。 第2行有n个不一样的整数 p1,p2,...,pn (1≤pi≤1e9).

输出格式

每组数据输出一行结果,如果可行,那么输出YES,否则输出NO。

输入输出样例

输入 #1

2
4 5 9
2 3 4 5
3 2 3
1 2 3

输出 #1

YES
NO

输入 #2

2
5 10 11
2 8 3 7 5
3 5 12
1 4 3

输出 #2

YES
NO

说明/提示

数据范围

对于50%的数据,1 ≤ n ≤ 10,1 ≤ pi ≤ 20
对于65%的数据,1 ≤ n ≤ 100
对于100%的数据,1 ≤ n ≤ 1e5,1≤a,b≤1e9,1 ≤ pi ≤ 1e9,1≤T≤10

样例解释

对于样例1:
第一组数据中,四名员工的工号依次为{2,3,4,5},此时a=5,b=9,可以安排{2,3}在A座,{4,5}在B座,人员分配完 成,该方案可行,所以第一行输出YES。
第二组数据中,无论如何工号为3的员工也无法找到与之对应的员工进行分配,所以第二行输出NO。

对于样例2:
第一组数据中,五名员工的工号依次为{2,3,7,8,5},此时a=10,b=11,首先将5号员工安排在A座中,他与他自身对 应,符合题意;之后将{2,8}{3,7}分别也安排在A座,分配完成,输出YES。
第二组数据中,无论如何工号为3的员工也无法找到与之对应的员工进行分配,所以输出NO。

题解

 这题可以用2-sat做,然而我并不会,题解的做法开2倍并查集还看不懂,所以就自己乱搞。

 1.题意

  其实就是给一些节点染色, 给定一些限制,要求某两个节点必须染成同一个颜色

  

 1.推性质

  这题的关键部分就是

U137971 公司搬迁 - 并查集

标签:题解   wrap   输入格式   marked   范围   限制   准备   找不到   round   

原文地址:https://www.cnblogs.com/ltdjcoder/p/13897591.html

版权声明:完美者 发表于 2020-10-30 12:10:59。
转载请注明:U137971 公司搬迁 - 并查集 | 完美导航

暂无评论

暂无评论...