526互联

Educational Codeforces Round 152 (Rated for Div. 2) C. Binary String Copying

发布时间 2023-08-01 16:52:51作者: 突破铁皮

题目大意为给定一个01字符串，给定m个区间，对于每个区间进行一次局部排序，求能得到的字符串种类数

解法：因为字符串只包含0，1两个字符，我们观察可以得到，对于不同的区间来说如果排序后一样则说明肯定是某些位置在排序过程中无贡献，因此我们只需找出有贡献的位置即可

对于一个区间[l,r],来说，如果进行排序，首先肯定是最右边的0和最左边的1位置发生变换

因此我们先预处理一下，先预处理1，对于1来说每次寻找最左边的1，对于右边的0来说，优先交换最右边的，再预处理0，对于0来说每次寻找最右边的0，对于左边的1来说优先交换最右边的0

例如0101,我们选取0101和101是一样的，因为最右边的0一样，最左边的1一样

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int N=2e5+10;
typedef pair<int,int> PII;
char s[N];
int t,n,m;
int L[N],R[N];
set<PII> st;
void solve(){
	st.clear();
	cin>>n>>m;
	cin>>s+1;
	int last=N;
	for(int i=n;i;i--){
		if(s[i]=='1'){//如果是1就更新上次出现的1，使得1为最左边的
			last=i;
		}
		L[i]=last;
	}
	last=-1;
	for(int i=1;i<=n;i++){
		if(s[i]=='0'){//如果是0就更新上次出现的0，使得0为最右边的
			last=i;
		}
		R[i]=last;
	}
	while(m--){
		int l,r;
		cin>>l>>r;
		l=L[l];
		r=R[r];
		if(r<=l) l=r=0;//说明该段全0或者全1，不影响
		st.insert({l,r});
	}
	cout<<st.size()<<endl;
}
int main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
	solve();
}
}