Gym - 101981E 思维

Gym - 101981EEva and Euro coins

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

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

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

 #include<cstdio>

 #include<iostream>

 #include<stack>

 using namespace std;

 const int N=1e6+;

 struct Node{

     int op,num;

     Node(){}

     Node(int op,int num):op(op),num(num){}

     bool operator!=(const Node& n1)const{

         return op!=n1.op||num!=n1.num;

     }

 };

 int n,k;

 char a[N],b[N];

 stack<Node> ss,tt;

 void solve(char* s,stack<Node>& sta){

     while(!sta.empty()) sta.pop();

     for(int i=;i<n;i++){

         if(sta.empty()||sta.top().op!=s[i]-'')

             sta.push(Node(s[i]-'',));

         else sta.top().num++;

         if(sta.top().num==k) sta.pop();

     }

 }

 int main(){

     while(~scanf("%d%d",&n,&k)){

         scanf("%s%s",a,b);

         solve(a,ss);

         solve(b,tt);

         bool flag=true;

         if(ss.size()!=tt.size()) flag=false;

         while(flag&&!ss.empty()&&!tt.empty()){

             if(ss.top()!=tt.top()) flag=false;

             ss.pop();

             tt.pop();

         }

         if(flag) printf("Yes\n");

         else printf("No\n");

     }

     return ;

 }

tcl