Codeforces 1370 E

题意： 给定两个 01 01 01序列 S S S和 T T T，可以选择 S S S中的子序列 s s s进行一次顺时针操作，即：
t s [ 1 ] = s [ 0 ] , t s [ 2 ] = s [ 1 ] , . . . , t s [ s . s i z e ( ) − 1 ] = s [ s . s i z e ( ) − 2 ] , t s [ 0 ] = t s [ s . s i z e ( ) − 1 ] ts[1] = s[0], ts[2]=s[1],...,ts[s.size()-1]=s[s.size()-2], ts[0]=ts[s.size()-1] ts[1]=s[0],ts[2]=s[1],...,ts[s.size()−1]=s[s.size()−2],ts[0]=ts[s.size()−1]
然后 s = t s s=ts s=ts。问是否可以通过不断地操作使得 S = T S=T S=T，如果可以输出最小操作次数，否则输出 − 1 -1 −1。
题解： 无解的情况就是 S c n t [ 0 ] ≠ T c n t [ 0 ] Scnt[0] \neq Tcnt[0] Scnt[0]​=Tcnt[0]或者 S c n t [ 1 ] ≠ T c n t [ 1 ] Scnt[1] \neq Tcnt[1] Scnt[1]​=Tcnt[1]。
之后，对于 S [ i ] = T [ i ] S[i]=T[i] S[i]=T[i]自然无需调整，所以我们将 S [ i ] ≠ T [ i ] S[i]\neq T[i] S[i]​=T[i]的部分组成一个新的序列 s t r str str
对于 s t r str str存储的是 S [ i ] ≠ T [ i ] S[i]\neq T[i] S[i]​=T[i]的 S [ i ] S[i] S[i]。
需要了解的是：

1. 可以知道， s t r str str中 0 0 0和 1 1 1的数量一定一样多，如果不一样多则无法得到 T T T。设 s t r c n t 0 = x , s t r c n t 1 = y strcnt0=x,strcnt1=y strcnt0=x,strcnt1=y，那么在对应的T中 s t r T c n t 0 = y , s t r T c n t 1 = x strTcnt0=y,strTcnt1=x strTcnt0=y,strTcnt1=x，所以 x = y x=y x=y，即两者数量一定相等。

2. 可以知道，每次操作一定选择的是 010101...01 010101...01 010101...01或 101010...10 101010...10 101010...10
   因为 S S S中对应的 0 0 0对应 T T T中的1，所以我们每次需要把 s t r str str中的 0 0 0和 1 1 1调换位置，进行一次顺时针移动后就可以得到当前选择的序列中各个元素相较于移动前都发生了改变，即 0 → 1 , 1 → 0 0→1,1→0 0→1,1→0。
   如果选择的非此种序列，那么至少存在连续两个元素相同，那么顺时针移动一次必然不能使得移动前后所有元素都发生改变。如 1001 1001 1001移动后成 1100 1100 1100，第三个元素未变。选择成为 010101...01 010101...01 010101...01或 101010...10 101010...10 101010...10就一定能保证只需移动一次就可以翻转所有元素。而其他情况移动成功情况至少要移动次数为max(max(连续的1个数)，max(连续的0个数))。

3. 开始选取元素：我们尽可能保证当前待选的元素放到序列后成为使得序列成为 0101...01 0101...01 0101...01或者 1010...10 1010...10 1010...10这两种，如果这两种不行，则就会出现某一个序列被加上当前待选元素后成为 0101...0 0101...0 0101...0或者 1010...1 1010...1 1010...1。由于尽可能少操作，即序列尽可能少，假设当前待选元素为 0 0 0，那么优先考虑加到 1010...1 1010...1 1010...1这种序列后面，如果这种序列不存在，那么考虑加到 0101...01 0101...01 0101...01这种序列后面，如果这种序列也不存在，那么考虑自己开辟一个新的序列，以 0 0 0开头，此时操作数加 1 1 1。待选元素为 1 1 1同理。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N = 1000010;
char s[N];
char t[N];
int str[N];
int g;
int n;

int main()
{
	scanf("%d", &n);
	scanf("%s", s + 1);
	scanf("%s", t + 1);
	
	int cnts[2] = {0}, cntt[2] = {0};
	for(int i = 1; i <= n; i++) {
		cnts[s[i] - '0']++;
		cntt[t[i] - '0']++;;
		if(s[i] == t[i]) continue;
		str[++g] = i;
	} 
	
	
	if(cnts[0] != cntt[0] || cnts[1] != cntt[1]) puts("-1");
	else {
		//cnt[i][j]表示第一个是i的当前为j的 
		int cnt[2][2] = {0, 0, 0, 0}, res = 0;
		for(int i = 1; i <= g; i++) {
			if(s[str[i]] == '0') {
				if(cnt[1][1]) cnt[1][1]--, cnt[1][0]++;
				else if(cnt[0][1]) cnt[0][1]--, cnt[0][0]++;
				else cnt[0][0]++, res++;
			} 
			else {
				if(cnt[0][0]) cnt[0][0]--, cnt[0][1]++;
				else if(cnt[1][0]) cnt[1][0]--, cnt[1][1]++;
				else cnt[1][1]++, res++;
			}
		}	
		printf("%d\n", res);
	}
	return 0;
}