c675 - 吉數

🔗 前往 ZeroJudge 原題

題目描述

題目要求我們建立一個函數，能夠在電腦上的流水編號（可能包含數字 4）和名牌上的號碼（不包含數字 4）之間進行轉換。如果輸入是 'T'，則將電腦上的號碼轉換為名牌上的號碼；如果輸入是 'F'，則將名牌上的號碼轉換為電腦上的號碼。

解題思路

由於號碼的範圍有限（1 到 10000），我們可以預先計算出所有可能的轉換。我們使用兩個陣列 a 和 b。a[i] 儲存的是電腦上的第 i 個號碼轉換為名牌上的號碼，b[i] 儲存的是名牌上的第 i 個號碼轉換為電腦上的號碼。

預計算的過程如下：

1. 遍歷從 0 到 10000 的所有數字。
2. 對於每個數字，檢查它是否包含數字 4。如果包含，則將數字加 1，直到不包含數字 4 為止。
3. 將原始數字的索引 i 儲存在 a 陣列中，將轉換後的數字儲存在 b 陣列中。

在輸入處理部分，我們讀取一個字元 x 和一個整數 it。如果 x 是 'T'，則輸出 a[it]；如果 x 是 'F'，則輸出 b[it]。

複雜度分析

• 時間複雜度: O(N + Q)，其中 N 是最大號碼（10000），Q 是查詢次數。預計算需要 O(N) 的時間，查詢需要 O(1) 的時間，總共 Q 次查詢需要 O(Q) 的時間。
• 空間複雜度: O(N)，因為我們需要儲存兩個大小為 10001 的陣列 a 和 b。

程式碼

#include <iostream>
using namespace std;
int a[10001],b[15752];
inline bool four(int k){
	while(k){
		if(k%10==4)return 1;
		k/=10;
	}
	return 0;
}
char x;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int it=0;
	for(int i=0;i<10001;++i,++it){
		while(four(it))
			++it;
		a[i]=it;
		b[it]=i;
	}
	while(cin >> x >> it)
		if(x=='T')
			cout << a[it] << "\n";
		else
			cout << b[it] << "\n";
}