专栏文章
字典序第k小
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @min2jbml
- 此快照首次捕获于
- 2025/12/01 19:31 3 个月前
- 此快照最后确认于
- 2025/12/01 19:31 3 个月前
常见问题。
- 最优化问题
- 计数题
- 字典序最小(如构造)
字典序第 小。
例1
题意
输入 ,。
求 中所有整数中字典序排名第 名的。
题解
对于每一位分别找。
伪代码
CPPcin>>n>>k;
ll cur=1;
k--;
while(k){
ll steps=0, first=cur, last=cur;
while(first<=n){ //steps表示前缀为cur,有多少个数字<=n
steps+=min(last,n)-first+1;
first=first*10;
last=last*10+9;
}
if(steps<=k){
k-=steps;
cur++;
}else{
cur=cur*10;
k--;
}
}
cout<<cur;
LIS+字典序 题目
给出 和数组
求其所有上升子序列中字典序第 小的那个。
求其所有上升子序列中字典序第 小的那个。
但是字典序有两种可能。
A: 以取的编号进行比较。
B: 以取的数值进行字典序比较。
这类问题都稍后讨论。
A: 以取的编号进行比较。
B: 以取的数值进行字典序比较。
这类问题都稍后讨论。
LIS
数值分类,位置列表。
表示第 个的值
表示第 结尾最长上升子序列
表示第 个的值的最长上升子序列计数
表示第 结尾最长上升子序列
表示第 个的值的最长上升子序列计数
LIS里的问题有很多是关于偏序关系的。
我们将每个点按照 为平面点, 为高度,可以让你的思路清晰。
LIS 计数
可以考虑按照 分层次,每层仅仅依赖上层。
使用三游标(滑动窗口)可以解决!
写代码的细节:每个点一定有至少一个依赖!!!!!
使用三游标(滑动窗口)可以解决!
写代码的细节:每个点一定有至少一个依赖!!!!!
字典序第 小的LIS
在任意一个编号中,编号越大,数值越小。
此消彼长
先简化问题为
细节
字典序第 小有致命细节问题。
易错点:中途计数超过 要截断。
会爆!!!!!!
易错点:中途计数超过 要截断。
会爆!!!!!!
为什么
因为在计数问题中,题目会让你取模,这就是一种提示。
但是第 小问题中,我们一般需要用到计数,不会给这种提示。
但是第 小问题中,我们一般需要用到计数,不会给这种提示。
LIS 数值字典序第 大= LIS编号字典序第 小
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...