牛客 Round-72. 小红的01串(三)
原题链接
简单
作者:
YMYS
,
2024-12-16 15:15:02
,
所有人可见
,
阅读 7
/*
* @Author: YMYS
* @Date: 2024-02-25 21:38:22
* @LastEditTime: 2024-12-16 15:14:31
* @FilePath: \VScode-C&C++-Coding\newcode\round\72\3_noself.cpp
* @URL:https://ac.nowcoder.com/acm/contest/98256/C
* @Description: 小红的01串(三)
*/
#include<bits/stdc++.h>
using namespace std;
int T,a,b,k;
void solve(){
//a:0 b:1 k:01字符对
cin>>a>>b>>k;
//A对应a,B对应b
char A='0', B='1';
//《特判》
//1、第一种情况:
//a和b组成的01串,在做01对最多的情况下都满足不了给的要求k
//这种情况需要分a和b相不相等,eg:10101 4个01对;1010 3个01对
//2、第二种情况:
//k为0,但是min(a,b)不为0,所以导致最少最少会有1个01对,这样也无法满足要求k
//3、额外思考:
//综合考虑1、2两种情况,假如k不为0,会不会存在说:
//a和b组成的01串,在做01对最少的情况下都超过了给的要求k呢?
//答案:不会,因为最少我们可以做到只有1个01对
if(2*min(a,b) - (a==b) < k || k==0 && min(a,b)>0){
cout<<-1<<endl;
return ;
}
//为了后续方便讨论,以及插入字符更灵活,我们这里将字符数多的char做第一个字符
//为此我们对a和b的数量进行讨论,必须保证a大b小
if(a<b){
swap(a,b);
swap(A,B);
}
string str;
str.push_back(A);//先把个数多的字符做第一个
a--;
//接下来开始交替插入01字符
//我们每插入一个字符,01字符对就会每多一个
int tmp = 1;
for(int i=1;i<=k;i++){//!!!!!!!!!!!!!while(a&&b)!!!!!!!!!!!
if(tmp){
str.push_back(B);
b--;
}else{
str.push_back(A);
a--;
}
// cout<<"tmp: "<<tmp<<endl;
tmp ^= 1;
}
//最后补字符的时候,我们在str最前面补数量大的字符,在str末尾补数量少的那个字符
//但是为了防止新增01对,我们需要检测一下最后一个是不是数量少的那个字符
if(str.back() == B){
// str.pop_back();
//为什么这里不用弹出了呢?
//因为最后一个已经是数量少的那个字符了,我们直接在其后面插入相同的字符即可,01对也不会增加
while(a){
str = A + str;
a--;
}
while(b){
str = str + B;
b--;
}
}else{
str.pop_back();//弹出末尾字符
while(a){
str = A + str;
a--;
}
while(b){
str = str + B;
b--;
}
str.push_back(A);
}
cout<<str<<endl;
}
int main()
{
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
cin>>T;
while(T--){
solve();
}
return 0;
}
这道题我在进行这个判断的时候【str.back() == B】,不小心写成了【str.back() == ‘B’】发现居然也过了60%的数据。可以发现只要考虑够全面,哪怕漏了某一种特殊的情况,也会过很多的数据。