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;
}