CodeForces 297A Parity Game (脑补题)
题意
一个01串,可以有两种操作:①在末尾添加parity(a);②删除开头的一个字符。其中parity(a),当串中1的个数为奇数时为1,偶数时为0。问某个01串是否可以通过若干操作变成另一个01串。
思路
简单分析一下可以先发现一个事情:当一个串的1的个数为奇数时,它最多可以再增加1个1;而当1的个数是偶数时,1的个数不可能再增加。这是一个决定性的性质。
再进一步发现,奇数个数1的01串可以任意减少1的个数,以及,任意一个串可以移位。以及,当1的个数为偶数个时,可以通过在末尾任意补0以及移位操作转换成长度一定、1个数一定的任意01串。而奇数个数1的01串可以通过先增加1个1,然后补0、移位,再减一个1也能转换成长度一定、1个数一定的任意01串。
所以我们只要统计起始串和目标串的长度,当起始串1个数为奇数时可以+1,然后如果起始串长度>=目标串,则一定可以通过减少1、补0、移位等操作转换成目标串。
代码
[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#define MID(x,y) ((x+y)/2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define REP(i, begin, end) for (int i = begin; i <= end; i ++)
using namespace std;
typedef long long LL;
typedef vector <int> VI;
typedef set <int> SETI;
typedef queue <int> QI;
typedef stack <int> SI;
int main(){
//freopen("test.in", "r", stdin);
//freopen("test.out", "w", stdout);
string s1, s2;
cin >> s1 >> s2;
int len1 = count(s1.begin(), s1.end(), '1'), len2 = count(s2.begin(), s2.end(), '1');
if (len1 & 1) len1 ++;
if (len1 >= len2){
puts("YES");
}
else{
puts("NO");
}
return 0;
}
[/cpp]
最新文章
- .net post的参数如果出现乱码如何解决!
- 文件上传小技巧/原生态【html篇】
- iOS 关于微信检测SDK应用的原理浅析
- C++ STL算法系列3---求和:accumulate
- discuz论坛X3升级时 文件下载出现问题,请查看您的服务器网络以及data目录是否有写权限
- 启动安卓模拟器报错 emulator: ERROR: x86_64 emulation currently requires hardware acceleration! CPU acceleration status:HAXM must be updated(version 1.1.1<;6.0.1) 解决办法
- 微软将Bing变开放平台 同谷歌争夺开发者
- C#学习日志 day 4 ------ 类相关---this指针以及相关关键字
- 关于__stdcall和__cdecl调用方式的理解
- Python编程中常用的12种基础知识总结
- Python系列 - 进程和线程
- 记录一次有意思的XSS过滤绕过2
- python第三方库的四种安装方法
- 【转】对cocos2d 之autorelease\ratain\release的理解
- H+ 后台主题UI框架
- 20155325 2016-2017-2 《Java程序设计》第8周学习总结
- idea 换主题
- Awk 从入门到放弃(2)– 分隔符 学习笔记
- hdu 1266 Reverse Number
- 开发中常遇到的linux系统配置操作整理