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