2018-2019ICPC南京E.Eva and Euro coins
流锡_liuxi7086
2022年12月01日 21:56
收录于文集
共3篇

题意:

给你s,t串

你可以将s串中连续k个相同的字符翻转

问你能不能将s串变成t串

思路:

考虑对于连续k个相同的字符状态进行一个合并

我们看这个串哪些位置是可以随意改动的,把这些位置去掉之后两串再看一不一样即可

比如k=2的时候

00->11 11->00 1001->1111 0110->0000(注意状态合并还要关注左右)

这里可以利用栈来实现

代码块
C++
自动换行
复制代码
#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;
}
复制成功