首页 > 其他分享 >Educational Codeforces Round 152 (Rated for Div. 2) C. Binary String Copying

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

时间:2023-08-01 16:56:21浏览次数:54  
标签:Binary Educational Rated last int 右边 排序 区间 include

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

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

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

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

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

换句话说,我们只需关心需要需要排序的区间大小,即第一个出现在0前面的1和最后一个出现为1后面的0,这一段就是需要排序的区间

#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();
}
}

 

标签:Binary,Educational,Rated,last,int,右边,排序,区间,include
From: https://www.cnblogs.com/liyiyang/p/17596966.html

相关文章

  • Binary String Copying
    Smiling&Weeping----第一次见你的时候,在我的心里已经炸成了烟花,需要用一生来打扫灰炉。题目链接:Problem-C-Codeforces题目大意不难,就是把每种......
  • Educational Codeforces Round 152 (Rated for Div. 2)
    传送阵T1MorningSandwich题目大意\(t\)个测试,每个测试给三个正整数\(b,c,h\),分别表示面包和两种馅料的个数,每两个面包之间必须放一个馅料,问最多能摆几层?思路我们发现\(c,h\)所表示的两种馅料其实相差不大,所以我们可以分两种情况\(a>c+h\)因为开头总是面包,所以要+......
  • CF1849C Binary String Copying
    Link我们想一下,什么时候两种变换是相同的或者说,这意味着什么。本题目有特殊性,特殊性就在于只有0和1对于每一个被改变的区间\([L_i,r_I]\),从\(l_i\)开始的那一堆0,和从\(r_i\)开始的那一堆1都没变。所以变化的部分就要从从左往右第一个1,和从右往左第一个0开始算。这个东西可以......
  • Educational Codeforces Round 152 (Rated for Div. 2) 题解
    \(6\)题做出来\(3\)题,这一次的D题没能复刻上一次Round888Div.3最后几分钟AC的奇迹A.MorningSandwich大水题,5min时间4min都在翻译题面直接拿\(b\)和\(c+h\)进行比较分类讨论即可单次操作时间复杂度\(O(1)\)B.Monsters首先有一个特别显然、复杂度特别高的......
  • stm32cubeide ioc报错 This IOC file has been generated with CubeMX version 5.6.1
    STM32Cubemx文件的版本不一致导致打不开.ioc文件的问题问题:ThisIOCfilehasbeengeneratedwithCubeMXversion5.6.1YourcurrentCubeMXversionis5.0.0PleaseupdatetoanewestCubeMXversiontobeabletoopenthisIOC.笔者遇到这个问题后,就开始升级程序,但是升级......
  • Educational Round 147
    前言:非常好场次编号,爱来自小粉兔。唉,GF。A.shaber模拟。B.shaber。找最大的满足\(a_{l\simr}\)和\(a'_{l\simr}\)有不同,且\(a'_{l\simr}\)递增的\(\langlel,r\rangle\)即可。\(\mathcalO(n)\)。C.shaber。枚举字符\(c\),非\(c\)最大连续段长是\(k\)的......
  • Educational Codeforces Round 152 (Rated for Div. 2)记录
    A.MorningSandwich#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#include<string.h>#include<set>#include<string>#include<map>#include<iostream>#include<queue......
  • Educational Codeforces Round 76 (Rated for Div. 2)
    EducationalCodeforcesRound76(RatedforDiv.2)A-TwoRivalStudents思路:最多可加x个距离,且最后的距离不能超过n-1#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong//#defineint__int128typedefpair<int,int>PII;typedefpair<string,......
  • Educational Codeforces Round 152 A~D
    A#include<bits/stdc++.h>#defineendl'\n'#defineiosios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)usingnamespacestd;typedefpair<int,int>PII;constintN=2e5+10;constintMOD=1e9+7;intT;vo......
  • Educational Codeforces Round 1
    EducationalCodeforcesRound1A.TrickySumintfac[N],p2[N];voidinit(){fac[0]=1;p2[0]=1;for(inti=1;i<=33;i++){fac[i]=fac[i-1]*2;p2[i]=p2[i-1]+fac[i];}}voidsolve(){intn=read();intsum=(1+n)*n/2;co......