01串题【牛客tracker 每日一题】

01串题

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

你有a aa个0 00，和b bb个1 11，你需要用这些01 0101字符构造出一个长度为a + b a+ba+b的01 0101字符串，随后小红会进行无数次操作，每次操作会选择一对相邻且相同的字符，并将他们删除，然后将剩余的字符串拼接起来。直到无法进行该操作为止。
你需要保证你构造出的字符串在经过小红的的无数次操作之后，剩余字符串长度为x xx。

输入描述：

第一行输入三个非负整数a aa,b bb,x xx，分别代表0 00,1 11的数目和最后的字符串长度。

0 ≤ a , b , x ≤ 1 0 5 0≤a,b,x≤10^50≤a,b,x≤105，且a aa、b bb不同时为0 00。

保证x xx一定是偶数。

输出描述：

输出你构造出来的字符串，如果无法构造出来，那么输出− 1 -1−1。

示例1

输入：

3 1 2

输出：

0001

说明：

我们可以将23位置删除，最后生成字符串01长度为2

示例2

输入：

2 1 2

输出：

-1

说明：

我们无法生成字符串

解题思路

首先将目标剩余长度x xx除以2 22（因剩余字符串为01 0101交替结构，每对01 0101占长度2 22），再将0 00的数量a aa和1 11的数量b bb分别减去x xx（对应剩余部分所需的x xx个0 00和x xx个1 11），随后判断是否满足a 、 b a、ba、b非负且均为偶数（多余的0 00和1 11需成对出现才能被完全删除），若不满足则输出− 1 -1−1；若满足则先构造x xx个“01 0101”作为剩余的核心部分，再将多余的0 00和1 11依次追加在后面（这些成对的字符会在操作中被删除）；该方法通过数学推导确定构造的条件和字符串结构，避免模拟删除操作，时间复杂度为O ( a + b ) O(a+b)O(a+b)，适配a 、 b 、 x a、b、xa、b、x达1 e 5 1e51e5的规模，高效判断是否可构造并精准输出对应字符串。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;intmain(){ll a,b,x;cin>>a>>b>>x;x/=2,a-=x,b-=x;if(a<0||b<0||a&1||b&1)cout<<"-1\n";else{while(x--)cout<<"01";while(a--)cout<<"0";while(b--)cout<<"1";cout<<endl;}}