专栏文章

字典序第k小

个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2jbml
此快照首次捕获于
2025/12/01 19:31
3 个月前
此快照最后确认于
2025/12/01 19:31
3 个月前
查看原文
常见问题。
  1. 最优化问题
  2. 计数题
  3. 字典序最小(如构造)
字典序第 kk 小。

例1

题意

输入 nnkk
1kn1091\leq k \leq n\leq10^9
[1,n][1,n] 中所有整数中字典序排名第 kk 名的。
题解
对于每一位分别找。
伪代码CPP
cin>>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+字典序 题目

给出 n,kn,k 和数组 a[1],a[2],,a[n]a[1],a[2],\cdots,a[n]
求其所有上升子序列中字典序第 kk 小的那个。
但是字典序有两种可能。
A: 以取的编号进行比较。
B: 以取的数值进行字典序比较。
这类问题都稍后讨论。

LIS

数值分类,位置列表。
x[i]x[i] 表示第 ii 个的值
f[i]f[i] 表示第 ii 结尾最长上升子序列
c[i]c[i] 表示第 ii 个的值的最长上升子序列计数
LIS里的问题有很多是关于偏序关系的。
我们将每个点按照 (i,a[i])(i,a[i]) 为平面点,f[i]f[i] 为高度,可以让你的思路清晰。

LIS 计数

可以考虑按照 f[i]f[i] 分层次,每层仅仅依赖上层。
使用三游标(滑动窗口)可以解决!
写代码的细节:每个点一定有至少一个依赖!!!!!

字典序第 kk 小的LIS

在任意一个编号中,编号越大,数值越小
此消彼长
先简化问题为 k=1k=1
细节
字典序第 kk 小有致命细节问题。
易错点:中途计数超过 kk 要截断。
c[i]c[i] 会爆!!!!!!
为什么
因为在计数问题中,题目会让你取模,这就是一种提示。
但是第 kk 小问题中,我们一般需要用到计数,不会给这种提示。
LIS 数值字典序第 kk 大= LIS编号字典序第 kk

评论

0 条评论,欢迎与作者交流。

正在加载评论...