h927 - 【h927】，窩的超人

🔗 前往 ZeroJudge 原題

題目描述

題目描述ㄌㄌ未之公的故事，並要求計算將字串 b 的字元依序加入字串 a 的最左邊或最右邊後，所形成的二進位字串的最大十進位值（模 998244353）。

解題思路

這題的核心在於貪心策略。為了使最終的二進位數最大，我們應該盡可能將 '1' 字元放在高位。因此，在將 b 的字元加入 a 時，如果 b 的當前字元是 '1'，則應將其加到 a 的最左邊；如果 b 的當前字元是 '0'，則應將其加到 a 的最右邊。

程式碼中，ans 儲存目前形成的二進位數的值，ba 儲存 2 的冪，用於計算二進位數的值。對於 b 中的每個字元，如果字元是 '1'，則將 ba 加到 ans，表示將 '1' 放在高位；如果字元是 '0'，則將 ans 左移一位（相當於乘以 2），表示將 '0' 放在低位。所有操作都對 998244353 取模。

複雜度分析

• 時間複雜度: O(m)，其中 m 是字串 b 的長度。因為我們需要遍歷字串 b 一次。
• 空間複雜度: O(1)，因為我們只使用了常數級別的額外空間。

程式碼

#include <iostream>
using namespace std;
long n,m,ans,mod=998244353,ba=1;
string a,b;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n >> m >> a >> b;
	for(int i=0;i<n;++i){
		ans=(ans*2)%mod;
		ba=(ba*2)%mod;
		if(a[i]=='1')ans+=1;
	}
	for(int i=0;i<m;++i){
		(b[i]=='1')?ans+=ba:ans<<=1;
		ans%=mod;
		ba=(ba*2)%mod;
	}
	cout << ans;
}