题解：AT_abc419_d [ABC419D] Substr Swap

题解：AT_abc419_d Substr Swap

阿巴太菜 C 没过，但过了 D。

思路

首先，我们看到这字符串翻来翻去的，就知道，一定会有重复翻的。那一个字符串翻来翻去，有可能会翻会来，那我们就建一个数组来存储每一位翻转的次数就行了。

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+1;
bitset<N>k;
string a,b;
int n,m;
signed main(){
	k.reset();
	cin>>n>>m;
	cin>>a>>b;
	while(m--){
		int l,r;
		cin>>l>>r;
		for(int i=l-1;i<r;i++){
			k[i]=k[i]^1;
		}
	}
	for(int i=0;i<n;i++){
		if(k[i]==1){
			swap(a[i],b[i]);
		}
	}
	cout<<a<<"\n";
    return 0;
}

结果丝毫不出意外，TLE 了……

我们要想办法把在 $l$ 到 $r$ 之间的赋值的时间复杂度降到 $O(1)$ 。

这个时候什么算法能胜任呢？很明显，答案是差分！

知道是差分，这题就好做了。

AC 代码

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=5e5+1;
int k2[N];
string a,b;
int n,m;
void f(int l,int r,int c){//差分
	k2[l-1]+=c;
	k2[r]-=c;
}
signed main(){
	cin>>n>>m;
	cin>>a>>b;
	while(m--){
		int l,r;
		cin>>l>>r;
		f(l,r,1);
	}
	for(int i=1;i<n;i++){
		k2[i]+=k2[i-1];
	}
	for(int i=0;i<n;i++){
		if(k2[i]%2==1){
			swap(a[i],b[i]);//如果翻转了奇数次，就交换
		}
	}
	cout<<a<<"\n";
    return 0;
}

题解：AT_abc419_d [ABC419D] Substr Swap

文章操作

题解：AT_abc419_d Substr Swap

思路

AC 代码

相关推荐

评论

题解：AT_abc419_d [ABC419D] Substr Swap