Codeforces 1492D、Genius's Gambit
2024-10-21 11:44:11
原题网址
https://codeforces.com/contest/1492/problem/D
题目大意
给定a,b,k,求x,y使得x和y的二进制表示都恰有a个0和b个1,且不能使用开头的0。另外,还要求x-y的二进制表示恰有k个1。如果不存在x,y输出No,否则输出x和y的二进制表示。
解题思路
此题为构造性问题。
注意到10000-00001=01111(1个1和p个0生成p个1),11110-01111=01111(1个0和p个1生成p个1),我们可以解决该题。
首先若k=0,肯定有解,只要x和y相等即可。
k>0时,若没有0或只有1个及以下的1,肯定无解。因为x和y开头必须是1,剩下的里面必须0和1都有才可能有解。
k>0,有1个以上1且有0时,考虑x=11110000和y=11100010。首先,x把1都放前面,0都放后面;y在x基础上把最右侧1往右移动位置。这样每移动一位,x-y就会多出一个1。最多得到a个1。即k<=a时有解。
若k>a,则最后一个1已经无处可移动了,得到x=11110000和y=11100001。我们还能把最左侧0往左移动位置。这样每移动一位,x-y还会再多出一个1。因为最高位的1不能越过,还有一个1已经在最低位了,这样最多移动b-2次。所以k<=a+b-2时有解。
其他情况无解。
一般情况下想到的都是多少个1后面放多少个0这种直接构造解的方法。但是这题用先构造一个特殊解,然后交换适当位置得到新解的方法更方便。
我的代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, k;
string x, y;
ios::sync_with_stdio(false);
cin >> a >> b >> k;
if (k > 0 && (a == 0 || b == 1)) {
cout << "No\n";
return 0;
}
for (int i = 0; i < b; ++i) {
x.push_back('1');
y.push_back('1');
}
for (int i = 0; i < a; ++i) {
x.push_back('0');
y.push_back('0');
}
if (k <= a) {
swap(y[b - 1], y[k + b - 1]);
cout << "Yes\n" << x << endl << y;
return 0;
}
if (k <= a + b - 2) {
swap(y[b - 1], y[a + b - 1]);
swap(y[b - 1], y[b - 1 - (k - a)]);
cout << "Yes\n" << x << endl << y;
return 0;
}
cout << "No\n";
return 0;
}
最新文章
- Oracle 12c 使用scott等普通用户的方法
- 【C语言】C语言局部变量和全局变量
- js获取上一个月、下一个月格式为yyyy-mm-dd的日期
- HDU 3791 二叉搜索树
- 【转载】取消Debian系统自动锁屏
- css3画图之大白(●—●)
- COM学习笔记
- [iOS微博项目 - 1.7] - 版本新特性
- vmware workstation下的虚拟Linux通过NAT模式共享上网
- Wireless Password - HDU 2825(ac自动机+状态压缩)
- ubuntu 14.0 下github 配置
- C++中的int和short int
- JS中处理单个反斜杠(即转义字符的处理)
- JavaScript 语言精粹读书笔记
- hihoCoder 1039:字符消除(字符串处理)
- bzoj 4945: [Noi2017]游戏
- Tutorial 01_熟悉常用的Linux操作和Hadoop操作
- 解决Fiddler查看Post参数中文乱码的问题
- Verilog HDL语言实现的单周期CPU设计(全部代码及其注释)
- Ubuntu 18.04 安装和常用软件安装
热门文章
- Pytorch基础-张量基本操作
- python进阶之路12之有参装饰器、多层语法糖、递归函数简介
- MySQL 字符串长度 char_length、length
- OpenMP Parallel Construct 实现原理与源码分析
- windows系统批量转换CRLF和LF格式代码,解决eslint报错Delete `␍`解决&#39;unix2dos&#39; is not recognized as an internal or external command
- 详解 Gulp4 和 Gulp3 的区别
- ORM哪家强?java,c#,php,python,go 逐一对比, 网友直呼:全面客观
- Python内置对象(一)
- 艰难的 debug 经历,vscode 无法获取远程环境 ssh 报错,windows 11 ssh
- SpringBoot Test Junit 联用