f637 - DF-expression
題目描述
題目給定一個由 0、1、2 組成的字串 S，代表一個 n x n 的黑白影像的 DF-expression。n 是 2 的冪次。要求計算原始影像中有多少個像素是 1。DF-expression 的編碼方式是遞迴的：如果所有像素相同，則用 0 (白色) 或 1 (黑色) 表示；否則，將影像分割成四個 n/2 x n/2 的小正方形，並用 2 開頭，然後接上四個小正方形的編碼。
解題思路
這題的核心是解析 DF-expression 字串，並根據其結構計算影像中 1 的數量。程式使用一個貪婪的策略來解析字串。it 變數追蹤目前遞迴的深度，c[it] 記錄在深度 it 中遇到的 0 和 1 的數量。當遇到 '2' 時，遞迴深度增加；當遇到 '1' 時，計算在目前深度下，有多少個 n/(1<<it) x n/(1<<it) 的區域是黑色的，並將其加到答案中。c[it] 記錄了在該深度遇到的 0 和 1 的數量，當 c[it] 等於 4 時，表示該深度下的四個子區域都已處理完畢，遞迴深度減小。
複雜度分析
- 時間複雜度: O(S)，其中 S 是輸入字串的長度。因為程式只需要遍歷一次字串。
- 空間複雜度: O(n)，其中 n 是影像的大小。因為
c陣列的大小是 1025，而 n 最大是 1024。
程式碼
#include <iostream>
using namespace std;
string a;
long long int n,c[1025],it;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> a >> n;
long long int al=a.length(),ans=0;
for(int i=0;i<al;++i){
if(a[i]=='2'){
++it;
}
else{
if(a[i]=='1'){
ans+=(n/(1<<it))*(n/(1<<it));
}
++c[it];
if(c[it]==4){
while(c[it]==4){
c[it]=0;
++c[it-1];
--it;
}
}
}
}
cout << ans ;
}