CF949A Zebras 题解

题目传送门

题意

给定一个仅包含 $0$ 和 $1$ 的字符串（$01$ 串），你需要将其拆成若干个 不一定连续 的子串，这些子串满足如下条件：

• 首末均为 $0$

• 中间 $01$ 交替

试输出其中任意一种拆分方案。

比如：

0 0 1 0 1 0 0
-------------
0   1 0        ---- 位置 1,3,4
  0     1 0    ---- 位置 2,5,6
            0  ---- 位置 7

思路

首先我们可以先观察所有符合

• 首末均为 $0$

• 中间 $01$ 交替

的子串：

0
010
01010
0101010
010101010
...

发现了什么？对于以上的每一个 $1$，它的左边和右边都有 $1$ 个 $0$ 包含它。

如果对应回原串，每一个 $1$ 的左边和右边都需要找到 $1$ 个 $0$。

那也就是说，我们可以对于每一个 $1$，记录一下它所找到的左边的 $0$ 和右边的 $0$，然后用一种类似链表的方法把他们串联起来，最后再进行遍历。

暴力做法核心代码

//这里给出的部分代码是1的左边找0
for(int i=1;i<=n;++i){//这里不能够从n到1，下面会讲到
	if(str[i]=='1'){//枚举1
		bool isfind=0;
		for(int j=1;j<i;++j){//找之前1的左边未使用过的0
			if(str[j]=='0'&&!used[j]){//如果找到
				used[j]=1;
				L[i]=j;//1的左边就是找到的0
				R[j]=i;//找到的0的右边就是1
				isfind=1;
				break;
			}
		}
		if(!isfind){//如果没找到，说明0不够用，输出-1
			printf("-1");
			return 0;
		}
	}
}

然后就会发现在第 8 个点 T 了

---

满分做法

由于原做法对于每一个 $1$ 都需要找一遍 $0$，所以我们可以对其优化。

如果当一个 $1$ 有多个 $0$ 可使用时，其实使用哪个都没所谓。

比如拿“1 的左边找 0”做示范：

0100010

我们可以发现，$i=6$ 位置上的 $1$ 可使用的 $0$ 的数量要大于 $i=2$ 位置上的 $1$ 可使用的 $0$ 的数量。

那么至少在当两个位置 $i < j$ 且 $a_i=a_j=1$ 时，$a_i$ 可使用的 $0$ 的数量 $\leq$ $a_j$ 可使用的 $0$ 的数量。

所以说在这里，当我们从左到右遍历的时候，其实前面 $i=2$ 的 $1$ 已经“吃饱喝足”了，剩下的 $0$ 就由 $i=6$ 的 $1$ 解决就可以了。

我们可以使用 STL，将之前的 $0$ 放进栈或队列里，使得寻找 $0$ 的复杂度为 $O(1)$，使用时只需要 pop 就可以了。

反过来，如果在“1 的左边找 0”里从右到左遍历，第一个 0 给了 $a_6$，这就导致 $a_2$ 没 0 用了，导致程序输出了错误的答案。

代码

if(str[i]=='0'){//如果遇到0
	sta.push(i);//将其ID放入“可使用0”里面，方便索引
}
else{
	if(sta.empty()){//如果已经没有可使用0了，输出-1
		printf("-1");
		return 0;
	}
	L[i]=sta.top();//1的左边就是找到的0
	R[sta.top()]=i;//找到的0的右边就是1
/*
	R[i]=sta.top();//1的右边就是找到的0
	L[sta.top()]=i;//找到的0的左边就是1
*/
	sta.pop();
}

提交记录