Gym

Gym - 101981E Eva and Euro coins

题意：给你两个长度皆为n的01串s和t,能做的操作是把连续k个相同的字符反转过来，问s串能不能变成t串。

一开始把相同的漏看了，便以为是个差分模拟，然后懂了题意后一时也没想到，看了题解瞬间明了（题解做题法）。

相同连续k个1可以变成0，而相同连续k个0可以变成1,然后调整1的位置，所以其实便是看把连续k个相同字符删去后，两个字符串还相不相同，直接栈模拟。

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<stack>
 4 using namespace std;
 5 const int N=1e6+11; 
 6 struct Node{
 7     int op,num;
 8     Node(){}
 9     Node(int op,int num):op(op),num(num){}
10     bool operator!=(const Node& n1)const{
11         return op!=n1.op||num!=n1.num;
12     }
13 };
14 int n,k;
15 char a[N],b[N];
16 stack<Node> ss,tt;
17 void solve(char* s,stack<Node>& sta){
18     while(!sta.empty()) sta.pop();
19     for(int i=0;i<n;i++){
20         if(sta.empty()||sta.top().op!=s[i]-'0')
21             sta.push(Node(s[i]-'0',1));
22         else sta.top().num++;
23         if(sta.top().num==k) sta.pop();
24     }
25 }
26 int main(){
27     while(~scanf("%d%d",&n,&k)){
28         scanf("%s%s",a,b);
29         solve(a,ss);
30         solve(b,tt);
31         bool flag=true;
32         if(ss.size()!=tt.size()) flag=false;
33         while(flag&&!ss.empty()&&!tt.empty()){
34             if(ss.top()!=tt.top()) flag=false;
35             ss.pop();
36             tt.pop();
37         }
38         if(flag) printf("Yes
");
39         else printf("No
");
40     }
41     return 0;
42 }

tcl