本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-06-25 20:42:54

题意：

给出一个长度为 $n+m$ 的 01串，要求将其划分为两个子序列 $a$ 和 $b$ ，长度分别为 $n$ 和 $m$ ，使每一个元素都恰好在一个子序列内，使这两个子序列视为二进制数后加和最大，求出二进制下最大加和。

scallion 赛时的做法是：使 $n>m$ ，将前 $m$ 个位分给 $b$ ，后 $n$ 个位给 $a$ ，然后两个指针从分界处开始分别往左和右扫，对于左边扫到的 $1$ ，若右边扫到的 $0$ 位权比自己大则交换。

感觉有点对，但不知道为啥能取到上界。

code

const int N=1e6+5;

char s[N];

int ans[N];

signed main(){
	signed _T=read();
	while(_T--){
		int n=read(),m=read();
		scanf("%s",s+1);
		if(n>m)swap(n,m);
		int l=n,r=n+1;
		while(1){
			while(l>0&&s[l]=='0')
				l--;
			while(r<=n+m&&s[r]=='1')
				r++;
			if(l>0&&r<=n+m&&n+m-r>n-l)
				swap(s[l],s[r]);
			else
				break;
		}
		for(int i=1;i<=m;i++)
			ans[i]=s[n+m-i+1]-'0';
		for(int i=1;i<=n;i++)
			ans[i]+=s[n-i+1]-'0';
		for(int i=1;i<=n+m;i++)
			ans[i]+=ans[i-1]>>1,ans[i-1]&=1;
		int len=n+m;
		while(len>1&&ans[len]==0)len--;
		for(int i=len;i>=1;i--)
			pc(ans[i]+'0'),ans[i]=0;
		pc('\n');
	}
	return 0;
}