facebook.com/codingcompetitions/hacker-cup/..

由於只要寫一題便可以通關，所以我只在時間內寫了 A 和 B1，賽後補了 C1 + C2，沒寫 D。

Problem A: Second Hands

題目連結

題意整理

1. 兩個展示櫃
2. 一個展示櫃最多只能擺 \( K \) 個時鐘
3. 每個展示櫃不能有相同種類的時鐘

題解

直接按照題意整理檢查就好。

Code

#include <iostream>
#include <vector>

int main() {
    const size_t MAX_S = 100;
    size_t T;
    std::cin >> T;
    for (size_t lt = 1; lt <= T; ++lt) {
        size_t N, K;
        std::vector<size_t> cntStyle(MAX_S + 1);
        std::cin >> N >> K;

        bool has3 = false;
        for (size_t ln = 0; ln < N; ++ln) {
            size_t s;
            std::cin >> s;
            ++cntStyle[s];
        }

        for (size_t c : cntStyle) {
            if (c >= 3) {
                has3 = true;
                break;
            }
        }

        auto ans = (N > 2 * K || has3) ? "NO" : "YES";
        std::cout << "Case #" << lt << ": " << ans << std::endl;
    }

    return 0;
}

Problem B: Second Friend

題目連結

題意整理

1. \(R\times C\) 的棋盤
2. 棋盤上有一些預先擺上的樹和石頭
3. 你要在沒有石頭得格子擺上樹，讓每個樹都至少有兩個鄰居樹。

題解

假如一開始就沒有樹的話那就 ok，接下來考慮一開始至少有一棵樹的情況。

\(R = 1\) 或 \(C = 1\) 一定無法完成。

假如沒有石頭的情況下把所有地方都放上樹，就一定可以滿足。但因為有石頭，就會出現死路的情況。所以需要設法把死路排除，留下環。

Example:

理論上要用 BFS ，但這裡這裡我用了遞迴去 DFS ，所以遇到螺旋狀迷宮直接炸 Stack ，來不及了😭。賽後也沒辦法重新測試，就不放 Code 了。

Problem C: Second Meaning

題目連結

題意整理

給定一個摩斯單字，要生出另外 \(N-1\) 個長度不超過 \(10\) 的單字。主要限制在於生出單字的長度。

題解

主要的想法：

• 霍夫曼編碼的限制：摩斯單字只能出現在葉子。
• \(S = \) { \(00000000_2 ... 11111111_2\) } 可以形成 256 個不衝突的摩斯單字。

假如 \(C_1\) 以 0 開頭，那麼就讓 S 裡面所有單字在前面加上 1 ，反正就是不要和 \(C_1\) 相同開頭。

Code

#include <iostream>
#include <set>
#include <string>
#include <vector>

std::vector<std::string> solve(size_t n, const std::string& c1) {
    std::set<std::string> hub;

    for (int sts = 0; sts < (1 << 8); ++sts) {
        std::string s(8, '.');
        for (int lx = 0; lx < 8; ++lx) {
            if (sts & (1 << lx)) {
                s[lx] = '-';
            }
        }

        hub.insert(std::move(s));
    }

    std::string newC1;
    if (c1[0] == '.') {
        newC1 = "-";
    } else {
        newC1 = ".";
    }

    std::vector<std::string> ans;

    for (const auto& s : hub) {
        ans.push_back(newC1 + s);
        if (ans.size() == n - 1) {
            return ans;
        }
    }

    return ans;
}

int main() {
    size_t T;
    std::cin >> T;
    for (size_t lt = 1; lt <= T; ++lt) {
        size_t N;
        std::string s;
        std::cin >> N >> s;

        auto ans = solve(N, s);

        std::cout << "Case #" << lt << ":" << std::endl;
        for (const auto& c : ans) {
            std::cout << c << std::endl;
        }
    }

    return 0;
}