Qingshan Loves Strings 2 题解

我不知道为神马这些题解这么……长。

说一下我的思路。

第一步（没啥用）

首先，可证明如果

s

中

1

与

0

数量不一样，那么一定不可行。

为什么？因为结果

s

中

1

与

0

数量一定一样，而操作不改变

s

中

1

与

0

数量差。

第二步

此题一定是先处理两端，再处理中间的。因为对中间的操作不会影响两端。

我们把题中的

k−i+1

设为

j

，有以下三种情况：

$s_i≠s_j$ 直接跳过。
$s_i=s_j=0$ 在 $j$ 后插入。
$s_i=s_j=1$ 在 $i$ 前插入。

CPP

#include<bits/stdc++.h>
using namespace std;
int T,n;
string s;
void add(string &s,int x){
	s=s.substr(0,x)+"01"+s.substr(x);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>s;
		vector<int>cnt(2);
		for(int i=0;i<n;i++){
			cnt[s[i]-'0']++;
		}
		if(cnt[1]!=cnt[0]){
			cout<<"-1\n";
			continue;
		}
		vector<int>a;
		for(int i=0;i<s.size();i++){
			int t=s.size()-i-1;
			if(s[i]!=s[t]) continue;
			if(s[i]=='0'){
				add(s,t+1);
				a.emplace_back(t+1);
			}
			else{
				add(s,i);
				a.emplace_back(i);
			}
			if(a.size()>300) break;
		}
		if(a.size()>300) cout<<"-1\n";
		else{
			cout<<a.size()<<'\n';
			for(int i:a) cout<<i<<' ';
			cout<<'\n';
		}
	}
	return 0;
}

Qingshan Loves Strings 2 题解

文章操作

第一步（没啥用）

第二步

相关推荐

评论

Qingshan Loves Strings 2 题解