d547 - 4. 秘密(secrets)
題目描述
題目描述了尋找藏寶圖中正確門的過程。給定一個提示密碼（0 和 1 的序列）和多個門上的數字序列，需要找到與提示密碼匹配的門，並輸出該門的數字序列。匹配規則是根據門上數字序列的差值大小關係生成 0 和 1 的序列。
解題思路
程式碼模擬了題目描述的解法。對於每一扇門，從右向左計算一個由 0 和 1 組成的序列。計算規則是比較相鄰兩個數字的差的絕對值與左邊數字的大小，如果差的絕對值大於等於左邊的數字，則為 1，否則為 0。然後，將計算出的序列與提示密碼進行比較。如果兩個序列相同，則輸出該門的數字序列。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是門的數量，M 是每個數字序列的長度。對於每一扇門，需要遍歷數字序列一次來生成 0 和 1 的序列，然後再遍歷一次來比較序列。
- 空間複雜度: O(M)，主要用於儲存提示密碼、門上的數字序列以及計算出的 0 和 1 的序列。
程式碼
#include <iostream>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
++m;
bool a[m]={0};
int b[m];
for(int i=1;i<m;++i)
cin >> a[i];
while(n--){
for(int i=0;i<m;++i)
cin >> b[i];
bool c[m]={0};
if(b[m-1]>=b[m-2])
c[m-1]=1;
for(int i=m-2;i>0;--i){
int as=abs(b[i]-b[i+1]);
if(as>=b[i-1])
c[i]=1;
}
bool ans=0;
for(int i=0;i<m;++i){
if(a[i]!=c[i]){
ans=1;
break;
}
}
if(ans==0){
for(int i=0;i<m;++i)
cout << b[i] << " ";
cout << "\n";
}
}
}