題目：

1557 兩個集合
題目來源： CodeForces
基準時間限制：1 秒 空間限制：131072 KB 分值: 40 難度：4級算法題
小X有n個互不相同的整數(shù)： p1,p2,…,pn 。他想把這些整數(shù)分到兩個集合A和B里邊。但是要符合下面兩個條件。

· 如果x屬于A，那么a-x也肯定屬于A。

· 如果x屬于B，那么b-x也肯定屬于B。

判斷一下是否存在一種方案來分配這些數(shù)字到集合A，B中。

注意：如果一個集合為空也是可以的。

Input
單組測試數(shù)據(jù)。
第一行有三個整數(shù)n,a,b (1≤n≤10^5; 1≤a,b≤10^9)。
第二行有n個不一樣的整數(shù) p1,p2,…,pn (1≤pi≤10^9).
Output
如果可行，那么輸出YES，否則輸出NO。
Input示例
樣例輸入1
4 5 9
2 3 4 5
Output示例
樣例輸出1
YES

題意很清楚就是把所有的數(shù)字按要求分在A,B集合中，看是否能全部分完。

看似很簡單，但是有很多坑點，需要把所有的邏輯都想清楚再下筆。

解法：
　　　　首先我們看到這道題肯定會想到二分圖的解法。
　　　　二分圖是相鄰的點要染成不同色，看是否能把整個圖只用兩種顏色染色。
　　　　這道題是相鄰的點（a[i]+a[j]==A || a[i]+a[j]==B）要染成同色，看是否能用兩種顏色表示。（注意的是兩種顏色可能相同(A == B)）
　　　　但是和二分圖很不同的是，當一個點可以在A中而且可以在B中時，用二分圖的邏輯有點行不通了。

　　所以我們換個思路：
　　　　
　　　　當某個點只能存在A中/只能存在于B中時，我們就把這個點和與之匹配的點（A-a[i]/B-a[i]）放在A/B中。
　　　　一趟一趟的掃所有的點，如果某一次沒有能放在A/B中的點了，
　　　　　　1.n個點中還有點沒有被放在A/B中，那就不能分完，輸出NO。
　　　　　　2.n個點全部放在A/B中了，那就能分完，輸出YES。

　　　　注意的就是如果A == B,可能會陷入死循環(huán)，需要特殊處理A == B，直接看是否能將全部點放在A/B中就可以。

代碼：

#include <iostream> #include <algorithm> #include <map> #include <vector> #include <set> #include <math.h> #include <queue> using namespace std; typedef long long ll; #define INF 2147483647int s[100010];map<int, bool> in; // 表示數(shù)字沒有被使用過，所有的數(shù)字都在大集合里 int main(){int n,a,b;cin >> n >> a >> b;for(int i = 0;i < n; i++){cin >> s[i];in[s[i]] = true;}int count = 0; //記錄多少個數(shù)字被使用過 while(true){//標記當前循環(huán)是否有數(shù)字匹配 bool update = false;for(int i = 0;i < n; i++){ if(!in[s[i]]) continue; //這個數(shù)字被使用過了，不再計算 if(in[a-s[i]] && !in[b-s[i]]){//在A集合中能找到匹配對象，B集合中找不到，一定要放在A集合中 in[a-s[i]] = false; in[s[i]] = false;count += 2;update = true;}else if(!in[a-s[i]] && in[b-s[i]]){//在B集合中能找到匹配對象，A集合中找不到，一定要放在B集合中in[b-s[i]] = false;in[s[i]] = false;count += 2;update = true;}else if(in[a-s[i]] && in[b-s[i]] && a == b){//如果a == b，全部放在一個集合中就可以了 in[a-s[i]] = false; in[s[i]] = false;count += 2;update = true;}}//如果放了n個數(shù)字了，說明可以分配 if(count >= n) break;//如果放不夠n個數(shù)字，而且再也找不到匹配了，說明無法分配 if(!update){cout << "NO" << endl;return 0;}}cout << "YES" << endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的51nod 1557 两个集合 (严谨的逻辑题)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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