【USACO 3.2.2】二进制数01串
2024-10-11 16:45:23
【描述】
考虑排好序的N(N<=31)位二进制数。
你会发现,这很有趣。因为他们是排列好的,而且包含所有可能的长度为N且含有1的个数小于等于L(L<=N)的数。
你的任务是输出第I(1<=I<=长度为N的二进制数的个数)大的,长度为N,且含有1的个数小于等于L的那个二进制数。
注意:这里“长度为N”包括长度小于N的数(我们认为高位用0补齐)
【格式】
PROGRAM NAME: kimbits
INPUT FORMAT:(file kimbits.in)
共一行,用空格分开的三个整数N,L,I。
OUTPUT FORMAT:(file kimbits.out)
共一行,输出满足条件的第I大的二进制数。
【分析】
简单的组合数学的题目,用二分法,对每一位判断当改位是0的时候的有多少个符合条件的数就行了。
注意加个记忆化,注意开longlong
#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
const int maxn=+;
using namespace std;
long long c[maxn][maxn],n,o=;
long long C(long long a,long long b)
{
if (a==) return ;
if(c[a][b]!=-) return c[a][b];
return a==?b:c[a][b] = ((C(a-,b)*(b-a+)))/a;
}
long long total(long long num,long long len,long long Maxo);
int main()
{
long long l,i,len;//cnt是已有1的个数
//文件操作
freopen("kimbits.in","r",stdin);
freopen("kimbits.out","w",stdout);
char ans[maxn];
memset(c,-,sizeof(c));
memset(ans,,sizeof(ans));
scanf("%lld%lld%lld",&n,&l,&i);
for (len=;len<n;len++)//枚举长度
{
long long temp=total(,len,l); if (temp>=i) ans[len]=+'';
else {ans[len]=+'';i=i-temp;o++;}
}
printf("%s",ans);
return ;
}
//剩下len位
long long total(long long num,long long len,long long Maxo)
{
long long cnt=;
len=n-len-;
for (long long i=;(i+o)<=Maxo;i++)//剩余位中1的个数
cnt+=C(i,len);
return cnt;
}
最新文章
- Mac 操作技巧
- 兼容8事件绑定与解绑addEventListener、removeEventListener和ie的attachEvent、detachEvent
- **SQL某一表中重复某一字段重复记录查询与处理
- Android中AsyncTask使用
- sqlserver 锁与阻塞
- 前端资源构建-Grunt环境搭建
- iOS开发小技巧--图片的圆角处理
- 【转】Install MATLAB 2013a on CentOS 6.4 x64 with mode silent
- 2D丛林逃生
- linux基础(五)
- bootstrap表格固定表头,表格内容滚动条滚动显示
- 打开word时出现the setup controller has encountered a problem during install解决办法
- 快速EDAS字体嵌入问题
- vue+axios 前端实现的常用拦截
- C# for循环或者foreach往List中添加对象的时候前面的数据总被最后加入的覆盖
- ASP.NET Core Docker jexus nginx部署-CentOS实践版
- [No000012A]WPF(2/7):布局,容器和布局转换[译]
- A*算法 寻路
- TJU Problem 1644 Reverse Text
- 20172319 《Java程序设计教程》 第10周学习总结
热门文章
- POJ3087 Shuffle&#39;m Up(模拟)
- hiho #1079 : 离散化
- 数据结构(线段树):NOI 2016 区间
- HDOJ(HDU) 2503 a/b + c/d(最大公约数问题)
- freemarker使用map
- Cookie介绍及JavaScript操作Cookie方法详解
- 吉哥系列故事--完美队形 - HDU 4513 (Manacher)
- ARES
- Html中src、href的相对路径与绝对路径
- PHP学习之[第05讲]PHP5.4 循环结构、系统函数和自定义函数