codeforces Parity Game

本文从WordPress迁移而来, 查看全部WordPress迁移文章

构造判断

题意：给出一个01串，允许两种操作；1.删除头元素;2.当前串中1的个数为奇数的时候，可以在尾部添加一个1，当前1的个数为偶数的时候，可以在尾部添加一个0。给出一个01的目标串，问原串能否通过2种操作得到目标串

本质是个构造，由原串构造得到目标串，但这题只是判断是否可行，而没有要输出构造的方法，实际上搞懂构造方法后，是可以输出的

  1. 当原串1的个数为偶数的时候，易知过程中1的个数只会保持不变或减少。当原串1的个数为奇数的时候，1的个数最多增1或保持不变或减少。所以当目标串1的个数比原串1的个数多出2或以上的时候，肯定构造失败。另外，如果原串1的个数为偶数，目标串个数又比原串多1，也是构造失败，因为原串1的个数无法增加
  2. 上面的情况排除后，只剩下以下的情况。
    1. 原串1的个数为奇数，目标串的个数比原串大1
    2. 原串1的个数为奇数，目标串1的个数小于等于原串
    3. 原串1的个数为偶数，目标串1的个数小于等于原串

构造的方法是，在尾部添加1个1（当原串1的个数为偶数的时候不用添加新的，而是直接利用最后那个1），和目标串的第1个1对应，然后从此开始，按照目标串的样子来构建，目标串如果后面是0，原串就添加和目标串一样个数的0；当目标串又出现了1，原串又添加1。原串当然不是想加0就加0，想加1就加1的，为了达到添加的目的，就要删除头元素，直到删掉1，改变了1的个数，才有可能改变添加的数字

可以知道，2里面的3种情况，目标串的1都只是比原串多1（奇数时），或者相等（偶数时），所以排除了哪些必定失败的情况后，剩下的都是必定成功的，就是这么神奇

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
#define N 10010
int n,_n,num,_num;

char s[N],_s[N];

int main(){
	while(scanf("%s%s",s,_s)!=EOF){
		n = strlen(s);
		_n = strlen(_s);
		num = _num = 0;
		for(int i = 0; i < n; i++)
			if(s[i] == '1')
				num++;
		for(int i = 0; i < _n; i++)
			if(_s[i] == '1')
				_num++;

		if(_num - num >= 2 || (!(num&1) && _num - num == 1)){
			puts("NO"); continue;
		}
		puts("YES");
	}
	return 0;
}