
题意:
给你s,t串
你可以将s串中连续k个相同的字符翻转
问你能不能将s串变成t串
思路:
考虑对于连续k个相同的字符状态进行一个合并
我们看这个串哪些位置是可以随意改动的,把这些位置去掉之后两串再看一不一样即可
比如k=2的时候
00->11 11->00 1001->1111 0110->0000(注意状态合并还要关注左右)
这里可以利用栈来实现
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e6+10;
const int N=2e6+10;
const int seed=131;
const int mod=1e9+7;
typedef long long ll;
int st[N][2];
string change(const string& s,int k){//除去k个连续相同的字符之后剩下的字符的相对位置不会改变
int top=0;
for(auto c:s){
int x=c-'0';
if (top&&st[top][0]==x) {
st[top][1]++;
}else{
st[++top][0]=x;
st[top][1]=1;
}
if (st[top][1] == k)top--;
}
string res;
while (top&&st[top][1]){
res.push_back(st[top][0]+'0');
st[top][1]--;
if(!st[top][1])top--;
}
return res;
}
void solve(){
int n,k;
cin>>n>>k;
string s,t;
cin>>s>>t;
s= change(s,k);
t= change(t,k);
cout<<(s==t?"Yes":"No");
}
signed main()
{
ios::sync_with_stdio(false),cin.tie(0);
int t=1;
// cin>>t;
while (t--)solve();
return 0;
}