codeforces-#651-E

codeforces-#651-E

七月 11, 2020

E. Binary Subsequence Rotation

题意
给出两个等长度的01字符串s t
要求经过最少次操作使得s变为t
一次操作定义为
选出s中的一个子序列a
将子序列a中的元素顺时钟移动一位 再按原下标放回到s中 视为一次操作

比如
s=101001 选出子序列为{s1,s2,s4}={1,0,0} 顺时针转动后为 {0,1,0}放回s
则s变为 {011001}

首先排除掉s和t中0/1数量不同的
其他情况一定存在解
将 s中同一位置与 t
不同的字符拿出组成一个新字符串，
每次操作一定是取出 01010…或 10101…的子序列，

类似000111 -> 111000 可以拆成三对01子序列进行转换
所以找出原字符串中最长的未被1抵消的 0的长度 较短的 连续0则被包含在0101 中
和最长的不被0抵消的1的长度 ；有部分为1开头的子序列被包含在0101的子序列中被计入以0开头的子序列
未被包含的子序列独自组成1010子序列
的长度即可，因为这些都是不能一次连续取的

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
# include <bits/stdc++.h>

using namespace std;
typedef long long ll;

# define endl '\n'

# define Turnoff std::ios::sync_with_stdio(false)

const int Max=2e5+5;
const int Mod=998244353;
int data[Max],vis[Max];
int n;
int main() {
    Turnoff;
    cin>>n;
    string s,t;cin>>s>>t;
    int cnt=0;
    for(auto i:s)if(i=='1')cnt++;
    for(auto i:t)if(i=='1')cnt--;
    if(cnt)cout<<-1<<endl;
    else{
        int ans=0,maxn=0,minn=0;///注意初始值为0若0101串多于1010串那么minn值仍为0
        for(int i=0;i<n;i++){
            if(s[i]==t[i])continue;
            if(s[i]=='1')cnt++;
            else cnt--;
            maxn=max(maxn,cnt);
            minn=min(minn,cnt);
        }
        cout<<maxn-minn<<endl;
    }
}