洛谷 题解 P2727 【01串 Stringsobits】
2024-08-27 18:09:01
本蒟蒻又双叒叕被爆踩辣!
其实只要理解了就会觉得这是个傻逼题!
这题给的标签是 dp,搜索,数论
但是可以用二分的思路做!
Solution:
从最高位开始枚举,
我们考虑每一位,是不是只可以取0/1
那么我们就先求出当此位置为0时,它可以做到的方案数(等会再告诉你们为什么要求
我们想一想,什么时候此位该为0,什么时候此位该为1???
我们求出它的方案数,那这个方案数是不是就是但此位为0时可以达到的最大值;
如果i比这个最大值还要大的话,此位为0是不是就做不到了。
result:
所以,如果这个方案数比i大,说明排名为i的数一定属于最高位是0的数,否则就属于最高位为1的数。
你就逐位考虑下来就可以了!
这就是运用了二分的思路,对其进行求解。
至于方案数的话,在最开始跑一遍dp就行了,
g[i][j] = g[i - 1][j - 1] + g[i - 1][j];
就是它为0/1前一位的值相加即可。
code:
#include<bits/stdc++.h>//万能头
using namespace std;
#define maxn 60//可以稍微大一点
#define int long long//这是个坑
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
int n, l, k, g[maxn][maxn], sum[maxn][maxn], a[maxn];
//g[k][i]是来表示在前k位中,恰有i个1的二进制数的数量
//sum[k][i]是来表示在前k位中,最多有i个1的二进制数的数量
//a[i]是当前这一位是0/1,输出是用。
void dfs(int x, int l, int k){
if(x == 0){//跑到了最后一位了
Dep(i, n, 1){//输出路径
printf("%d", a[i]);
}
exit(0);//不可以用return,return只结束当前这一轮函数,exit(0)就可以直接结束程序。
}
if(k <= sum[x - 1][l]){//如果它小于或等于此位取0时的最大值
a[x] = 0;//当前这位就取0;
dfs(x - 1, l, k);//并且直接跑到下一位
}
else{//如果它大于的话
a[x] = 1;//当前就取1;
dfs(x - 1, l - 1, k - sum[x - 1][l]);//并且跑下一位的时候要把还可以取的‘1’的数量-1,然后要跑的数位也会减去这位取了‘1’以后减下的值。
}
}
signed main(){
scanf("%d%d%d", &n, &l, &k);//RT
g[0][0] = 1;//初始化,一定要记得
Rep(i, 1, n){
g[i][0] = 1;//如果只要0个‘1’,肯定只有1种方法。
Rep(j, 1, n){
g[i][j] = g[i - 1][j - 1] + g[i - 1][j];//递归求恰有i个1的二进制数的数量
}
}
Rep(i, 0, n){
Rep(j, 0, n){
Rep(k, 0, j){
sum[i][j] += g[i][k];//跑一下求最多有i个1的二进制数的数量
}
}
}
dfs(n, l, k);//搜索一下就可以了
return 0;
}
在这里还说一下我前两次Wa在那
First:
我求sum[ ][ ]的时候,不是从第0位开始跑的。。。
Second:
没开long longQAQ
Ps:请看懂再抄
最新文章
- TDDL分库分表规则
- VS2010中汉字拷贝到Word出现乱码问题解决
- [ZigBee] 4、ZigBee基础实验——中断
- Quartz Spring与Spring Task总结
- iOS 上拉刷新和下拉加在更多(第三方框架EGOTableViewPullRefresh)
- updatePanel导致JS失效的解决办法(转)
- Jquery 操作Html 控件 CheckBox、Radio、Select 控件 【转】http://www.cnblogs.com/lxblog/archive/2013/01/09/2853056.html
- php 连接测试sphinx
- webqq 获得好友列表hash算法 获得最新hash的方法
- shuffle过程中的信息传递
- 135. Candy
- c++ 命名空间 以及 作用域 函数参数 面向对象实验报告
- PHP文件基本操作及文件的上传和下载
- day07 Python文件操作
- 采用xtrabackup部署主从同步
- Java12配置
- Selenium基础知识(二)鼠标操作
- LeetCode 4Sum (Two pointers)
- idea配置(卡顿、开发环境等配置),code style template
- LEETCODE —— Unique Paths II [Dynamic Programming]