上海网站建设上海黄金,wordpress 替换图标,用易语言做刷网站注册软件,建设银行官网网站人事题目大意
给出n,a,b和n个数#xff0c;有两个集合A,B#xff0c;如果x放在A中则a-x必须存在且在A中#xff0c;B同理#xff0c;问你是否有合法方案 解题思路
不难发现#xff0c;如果a-x或b-x存在#xff0c;那么和x必须在同一个集合#xff08;若x放A中b-x放B中则不…题目大意
给出n,a,b和n个数有两个集合A,B如果x放在A中则a-x必须存在且在A中B同理问你是否有合法方案 解题思路
不难发现如果a-x或b-x存在那么和x必须在同一个集合若x放A中b-x放B中则不满足题面的性质
那么把有关联的点用并查集连一起并判断是否都存在a-x或b-x code
#includemap
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 100100
using namespace std;
ll T,n,a,b,pp,to[N][3],v[N][3],s[N],fa[N];
mapll,llp;
ll find(ll x)
{return fa[x]x?x:fa[x]find(fa[x]);
}
void merge(ll x,ll y)
{ll xxfind(x),yyfind(y);if(xxyy)return;fa[xx]yy;v[yy][1]v[xx][1];v[yy][2]v[xx][2];return;
}
int main()
{scanf(%lld,T);while(T--){scanf(%lld%lld%lld,n,a,b);for(ll i1;in;i){fa[i]i;scanf(%lld,s[i]);p[s[i]]i;}for(ll i1;in;i){if(s[i]a)to[i][1]0;else to[i][1]p[a-s[i]];//a-xif(s[i]b)to[i][2]0;else to[i][2]p[b-s[i]];v[i][1](to[i][1]?1:0);//连边v[i][2](to[i][2]?1:0);}for(ll i1;in;i){if(to[i][1])merge(i,to[i][1]);if(to[i][2])merge(i,to[i][2]);}pp1;for(ll i1;in;i)if(fa[i]i)if(!(v[i][1]||v[i][2]))pp0;//必须可以同时放到一个集合中if(pp)puts(YES);else puts(NO);for(ll i1;in;i)p[s[i]]0;}return 0;
}
