Codeforces Round #704 (Div. 2) D. Genius’s Gambit

題意

要求構造出兩個不包含前導0的二進制數字 x , y x,y x,y，滿足：

• x , y x,y x,y都具有 a a a個 0 0 0和 b b b個 1 1 1
• x ? y x-y x?y具有 k k k個 1 1 1

限制

a ≥ 0 a\ge 0 a≥0

b ≥ 1 b\ge 1 b≥1

0 ≤ k ≤ a + b ≤ 2 ? 1 0 5 0\le k\le a+b\le 2\cdot 10^5 0≤k≤a+b≤2?105

思路

顯然的，由于要求 x , y x,y x,y不包含前導 0 0 0，故兩數字最高位必定為 1 1 1

特殊討論 k = 0 k=0 k=0時，根據上述約束，直接輸出兩個字串即可

注意先輸出 b b b個 1 1 1再輸出 a a a個 0 0 0

否則，觀察樣例，自己多寫幾個例子，可以發現這個規律

中間位對應都相同時，計算減法可以直接當作 X ? X = 0 X-X=0 X?X=0

那么假如這一段的長度為 t t t，減數最高位為 1 1 1，被減數最低位為 1 1 1，其余 t ? 1 t-1 t?1個位置均為 0 0 0

那做減法得到的結果即 2 t ? 1 ? 1 2^{t-1}-1 2t?1?1，其二進制則包含 t ? 1 t-1 t?1個 1 1 1

那么只要 k ≠ 0 k\neq 0 k?=0，就需要保證至少要有 2 2 2個 1 1 1與 1 1 1個 0 0 0，且 k ≤ a + b ? 2 k\le a+b-2 k≤a+b?2

答案總體可以分成以下三個部分（其中后兩個部分位置可以隨意調換）

程式

#include<bits/stdc++.h>
using namespace std;

void solve()
{
    int a,b,k;
    cin>>a>>b>>k;
    
    if(k==0)
    {
        cout<<"Yes\n";
        for(int i=1;i<=b;i++)
            cout<<1;
        for(int i=1;i<=a;i++)
            cout<<0;
        cout<<'\n';
        for(int i=1;i<=b;i++)
            cout<<1;
        for(int i=1;i<=a;i++)
            cout<<0;
        cout<<'\n';
        return;
    }
    
    if(a<1||b<2||k>a+b-2)
    {
        cout<<"No\n";
        return;
    }
    
    string x="1",y="1";
    b--;
    
    x+='1';
    y+='0';
    a--,b--;
    
    for(int i=1;i<k;i++)
    {
        if(a>0)
        {
            a--;
            x+='0';
            y+='0';
        }
        else if(b>0)
        {
            b--;
            x+='1';
            y+='1';
        }
    }
    
    x+='0';
    y+='1';
    
    while(a--)
    {
        x+='0';
        y+='0';
    }
    while(b--)
    {
        x+='1';
        y+='1';
    }
    
    cout<<"Yes\n"<<x<<'\n'<<y<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    solve();
    return 0;
}

https://www.cnblogs.com/stelayuri/p/14437470.html