f384 - 次承的痘痘

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個由 0 和 1 組成的字串，這個字串代表一個經過某種轉換後的痘痘數量編碼。要求我們從這個編碼中反推出原始的痘痘數量。題目提供了一些小數值的編碼作為規律參考。

解題思路

題目提供的編碼方式實際上是將痘痘數量轉換成二進位表示，然後將二進位表示的每一位進行 XOR 運算。具體來說，如果痘痘數量為 x，其二進位表示為 b_n b_{n-1} ... b_1 b_0，那麼編碼字串的每一位 c_i 實際上是 b_i 與 b_{i+1} 的 XOR 運算結果。

程式碼的邏輯是先將輸入的 0 和 1 字串轉換為十進位數 x。然後，從 x 的最高位開始，每次將 x 右移一位，並將右移後的 x 與 y 進行 XOR 運算，直到 x 為 0。最終的 y 值就是原始的痘痘數量。

這個方法實際上是模擬了醫生給出的編碼轉換過程的逆向操作。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為需要遍歷字串一次來計算十進位數，然後進行最多 n 次的右移和 XOR 運算。
• 空間複雜度: O(1)，因為只使用了常數個變數來儲存資料。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);
	string s;
	while(cin >> s){
		long x=0;
		for(int i=0;i<s.size();++i){
			x*=2;
			x+=s[i]-'0';
		}
		long y=x;
		while(x>>=1){
			y^=x;
		}
		cout << y << "\n";
	}
}