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;
}