j032 - 11933 - Splitting Numbers

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入的十進位數 n 轉換為二進位，然後將二進位數中的奇數位置的 1 組合成數 a，偶數位置的 1 組合成數 b，最後輸出 a 和 b 的十進位表示。

解題思路

解題思路是將輸入的十進位數 n 轉換為二進位表示，然後從最低位開始遍歷二進位數。如果當前位是 1，則根據其位置（奇數或偶數）將其添加到對應的數 a 或 b 中。使用位運算 n % 2 判斷當前位是否為 1，並使用 n /= 2 將 n 右移一位。ba 變數用於追蹤當前位的權重。

複雜度分析

• 時間複雜度: O(log n) (因為需要遍歷 n 的二進位表示，其長度為 log n)
• 空間複雜度: O(1) (只使用了常數個變數)

程式碼

#include <iostream>
using namespace std;
long n;
int main(){
	cin.tie(0); ios::sync_with_stdio(0);
	while(cin >> n){
		if(n==0)return 0;
		long a=0,b=0;
		for(long i=0,ba=1,c=0;i<32;++i,ba*=2,n/=2)
			if(n%2){
				++c;
				(c%2)?a+=ba:b+=ba;
			}
		cout << a << " " << b << "\n"; 
	}
}