Binary Subsequence Rotation（Codeforces Round #651）

Link

题意

给出两个 $01$字符串 $s,t$。定义一次操作为选出字符串的一个子序列，循环位移一个。
问经过多少次操作能够让 $s == t$。

思路

观察发现只有形如 $010101$或 $101010$之类的操作才有意义，对于连续的 $1$，选了之后后面的几个 $1$并不会改变，例如 $100111$变成 $110011$,第 $1,5,6$位上的 $1$还是 $1$,因此选连续的 $0或1$是没有意义的。
我们可以类比括号匹配类的问题，遇到 $0就+1$， $1就-1$，求出他的最大值和最小值就是我们需要进行的操作的个数。

代码

#include<bits/stdc++.h>
#define ll long long
#define N 1000015
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n;i>=a;i--)
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define lowbit(i) ((i)&(-i))
#define VI vector<int>
using namespace std;
int n,cur,Max,Min;
char s[N],t[N]; 
int main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);scanf("%d",&n);scanf("%s%s",s+1,t+1);rep(i,1,n){if(s[i]==t[i]) continue;if(t[i]=='0') cur--;else cur++;Max = max(Max,cur);Min = min(Min,cur);}if(cur!=0) printf("-1");else printf("%d",Max-Min); return 0;
}