专栏文章

[中文翻译] 到底什么是排序?

AT_agc055_f题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqq44w7
此快照首次捕获于
2025/12/04 08:54
3 个月前
此快照最后确认于
2025/12/04 08:54
3 个月前
查看原文
这个的好处就在于,如果 bib_i 的取值为 [1,K][1,K],那么甚至不需要排序。唯一需要排序的一次是在 pos 的时候,因为要保证 cbpos<Nc'_{b_{pos}} < N
实际上贪心算法对于每个 ii 发生的过程是:
  • cbicbi+1c'_{b_i} \gets c'_{b_i}+1
  • cc 从小到大排序。
由于 bi[1,K]b_i \in [1,K],所以实际上是任选一个 cx,x[1,K]c'_{x}, x \in [1,K]11,都能对应一个 bib_i。此时应将 cxc'_x 设为互相区分的,因为对应的 bib_i 不同。此时,排序相当于一个映射,将当前的标号 bib_i 双射到原始互不相同的每个 cc' 元素,这样就可以最后再排序。
于是要计数的过程是:任选一个 cxc'_x11,求排完序后是 {c}pos\{c\}_{pos} 的方案数。

评论

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

正在加载评论...