QOJ504#1289 A + B Problem题解

Iceturky · 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;
}