j354 - 積木對接 (Blocks)

🔗 前往 ZeroJudge 原題

題目描述

題目給定兩個積木序列 a 和 b，分別由 0 和 1 組成。目標是判斷是否存在一個位置，使得 b 序列可以完全嵌入到 a 序列中，且嵌入時，相同位置上的積木顏色相同（0+0 或 1+1）。如果存在這樣的嵌入位置，輸出 "YES"，否則輸出 "NO"。

解題思路

這題的核心思想是使用滑動視窗 (Sliding Window) 技巧。我們將 b 序列視為一個視窗，在 a 序列上滑動。對於每個視窗位置，我們檢查視窗內的元素是否與 b 序列的元素匹配。匹配的條件是 a[i+j] + b[j] <= 1，即兩個位置上的積木顏色相同。如果對於某個視窗位置，所有元素都匹配，則說明 b 序列可以嵌入到 a 序列中，輸出 "YES" 並結束程式。如果滑動視窗遍歷完 a 序列的所有可能位置，仍然沒有找到匹配的視窗，則輸出 "NO"。

複雜度分析

• 時間複雜度: O(n*m)，其中 n 是 a 序列的長度，m 是 b 序列的長度。因為需要遍歷 a 序列的所有可能視窗位置，並且對於每個位置，需要比較 b 序列的所有元素。
• 空間複雜度: O(n+m)，主要用於儲存 a 和 b 序列。

程式碼

#include <iostream>
using namespace std;
int n,m,a[10001],b[10001],x,sa,sb;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> n;
	for(int i=0;i<n*2+1;++i){
		cin >> x;
		while(x--)
			a[sa++]=i%2;
	}
	cin >> m;
	for(int i=0;i<m*2-1;++i){
		cin >> x;
		while(x--)
			b[sb++]=(i+1)%2; 
	}
	for(int i=0;i<=sa-sb;++i){
		bool ok=1;
		for(int j=0;j<sb;++j)
			if(a[i+j]+b[j]>1){
				ok=0;
				break;
			}
		if(ok){
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
}