2018-2019 ACM-ICPC, Asia Nanjing Regional Contest E Eva and Euro coins

题目描述

https://codeforces.com/gym/101981

Solution

我们考虑找到一个中间状态，然后判断两个状态是否都能到达中间状态即可

观察可得，对于连续 $k$ 个相同数字，我们都可以将其移动到序列的末尾

所以我们就将其移动到序列末尾，并将其都变成 $0$

然后判断两个状态是否相同即可

#include <iostream>
#define maxn 1000010
using namespace std;

int n, k;

char s[maxn], t[maxn]; 

int st[maxn], cnt[maxn], top; 
void solve(char *s) {
    st[top = 0] = -1;
    for (int i = 1; i <= n; ++i) {
        st[++top] = s[i] - '0';
        cnt[top] = st[top] == st[top - 1] ? cnt[top - 1] + 1 : 1;
        if (cnt[top] >= k) top -= k; 
    }
    for (int i = 1; i <= n; ++i) s[i] = i <= top ? st[i] + '0' : '0';
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> k >> s + 1 >> t + 1;
    solve(s); solve(t);
    for (int i = 1; i <= n; ++i)
        if (s[i] != t[i])
            return cout << "No\n", 0;
    cout << "Yes\n"; 
    return 0;
    
}