链接：https://codeforces.com/gym/101981/attachments
思路：容易观察得知，如果有k个连续相同我们可以删除它(换句话说他后面的可以任意前后移动)，所以这个题就变成了一个类似消消乐的题目，只要存在k个一样的就可以消，比较两个序列消完的最终态是否相同即可，如果不相同可以证明一定不能变成相同的。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
using namespace std;
string s1, s2;
const int maxn = 1e6 + 100;
int n, k;
int cnt[maxn], st[maxn];
string (string s){
if(k == 1)return "";
int top = 0;
for(int i = 0; i < n; i++){
if(top && st[top] == s[i] - '0'){
cnt[top]++;
if(cnt[top] == k)top--;
}
else{
top++;
st[top] = s[i] - '0';
cnt[top] = 1;
}
}
s = "";
for(int i = 1; i <= top; i++){
while(cnt[i]){
s += st[i];
cnt[i]--;
}
}
return s;
}
int main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
cin >> s1 >> s2;
if(solve(s1) == solve(s2))
cout << "Yes" << endl;
else cout << "No" << endl;
return 0;
}
|
近期评论