本文从WordPress迁移而来, 查看全部WordPress迁移文章
构造判断
题意:给出一个01串,允许两种操作;1.删除头元素;2.当前串中1的个数为奇数的时候,可以在尾部添加一个1,当前1的个数为偶数的时候,可以在尾部添加一个0。给出一个01的目标串,问原串能否通过2种操作得到目标串
本质是个构造,由原串构造得到目标串,但这题只是判断是否可行,而没有要输出构造的方法,实际上搞懂构造方法后,是可以输出的
- 当原串1的个数为偶数的时候,易知过程中1的个数只会保持不变或减少。当原串1的个数为奇数的时候,1的个数最多增1或保持不变或减少。所以当目标串1的个数比原串1的个数多出2或以上的时候,肯定构造失败。另外,如果原串1的个数为偶数,目标串个数又比原串多1,也是构造失败,因为原串1的个数无法增加
- 上面的情况排除后,只剩下以下的情况。
- 原串1的个数为奇数,目标串的个数比原串大1
- 原串1的个数为奇数,目标串1的个数小于等于原串
- 原串1的个数为偶数,目标串1的个数小于等于原串
构造的方法是,在尾部添加1个1(当原串1的个数为偶数的时候不用添加新的,而是直接利用最后那个1),和目标串的第1个1对应,然后从此开始,按照目标串的样子来构建,目标串如果后面是0,原串就添加和目标串一样个数的0;当目标串又出现了1,原串又添加1。原串当然不是想加0就加0,想加1就加1的,为了达到添加的目的,就要删除头元素,直到删掉1,改变了1的个数,才有可能改变添加的数字
可以知道,2里面的3种情况,目标串的1都只是比原串多1(奇数时),或者相等(偶数时),所以排除了哪些必定失败的情况后,剩下的都是必定成功的,就是这么神奇
1 |
|