e463 - Error
題目描述
題目要求找出所有由給定數字 s 開始，透過特定規則生成的數字序列。生成規則是，從當前數字 s 出發，可以選擇一個 i (1 <= i <= s/2)，並將 i * 10^k + s 加入序列，其中 k 是 i 的位數。這個過程可以遞迴進行，直到無法再生成新的數字。最後，輸出序列中數字的數量，並將序列中的數字排序後輸出。
解題思路
這題的核心是使用深度優先搜尋 (DFS) 來遍歷所有可能的數字序列。dfs 函數從給定的起始數字 s 開始，遞迴地生成新的數字，並將其添加到 ans 向量中。lDP 陣列用於計算 10 的冪，DP 陣列用於計算數字 i 的位數。在 main 函數中，讀取輸入數字 s，初始化 ans 向量，調用 dfs 函數生成序列，然後對序列進行排序並輸出結果。
複雜度分析
- 時間複雜度: O(N!)，其中 N 是輸入數字 s。在最壞的情況下，DFS 可能需要遍歷所有可能的數字組合。
- 空間複雜度: O(N)，主要用於儲存
ans向量和遞迴調用堆疊。
程式碼
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector <ll> ans;
ll DP[105],lDP[16]={1};
void dfs(ll s,ll n,ll len){
ans.push_back(s);
for(ll i=1;i<=n/2;++i)
dfs(i*lDP[len]+s,i,len+DP[i]);
}
//136,122,550,100
int main(){
cin.tie(0); ios::sync_with_stdio(0);
ll s;
for(ll i=1;i<=15;++i)
lDP[i]=lDP[i-1]*10;
for(ll i=1;i<=100;++i){
if(i<10)DP[i]=1;
else if(i<100)DP[i]=2;
else DP[i]=3;
}
while(cin >> s){
ans.clear();
dfs(s,s,DP[s]);
cout << ans.size() << "\n";
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i)
cout << ans[i] << " ";
cout << "\n";
}
}