AT_agc049_b [AGC049B] Flip Digits 题解

· · 题解

在打模拟赛的时候碰到了这道题，现在来回忆一下自己与众不同的思路。

首先，考虑到要让两个长度相同的串变得相同，我们可以按长度逐位循环枚举，而枚举到每一位则会有两种情况：

注意：

  1. 不开 long long 见祖宗。

  2. 需要一个值来记录上一个 1 出现位置的下标，下一次枚举时只要从后一位开始就行了。

下面贴出代码：

#include<bits/stdc++.h>
using namespace std;
int n,s,ss;
long long ans;
char s1[500005],s2[500005];
signed main()
{
   cin>>n;
   cin>>s1>>s2;
   for(int i=0;i<n;i++)
   {
      if(s1[i]==s2[i]) continue;
      s=0;
      for(int j=max(i+1,ss);j<n;j++)//寻找
         if(s1[j]=='1')
         {
            s=j;
            break;
         }
      ss=s+1;
      if(s==0)
      {
         cout<<-1;
         return 0;
      }
      ans+=s-i;
      s1[s]='0';
      s1[i]=s2[i];//改变
   }
   cout<<ans;
   return 0;
}