把n个数放到集合A和集合B

使得：

对于某个数x，若x在A集合则 a-x也必须在A集合（若a-x不存在于n个数中，则x不能放在A集合）

放在B集合同理。

输出任意解：每个数放在哪个集合里（允许n个数都放一个集合）

思路：

类似二分匹配的做法。

[java] view plaincopy

1. import java.io.PrintWriter;  
2. import java.util.ArrayList;  
3. import java.util.Arrays;  
4. import java.util.Collections;  
5. import java.util.HashMap;  
6. import java.util.HashSet;  
7. import java.util.Iterator;  
8. import java.util.List;  
9. import java.util.Map;  
10. import java.util.Scanner;  
11. import java.util.Set;  
12. import java.util.TreeSet;  
13.   
14. public class Main {  
15.     int work(int x){  
16.         if(x%2==0)return x+1;  
17.         else return x-1;  
18.     }  
19.     static int N = 200050;  
20.     class Node implements Comparable <Node>{  
21.         int x, id;  
22.         Node(int x, int id){  
23.             this.x = x; this.id = id;  
24.         }  
25.         public int compareTo(Node o){  
26.             return Integer.compare(x, o.x);  
27.         }  
28.         public String toString(){  
29.             return id + "=" + x;  
30.         }  
31.     }  
32.     class Edge{  
33.         int from, to, nex;  
34.         Edge (int from, int to, int nex){  
35.             this.from = from;  
36.             this.to = to;  
37.             this.nex = nex;  
38.         }  
39.     }  
40.     Edge[] edge = new Edge[N*10];  
41.     int[] head = new int[N];  
42.     int edgenum;    
43.     void addedge(int u, int v){    
44.         Edge E = new Edge(u, v, head[u]);    
45.         edge[edgenum] = E;    
46.         head[u] = edgenum ++;    
47.     }    
48.       
49.     int n;  
50.     int[] p = new int[N], ans = new int[N];  
51.     int a, b, max;  
52.     Map<Integer, Integer> map = new HashMap();  
53.     boolean match(int x, int y, int col){  
54.         int P = map.get(x);  
55.         if(map.containsKey(y-x) == false)  
56.             return false;  
57.         int Q = map.get(y - x);  
58.         if(ans[Q] == -1 || x * 2 == y){  
59.             ans[Q] = ans[P] = col;  
60.         }  
61.         else {  
62.             if(match(a+b-2*y+x, y, col))  
63.                 ans[Q] = ans[P] = col;        
64.             else return false;  
65.         }  
66.         return true;  
67.     }  
68.     boolean solve(){  
69.         if(max >= a && max >= b)return false;  
70.         for(int i = 1; i <= n; i++)  
71.             if(ans[i] == -1)  
72.             {  
73.                 if(match(p[i], a, 0)==false && match(p[i], b, 1) == false)  
74.                     return false;  
75.             }         
76.         return true;  
77.     }  
78.     void init(){  
79.         n = cin.nextInt();  
80.         a = cin.nextInt(); b = cin.nextInt();  
81.         max = 0;  
82.         for(int i = 1; i <= n; i++){  
83.             ans[i] = -1;  
84.             p[i] = cin.nextInt();  
85.             map.put(p[i], i);  
86.             if(p[i] > max) max = p[i];  
87.         }  
88.     }  
89.     public void work(){  
90.         init();  
91.         if(solve()){  
92.             out.println("YES");  
93.             for(int i = 1; i <= n; i++)out.print(ans[i]+" "); out.println();  
94.         }  
95.         else   
96.             out.println("NO");  
97.     }  
98.     Main() {  
99.         cin = new Scanner(System.in);    
100.         out = new PrintWriter(System.out);  
101.     }    
102.     public static void main(String[] args) {  
103.         Main e = new Main();    
104.         e.work();  
105.         out.close();  
106.     }  
107.     public Scanner cin;  
108.     public static PrintWriter out;  
109. } 

CodeForces 468B Two Sets 二分匹配