ZeroJudge D577: 等值首尾和變化型

大師專門秒殺題目維生

有一天他秒殺了等值首尾和後有了個想法

如果我從前面任取 N 個數把它加起來

那會有幾個一樣的數字呢

又哪個數字出現的方法最多呢

他說這已經超過他的智商了

於是他想找會編程的人幫他的忙

範例測資

範例輸入範例輸出
EOF 輸入，第 1 行有 2 個數字 a 和 b (a 代表有幾個數，b 代表要取幾個數) (0<=b<=a<=20)。
接下來有 a 個數字這些數字和不超過 2147483647 (不一定排序好)。
以 a = b = 0 做為結尾。		輸出 2 個數字 c 和 d (c 代表是哪個數字方法最多，d 代表方法數)。
若有很多 c 則輸出最小那個。
10 2
1 2 3 4 5 6 7 8 9 10
5 3
1 2 3 4 5
0 0		11 5
8 2

解題思路

使用 DFS 來累加 b 個數字，需要注意的是在 DFS 中需要判斷目前迴圈跑到的數字是否是在上一個數字的後面，所以可以在參數中再帶一個 start 變數預設為 0，並且迴圈從 start 開始，當要再次呼叫 DFS 時，將 start 的參數改成 i+1。

使用 Map 來紀錄每一個和出現的次數，並且使用 for (auto it:Map) 來判斷最多出現的和是哪一個，最後輸出答案即可。

範例程式碼－ZeroJudge D577: 等值首尾和變化型

#include <iostream>
#include <map>
using namespace std;

int a, b;
int num[30] = {};
bool visited[30] = {};
map<int, int>MAP;

void DFS(const int count, const int add, const int start) {
    if (count == b) {
        MAP[add]++;
    }
    for (int i = start; i<a; i++) {
        if (!visited[i]) {
            visited[i] = true;
            DFS(count+1, add+num[i], i+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> a >> b && a != 0 && b != 0) {
        MAP.clear();
        for (int i = 0; i < a; i++) {
            cin >> num[i];
            visited[i] = false;
        }
        DFS(0, 0, 0);
        int max = -999, maxNum = 0;
        for (auto it:MAP) {
            if (it.second > max) {
                max = it.second;
                maxNum = it.first;
            }
        }
        cout << maxNum << " " << max << "\n";
    }
}

//ZeroJudge D577
//Dr. SeanXD
標籤

相關文章

發佈留言