題目鏈接：點(diǎn)擊查看

題目大意：現(xiàn)在給出兩個(gè)集合A和B，再給出兩個(gè)數(shù)a和b，現(xiàn)在規(guī)定在集合A中的數(shù)x必須滿足x和a-x同時(shí)在集合a中，而在集合B中的數(shù)x也同樣需要滿足x和b-x同時(shí)在集合B中，現(xiàn)在給出一系列數(shù)，問能否將所有的數(shù)都分配到兩個(gè)集合中去

題目分析：這個(gè)題因?yàn)榉旁诹硕謭D的專題里，所以一開始想盡了一切辦法想將這個(gè)題目往匈牙利上靠攏，但最終沒辦法將模型抽象出來，看了題解后才知道是個(gè)簡(jiǎn)單并查集的題目，這里分析一下吧，對(duì)于任意一個(gè)x，無非只有四種情況：

a-x不存在，b-x不存在：輸出NO

a-x存在，b-x不存在：將x放到集合A中

a-x不存在，b-x存在：將x放到集合B中

a-x存在，b-x存在：將x放到集合A和集合B中

因?yàn)榻o出的n個(gè)數(shù)兩兩都是不同的，并且都是正整數(shù)，所以我們可以在一開始的時(shí)候就剪一下枝，如果數(shù)列中的最大值大于等于a或b中的最大值顯然是輸出NO的，因?yàn)檫@個(gè)時(shí)候無論是a還是b，減去這個(gè)最大值一定是一個(gè)負(fù)數(shù)，肯定找不到與其對(duì)應(yīng)的一個(gè)正整數(shù)，這種情況可以歸類為上面所述的第一種情況

我們維護(hù)1~n為數(shù)列，然后0為集合A，n+1為集合B，在輸入的時(shí)候就用map維護(hù)每個(gè)數(shù)的下標(biāo)，最后遍歷一遍，按照上述的2-4規(guī)則用并查集維護(hù)一下下標(biāo)，將x和a-x建邊或x和b-x建邊，最后判斷即可

該怎么判斷呢？因?yàn)槿绻麧M足了第一種情況，也就是a-x和b-x在數(shù)列中都不存在的話，那么這個(gè)數(shù)肯定被else判斷到了兩個(gè)集合中去了，也就是將點(diǎn)0和點(diǎn)n+1建了一條邊，第二種情況和第三種情況都會(huì)根據(jù)巧妙的邏輯將其與相應(yīng)的集合建邊，不重不漏，最后如果都存在的話，則只會(huì)先將這三個(gè)點(diǎn)：x,a-x,b-x三點(diǎn)建邊，等到后續(xù)判斷a-x的時(shí)候，以及b-x的時(shí)候，再利用else的邏輯將其與相應(yīng)集合建邊

不得不佩服這個(gè)題的思維邏輯

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;int val[N];unordered_map<int,int>pos;int f[N];int find(int x) {return x==f[x]?x:f[x]=find(f[x]); }void merge(int x,int y) {int xx=find(x);int yy=find(y);f[xx]=yy; }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int n,a,b;scanf("%d%d%d",&n,&a,&b);int mmax=0;for(int i=1;i<=n;i++){scanf("%d",val+i);pos[val[i]]=i;mmax=max(mmax,val[i]);}if(mmax>=max(a,b))return 0*printf("NO\n");for(int i=0;i<=n+1;i++)f[i]=i;for(int i=1;i<=n;i++){if(pos[a-val[i]])//如果x與a-x有對(duì)應(yīng)，就建邊merge(i,pos[a-val[i]]);else//否則將x加入到集合B中去merge(i,n+1);if(pos[b-val[i]])//如果x與b-x有對(duì)應(yīng)，就建邊merge(i,pos[b-val[i]]);else//否則將x加入到集合A中去merge(i,0);}int A=find(0);int B=find(n+1);if(A==B)printf("NO\n");else{printf("YES\n");for(int i=1;i<=n;i++){if(find(i)==A)printf("0");elseprintf("1");if(i!=n)putchar(' ');elseputchar('\n');}}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的CodeForces - 468B Two Sets(并查集+思维)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。