2026牛客寒假算法基础集训营4 | F 爱音的01串构造 题解

题目描述:

输入描述:

输出描述:

思路：

mex的取值规则为

子串全为 1 → mex = 0

子串全为 0 → mex = 1

子串同时包含 0 和 1 → mex = 2

要最大化总和,等价于最小化全0和全1子串的数量,因为混合子串的贡献最大

因此我们先求出0可将1分成几段和1可将0分成几段，若多出则从前往后一次多加一个位置，判断谁的段数多，段数多的先放

根据代码例如6个0 2个1

0分成3段，1分成2段，先放0，数组0每段为2一共3段duan0[0]=2,duan0[1]=2,duan0[2]=2接下来每段放2个0，因为没有余数所以不用增加每段0的个数，1被分成的段数同理,则最后为00100100

using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--){
		int a,b;
		cin>>a>>b;
		if(a==0){
			cout<<string(b,'1')<<"\n";
			continue;
		}
		if(b==0){
			cout<<string(a,'0')<<"\n";
			continue;
		}
		int duan0=min(a,b+1);
		int duan1=min(b,a+1);
		vector<int> avg0(duan0,a/duan0);
		vector<int> avg1(duan1,b/duan1);
		for(int i=0;i<a%duan0;i++){
			avg0[i]++;
		}
		for(int i=0;i<b%duan1;i++){
			avg1[i]++;
		}
		bool fir=1;
		if(duan0>duan1){
			fir=0;
		}
		int cnt1=0,cnt0=0;
		string s="";
		while(cnt1<duan1 || cnt0<duan0){
			if(fir){
				if(cnt1<duan1){
					s.append(avg1[cnt1],'1');
					cnt1++;
				}
				if(cnt0<duan0){
					s.append(avg0[cnt0],'0');
					cnt0++;
				}
			}else{
				if(cnt0<duan0){
					s.append(avg0[cnt0],'0');
					cnt0++;
				}
				if(cnt1<duan1){
					s.append(avg1[cnt1],'1');
					cnt1++;
				}
			}
		}
		cout<<s<<"\n";
	}
}