传送门

DP预处理+贪心

首先设$f[i][j]$表示长度为$i$的01串中有不大于$j$个1,然后显然

$f[i][j]=\sum_{k=1} ^{j} C[i][k]$

$C[i][j]=C[i-1][j-1]+C[i-1][j]$

DP预处理结束。

通过DP预处理出的数不断把编号缩小。

显然存在的是,如果$f[i-1][L]<I$,那么第$i$位就是1,否则即为0。

 //OJ 1847
 //by Cydiater
 //2015.9.22
 #include <iostream>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <string>
 #include <algorithm>
 #include <queue>
 #include <map>
 #include <ctime>
 #include <cmath>
 #include <iomanip>
 using namespace std;
 #define ll long long
 #define up(i,j,n)        for(int i=j;i<=n;i++)
 #define down(i,j,n)        for(int i=j;i>=n;i--)
 ;
 const int oo=0x3f3f3f3f;
 inline ll read(){
     ,f=;
     ;ch=getchar();}
     +ch-';ch=getchar();}
     return x*f;
 }
 ll N,L,I,f[][];
 namespace solution{
     void init(){
         N=read();L=read();I=read();
         memset(f,,sizeof(f));
     }
     void slove(){
         up(i,,)f[i][]=;
         up(i,,N)up(j,,L)f[i][j]=f[i-][j-]+f[i-][j];
         up(i,,N)up(j,,L)f[i][j]+=f[i][j-];
         down(i,N,)
             ][L]<I&&I>){
                 printf(");
                 I-=f[i-][L];
                 L--;
                 //cout<<i<<' '<<L<<' '<<f[i-1][L]<<' '<<I<<endl;
             }");
     }
 }
 int main(){
     //freopen("input.in","r",stdin);
     using namespace solution;
     init();
     slove();
     ;
 }

需要注意的是,要把数据开到long long

最新文章

  1. 微信扫描打开APP下载链接提示代码优化
  2. 交换芯片收发包的 DMA 实现原理
  3. 【codevs 1565】【SDOI 2011】计算器 快速幂+拓展欧几里得+BSGS算法
  4. EntityFramework Core 学习笔记 —— 包含与排除类型
  5. abort终止正在进行中的的ajax请求
  6. [Unity2D]鼠标(或触摸)输入处理
  7. MatLab 组件大全
  8. Android sqlite3工具的使用
  9. C++primer 阅读点滴记录(三)
  10. DB2数据库之间联邦
  11. eclipse运行mapreduce报错Permission denied
  12. ios 解析json,xml
  13. 命令行创建AVD
  14. php-fpm 启动参数及重要配置详解&lt;转&gt;
  15. python heapq
  16. jbpmAPI-4
  17. 用Java 实现一个表中的数据复制到另一个表中
  18. Angular 学习笔记 ( PWA + App Shell )
  19. 教你如何用Meterpreter渗透Win系统
  20. Jquery,全选,反选,

热门文章

  1. Node基础:url查询参数解析之querystring
  2. UWP 快速的Master/Detail实现
  3. node简单操作mysql的类
  4. 实现解耦-Spring.Net
  5. windows注册表学习笔记
  6. 当在XP系统上无法安装Mysql ODBC时,怎么办?
  7. UEFI与MBR区别
  8. BOP 2016 复赛题目
  9. 【瞎想】TDD与汉字;FDD与英语字母
  10. 使用D3制作图表(1)--画布绘制