d108 - NOIP 2008 2.火柴棍等式
題目描述
題目要求計算使用給定的火柴棍數量 n，可以組成多少個形如 "A + B = C" 的等式。其中 A、B、C 都是用火柴棍拼成的非負整數，且等式中的加號和等號各自需要兩根火柴棍。
解題思路
這道題可以使用深度優先搜尋 (DFS) 或回溯法來解決。基本思路是枚舉所有可能的 A、B、C 的組合，並檢查它們是否滿足以下條件：
- A、B、C 的火柴棍數量之和等於
n。 - A + B = C。
- A、B、C 的最高位不能為 0 (除非它們是 0)。
程式碼中，m[i] 儲存了拼寫數字 i 所需的火柴棍數量。dfs 函數遞迴地構建 A、B、C，並檢查是否滿足條件。type 變數用於追蹤目前正在構建的數字是 A、B 還是 C。
複雜度分析
- 時間複雜度: O(10^n)。由於火柴棍數量有限，且每個數字的火柴棍數量也是有限的，因此搜尋空間的大小是有限的。
- 空間複雜度: O(n)。主要來自於遞迴調用的堆疊空間。
程式碼
#include <iostream>
using namespace std;
int m[10]={6,2,5,5,4,5,6,3,7,6},n,ans;
void dfs(int x1,int y1,int sum,int tmp,int type){
if(tmp>n||sum>x1+y1)return;
if(type==1){
for(int i=0;i<10;++i){
if(x1!=0)dfs(x1*10+i,y1,sum,tmp+m[i],1);
}
for(int i=0;i<10;++i){
dfs(x1,i,sum,tmp+m[i],2);
}
}
else if(type==2){
for(int i=0;i<10;++i){
if(y1!=0)dfs(x1,y1*10+i,sum,tmp+m[i],2);
}
for(int i=0;i<10;++i){
dfs(x1,y1,i,tmp+m[i],3);
}
}
else{
if(tmp==n&&x1+y1==sum){
// cout << x1 << " " << y1 << " " << sum << "\n";
++ans;
return;
}
for(int i=0;i<10;++i){
if(sum!=0)dfs(x1,y1,sum*10+i,tmp+m[i],3);
}
}
}
int main(){
while(cin >> n){
ans=0;
n-=4;
for(int i=0;i<10;++i){
dfs(i,0,0,m[i],1);
}
cout << ans << "\n";
}
}