e583 - 11040 - Add bricks in the wall
題目描述
題目描述了一個三角形牆壁，其中一些磚塊的數字已知，要求根據「磚塊的數字是其下兩個磚塊數字之和」的規則，填補剩餘的磚塊數字。
解題思路
這道題的核心是模擬題目描述的填補規則。首先，讀取奇數行的已知數字。然後，從第二行開始，根據下方的兩個數字計算當前行的數字。最後，從倒數第二行開始，根據下一行的兩個數字計算當前行的數字。由於第九行沒有下方的磚塊，因此不需要計算。
程式碼首先初始化一個 10x10 的二維陣列 a，然後讀取奇數行的已知數字。接著，使用兩個迴圈計算中間行的數字，最後計算倒數第二行到第一行的數字。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是牆壁的行數 (在本例中為 10)。因為需要遍歷整個陣列來計算每個磚塊的數字。
- 空間複雜度: O(n^2)，因為使用了一個 10x10 的二維陣列
a來儲存牆壁的數字。
程式碼
#include <iostream>
using namespace std;
int a[10][10];
int main(){
int t;
cin >> t;
while(t--){
for(int i=0;i<10;++i)
for(int j=0;j<10;++j)
a[i][j]=0;
for(int i=0;i<10;i+=2)
for(int j=0;j<=i;j+=2)
cin >> a[i][j];
for(int i=2;i<10;i+=2)
for(int j=1;j<i;j+=2)
a[i][j]=(a[i-2][j-1]-a[i][j-1]-a[i][j+1])/2;
for(int i=1;i<10;i+=2)
for(int j=0;j<=i;++j)
a[i][j]=a[i+1][j]+a[i+1][j+1];
for(int i=0;i<9;++i){
for(int j=0;j<=i;++j)
cout << a[i][j] << " ";
cout << "\n";
}
}
}