解題區/解題區 - UVa

UVa 12011 - Complete the Set

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

找到一個完備集合，其任兩個數字做 AND 和 OR 運算都在集合中。

給定部分集合，請問至少還需要幾個元素使得其變成完備集合。

Sample Input

1
2
3
4
5
6
7
8
9
4
5
0 1 3 5 7
2
2 4
3
3 7 11
3
1 2 4

Sample Output

1
2
3
4
Case #1: 0
Case #2: 2
Case #3: 1
Case #4: 5

Solution

這一題從傳錯題目開始已經放著很久，當時怎麼樣都沒有想法，直接著手 O(n * 2^20) 最慘運行方式，其實這種複雜度與通過的複雜度就差那麼一點的 n。 // 肯定是死在 n。

其實可以發現到，假使挑選 i-th bit 很有可能會連帶其他的 bit 一同帶上，因此對於 i-th bit 最小化攜帶的 bit (做 AND 最小化)。

最後窮舉攜帶 i-th bit 是否要挑 (OR 所有攜帶的 bit)，複雜度降至 O(2^20)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
int main() {
    int testcase, cases = 0;
    int n, x;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &n);
        set<int> S;
        int A[32] = {}, all = (1<<18) - 1; // used i-th bits minimum attachment.
        memset(A, -1, sizeof(A));
        for (int i = 0; i < n; i++) {
            scanf("%d", &x);
            S.insert(x);
            all &= x; // used mask = 0
            for (int j = 0; j < 18; j++) {
                if ((x>>j)&1) {
                    if (A[j] == -1)
                        A[j] = x;
                    else
                        A[j] = A[j] & x;
                }
            }
        }
        S.insert(all);
        int m = 0;
        for (int i = 0; i < 18; i++) {
            if (A[i] != -1)
                A[m++] = A[i];
        }
        for (int i = 1; i < (1<<m); i++) { // used mask
            int num = 0;
            for (int j = 0; j < m; j++) {
                if ((i>>j)&1) {
                    num |= A[j];
                }
            }
            S.insert(num);
        }
        printf("Case #%d: %d\n", ++cases, (int)S.size() - n);
    }
    return 0;
}
/*
 4
 5
 0 1 3 5 7
 2
 2 4
 3
 3 7 11
 3
 1 2 4
 */