a364 - 2. 神秘的進位問題
題目描述
題目要求將一個十進位數字 N 轉換成神秘國度的進位表示法 abc，其中 a > b > c >= 0，且 N = C(a, 3) + C(b, 2) + C(c, 1)，C(m, n) 為二項係數。
解題思路
由於 N 的範圍較小 (0 <= N <= 500)，我們可以預先計算所有可能的 abc 組合，並將其對應的 N 值儲存起來。然後，對於每個輸入的 N，我們只需查找預先計算好的結果即可。預計算時，我們按照 a, b, c 的大小進行遍歷，確保找到字典序最小的解。二項係數的計算使用 cc(m, n) 函數，當 m < n 時返回 0。
複雜度分析
- 時間複雜度: O(a^3)，其中 a 是預計算時的最大 a 值 (在本程式碼中為 501)。 預計算部分的時間複雜度是固定的，查詢部分的時間複雜度是 O(1)。
- 空間複雜度: O(501^2)，用於儲存預計算的結果
ans陣列。
程式碼
#include <iostream>
using namespace std;
int ans[501][3],al=0;
int cc(int m,int n){
if(m<n)return 0;
if(n==1)return m;
else if(n==2)return m*(m-1)/2;
return m*(m-1)*(m-2)/6;
}
int main(){
for(int a=2;al<501;++a){
int t1=cc(a,3);
for(int b=1;b<a&&al<501;++b){
int t2=cc(b,2)+t1;
for(int c=0;c<b&&al<501;++c){
int tmp=t2+cc(c,1);
if(tmp<501&&ans[tmp][0]==0){
++al;
ans[tmp][0]=a;
ans[tmp][1]=b;
ans[tmp][2]=c;
}
}
}
}
int n;
while(cin >> n){
int k;
while(n--){
cin >> k;
for(int i=0;i<3;++i){
cout << ans[k][i];
}
cout << "\n";
}
}
}