COGS 862. 二进制数01串【dp+经典二分+字符串】

862. 二进制数01串

★   输入文件:kimbits.in   输出文件:kimbits.out 简单对比 时间限制:1 s   内存限制:128 MB

USACO/kimbits(译 by !Starliu )

描述

考虑排好序的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大的二进制数。

SAMPLE INPUT

(file kimbits.in)

5 3 19

SAMPLE OUTPUT

(file kimbits.out)

10011

题目链接:http://cogs.cf/cogs/problem/problem.php?pid=862

分析:这道题很难,构思巧妙,先用dp求出所要求dp[i,j]前i位1的个数不大于j的方案数,然后便是printf了。

先讲一下如何计算dp[i,j]。

dp[i,j]表示前i位,1的个数不大于j的方案数。

显然:dp[i,j]=dp[i-1,j]+dp[i-1,j-1];

dp[i-1,j]表示当前第i位以0开头所得到的方案数,dp[i-1,j-1]表示当前第i位以1开头得到的方案数。

如何根据得到的dp[i,j]来printf呢?如果当前我要确定第i位,那么肯定要看dp[i-1]集合中的值判断,例如我当前确定第5位,前4位不超过3个1的方案数为15,而我现在要求第19位,则第5为1,因为19>15,为什么呢?因为第5位可能为0,1,而为0的占了15个,为1的开头也是占15个,显然19属于为1开头的数,所以输出1,输出1的同时还要更新数据即可。输出0就什么也不用更新。

更新数据是指:当前第19位要减去15,3个1要变为2个1,以更新完的数据去得到第i+1个数才能是正确的。二分对每一位判断当改位是0的时候的有多少个符合条件的数就行了

貌似代码跑的飞起来,COGS上第一道排名NO.1的题,纪念一下!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=32+5;
 4 typedef long long ll;
 5 ll dp[maxn][maxn],n,o=0;
 6 ll C(ll a,ll b)
 7 {
 8     if(a==0)
 9         return 1;
10     if(dp[a][b]!=-1)
11         return dp[a][b];
12     return a==1?b:dp[a][b]=(C(a-1,b)*(b-a+1))/a;
13 }
14 ll total(ll num,ll len,ll maxo)
15 {
16     ll cnt=0;
17     len=n-len-1;
18     for(ll i=0;(i+o)<=maxo;i++)
19     {
20         cnt+=C(i,len);
21     }
22     return cnt;
23 }
24 int main()
25 {
26     ll l,i,len;
27     char ans[maxn];
28     memset(dp,-1,sizeof(dp));
29     memset(ans,0,sizeof(ans));
30     freopen("kimbits.in","r",stdin);
31     freopen("kimbits.out","w",stdout);
32     cin>>n>>l>>i;
33     for(len=0;len<n;len++)
34     {
35         ll temp=total(0,len,l);
36         if(temp>=i)
37             ans[len]=0+'0';
38         else
39         {
40             ans[len]=1+'0';
41             i=i-temp;
42             o++;
43         }
44     }
45     cout<<ans<<endl;
46     return 0;
47 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏IMWeb前端团队

js依赖注入初探

本文作者:IMWeb coolriver 原文出处:IMWeb社区 未经同意,禁止转载 前言:一个题目 之前在codewars上做在线题目时遇到这样一...

3569
来自专栏编程微刊

写给自己的TypeScript 入门小纲

1795
来自专栏九彩拼盘的叨叨叨

EditorConfig 介绍

当多人共同开发一个项目的时候,往往会出现大家用不同编辑器的情况。就前端开发者来说,有人喜欢 Sublime,有人喜欢 Webstorm , 也有人喜欢 Atom...

921
来自专栏LEo的网络日志

python技巧分享(九)

3546
来自专栏用户2442861的专栏

网易面试杂谈

http://blog.csdn.net/silangquan/article/details/18013967

842
来自专栏决胜机器学习

设计模式专题(二十四) ——访问者模式

设计模式专题(二十四)——访问者模式 (原创内容,转载请注明来源,谢谢) 一、概述 访问者模式(visitor)表示一个作用于某对象结构中的各元素的操作,它使...

35512
来自专栏性能与架构

mysql B+树索引

上图就是一棵B+树,每个部分有3个主要概念:物理磁盘块、数据项(蓝色)、指针(红色) 如磁盘块1,包含数据项 17、35,包含指针 P1、P2、P3,P1指向...

3467
来自专栏精讲JAVA

Java 虚拟机 2 : Java 内存区域及对象

为以后写文章考虑,也为巩固自己的知识和一些基本概念,这里要理清楚几个计算机中的概念。

1232
来自专栏Linyb极客之路

Java虚拟机:Java内存区域及对象

为以后写文章考虑,也为巩固自己的知识和一些基本概念,这里要理清楚几个计算机中的概念。

1292
来自专栏xingoo, 一个梦想做发明家的程序员

【java开发系列】—— spring简单入门示例

回顾   1 JDK安装   2 Struts2简单入门示例 前言   作为入门级的记录帖,没有过多的技术含量,简单的搭建配置框架而已。这次讲到spring...

21610

扫码关注云+社区

领取腾讯云代金券