解題區/解題區 - Zerojudge

a981. 求和問題

contents

  1. 1. 題目
    1. 1.1. 內容：
    2. 1.2. 輸入說明：
    3. 1.3. 輸出說明：
    4. 1.4. 範例輸入：
    5. 1.5. 範例輸出：
  2. 2. 解法

題目

內容：

給你N個正整數, 試求哪幾個之和剛好為M, 印出所有合條件的解, 如有多組解, 請按由小到大的順序印出(格式可參考樣例輸出)

輸入說明：

n m (1<=n<=30, 1<=m<=100000000) n個正整數, 全部以空格分開

輸出說明：

  • 其和剛好等於m的數, 如果有多組解則按由小到大全部印出, 如果無解則印出 -1

範例輸入：

10 100
10 20 40 30 50 80 60 70 5 15

範例輸出：

5 10 15 20 50
5 10 15 30 40
5 10 15 70
5 15 20 60
5 15 30 50
5 15 80
10 20 30 40
10 20 70
10 30 60
10 40 50
20 30 50
20 80
30 70
40 60

解法

  • 作法：
    分治，將輸入 n 個劃分成兩堆，分別窮舉所有可能，採用合併的方式去運算。
a981.cpp
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
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
using namespace std;
int main() {
    int n, m;
    int A[35];
    while(scanf("%d %d", &n, &m) == 2) {
        for(int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        sort(A, A + n, greater<int>());
        int h1Cnt = n / 2, h2Cnt = n - h1Cnt;
        map<long long, vector<int> > h1, h2;
        for(int i = (1<<h1Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h1Cnt; j++) {
                if((i>>j)&1)	sum += A[j];
            }
            h1[sum].push_back(i);
        }
        for(int i = (1<<h2Cnt)-1; i >= 0; i--) {
            long long sum = 0;
            for(int j = 0; j < h2Cnt; j++) {
                if((i>>j)&1)	sum += A[j + h1Cnt];
            }
            h2[sum].push_back(i<<h1Cnt);
        }
        set<int> ret;
        for(map<long long, vector<int> >::iterator it = h1.begin();
            it != h1.end(); it++) {
            long long f = (long long)m - it->first;
            map<long long, vector<int> >::iterator jt = h2.find(f);
            if(jt != h2.end()) {
                for(vector<int>::iterator iv = it->second.begin();
                    iv != it->second.end(); iv++) {
                    for(vector<int>::iterator jv = jt->second.begin();
                        jv != jt->second.end(); jv++) {
                        ret.insert(*iv| *jv);
                    }
                }
            }
        }
        if(ret.size() == 0)
            puts("-1");
        for(set<int>::reverse_iterator it = ret.rbegin();
            it != ret.rend(); it++) {
            for(int i = n-1; i >= 0; i--) {
                if(((*it)>>i)&1) {
                    printf("%d ", A[i]);
                }
            }
            puts("");
        }
    }
    return 0;
}