Electric Board（思维，抽象操作过程）

题目链接：http://icpc.upc.edu.cn/problem.php?cid=2877&pid=6

---

题目描述
An electric bulletin board is showing a string S S S of length N N N consisting of 0 0 0 and 1 1 1.

You can do the following operation any number of times, where Si denotes the i-th character ( 1 ≤ i ≤ N 1≤i≤N 1≤i≤N) of the string shown in the board.

Operation: choose a pair of integers ( l , r ) (l,r) (l,r) ( 1 ≤ l < r ≤ N 1≤l<r≤N 1≤l<r≤N)satisfying one of the conditions below, and swap S l S_l Sl​ and S r S_r Sr​.

S l S_l Sl​= 0 and S l S_l Sl​+1=…= S r S_r Sr​= 1.
S l S_l Sl​=⋯= S r S_r Sr​−1= 1 and S r S_r Sr​= 0.
Determine whether it is possible to make the string shown in the board match T T T, and find the minimum number of operations needed if it is possible.

Constraints
2 ≤ N ≤ 500000 2≤N≤500000 2≤N≤500000
S S S is a string of length N N N consisting of 0 and 1.
T T T is a string of length N N N consisting of 0 and 1.
输入
Input is given from Standard Input in the following format:
N N N
S S S
T T T
输出
If it is impossible to make the board show the string T T T, print -1.
If it is possible, find the minimum number of operations needed.

样例输入
【样例1】
7
1110110
1010111
【样例2】
20
11111000000000011111
11111000000000011111
【样例3】
6
111100
111000
【样例4】
119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

样例输出
【样例1】
2
【样例2】
0
【样例3】
-1
【样例4】
22

---

大意：

给出01序列 A , B A,B A,B，问至少多少次下面的操作，能将序列 A A A变为序列 B B B？
S l = 0 ， S l + 1... S r = 1 S_l=0，S_l+1...S_r=1 Sl​=0，Sl​+1...Sr​=1 或 S l . . . S r − 1 = 1 ， S r = 0 S_l...S_r-1=1，S_r=0 Sl​...Sr​−1=1，Sr​=0时，交换 S l S_l Sl​, S r S_r Sr​。

思考：

观察几组样例发现，其实就是0的移动！并且移动时不能跨越其他的0。

因为不能跨越，所以有冲突时，比如当前0要移动要最后，但是中间有0相隔，就要等到后面的0移动过才能移动。

这样，上面序列中0会和下面序列0的位置顺序一一对应。
（ A A A中第一个0要移动到 B B B中第一个0的位置，第二个0移动到第二个0的位置…）

如果正好对应，那不用动，否则就要操作一次。

实现：

将 A A A中0的位置按顺序存下， B B B中位置按顺序存下，循环判断对应是否相等。若不相等，操作次数 + + ++ ++。

Code：

#include<iostream>
using namespace std;

const int N=500010;
int n,m;
int a[N],b[N];

int main(){
	cin>>n;
	
	int sum1=0,sum2=0;
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='0') a[++sum1]=i;
	}
	
	for(int i=1;i<=n;i++){
		char c;cin>>c;
		if(c=='0') b[++sum2]=i;
	}
	
	if(sum1!=sum2){
		cout<<-1;return 0;
	}
	
	int ans=0;
	for(int i=1;i<=sum1;i++)
	{
		if(a[i]!=b[i]) ans++;
	}
	cout<<ans;
	
	return 0;
}

---

关键是题意的理解与转化。要简化模型。

当时比赛时觉得这个操作特麻烦，没能抽象操作过程。

还是做的题少。。