ZeroJudge 解題筆記：j354. 積木對接 (Blocks)

作者：王一哲
日期：2025年4月15日



ZeroJudge 題目連結：j354. 積木對接 (Blocks)

解題想法

這題將判斷兩個積木是否有解的函式另外寫會比較方便。

Python 程式碼

使用時間約為 94 ms，記憶體約為 3.4 MB，通過測試。

import sys

def solve(bot, top):  # 輸入兩個積木測試是否有解
    n, m = len(bot), len(top)
    if m > n:  # 特例，上方的積木較長，無解
        print("NO"); return
    d = n - m  # 長度差
    for i in range(d+1):  # 短積木的左側位置可能是 0 ~ d
        if all([t&b == 0 for t, b in zip(top, bot[i:i+m])]):
            print("YES"); return
    print("NO"); return

for line in sys.stdin:
    n = int(line)  # 長積木的卡榫數量
    bot = []  # 下方的長積木每格的高度，0 代表低，1 代表高
    h = 0  # 高度，長積木由 0 開始
    for b in map(int, input().split()):  # 依序設定長積木每格的高度
        for _ in range(b): bot.append(h)  # 放入 b 個 h
        h = 1 - h  # 0 變 1 或 1 變 0
    m = int(input())  # 短積木的卡榫數量
    top = []  # 上方的短積木每格的高度，0 代表低，1 代表高
    h = 1  # 高度，短積木由 1 開始
    for t in map(int, input().split()):  # 依序設定短積木每格的高度
        for _ in range(t): top.append(h)  # 放入 t 個 h
        h = 1 - h  # 0 變 1 或 1 變 0
    solve(bot, top)

C++ 程式碼

使用時間約為 2 ms，記憶體約為 368 kB，通過測試。

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

void solve(vector<int>&, vector<int>&);  // 輸入兩個積木測試是否有解

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n;  // 長積木的卡榫數量
    while(cin >> n) {
        vector<int> bot;  // 下方的長積木每格的高度，0 代表低，1 代表高
        int h = 0;  // 高度，長積木由 0 開始
        for(int i=0; i<2*n+1; i++) {  // 依序設定長積木每格的高度
            int b; cin >> b;  // 長積木每區的寬度
            for(int j=0; j<b; j++) bot.push_back(h);  // 放入 b 個 h
            h = 1 - h;  // 0 變 1 或 1 變 0
        }
        int m; cin >> m;  // 短積木的卡榫數量
        vector<int> top;  // 上方的短積木每格的高度，0 代表低，1 代表高
        h = 1;  // 高度，短積木由 1 開始
        for(int i=0; i<2*m-1; i++) {  // 依序設定短積木每格的高度
            int t; cin >> t;  // 短積木每區的寬度
            for(int j=0; j<t; j++) top.push_back(h);  // 放入 t 個 h
            h = 1 - h;  // 0 變 1 或 1 變 0
        }
        solve(bot, top);
    }
    return 0;
}

void solve(vector<int>& bot, vector<int>& top) {  // 輸入兩個積木測試是否有解
    int n = (int)bot.size(), m = (int)top.size();
    if (m > n) {  // 特例，上方的積木較長，無解
        cout << "NO\n"; return;
    }
    int d = n - m;  // 長度差
    for(int i=0; i<=d; i++) {  // 短積木的左側位置可能是 0 ~ d
        // 如果 top 及 bot[i:i+m] 每一格取 & 之後都等於 0，不會卡到，有解
        bool can = true;
        for(int j=0; j<m; j++) {
            if ((top[j] & bot[j+i]) == 1) {
                can = false; break;
            }
        }
        if (can) {
            cout << "YES\n"; return;
        }
    }
    cout << "NO\n"; return;  // 如果能跑完 for 迴圈，無解
}