id: 1503,1504.

A

考场做法是依次枚举每一位。判断 a[n-i+1]==a。

题解说只需判断 a 放在第一位或最后一位即可，因为左边连续的 a 数量大于右边连续的 a 的数量的时候放左边，以此类推。

B

翻译一下，就是每次可以选择一段 0 和 1 相等的前缀，然后将其翻转。要从初始串 A 搞到目标串 B。

弄前缀和。

原文：
A:  0111010000
B:  0100101100
前缀和：
A0: 1111223456
A1: 0123344444
---
B0: 1123344456
B1: 0111223444

发现对于每一位，不然是 A0==B0,A1==B1，不然是 A0==B1,A1==B0。我们假设前一种就是保持原型，后一种就是反转。

如果不是，则NO，否则继续判断：

前缀和：
A0: 1111223456
A1: 0123344444
     !     !

只有打感叹号的那些点（即 A0==A1 的点）可以将 \(1\sim i\) 变换。这就相当于，设 0 点上也有感叹号，我们可以把任意两个感叹号之间的 01 反转。

即，如果两个感叹号之间既有需要反转，又有需要保持原型的，那么就NO。最后一个感叹号以后如果有反转，那么也NO。

C

括号串就是函数的图像。

你想象有两个折线，1就是同时上升或下降，0就是一个上升一个下降。你需要保证任一时刻折线都不在第四象限，而且最后要到x轴。

于是你可以前一半的1上升，后一半的1下降。0，则交替着进行上升下降（就是第一个0让A折线上升，B折线下降，第二个0让A下降，B上升，第三个A上升，B下降……）这样显然是最优的。

D

神奇。就是黑白染色。黑格子一律填1，白格子一律填2。

但是比如现在ban的是2，但是黑格子已经填完了怎么办？那就填3，因为黑格子已经填完了，所以怎么放3都不会相交了。白格子填完同理。