Permutation (树状数组)
发布日期:2021-09-19 10:55:58 浏览次数:1 分类:技术文章

本文共 1393 字,大约阅读时间需要 4 分钟。

Given N and K find the N-th permutation of the integers from 1 to K when those permutations are

lexicographically ordered. N starts from 0. Since N is very large N will be represented by a sequence
of K non-negative integers S1, S2, . . . , Sk. From this sequence of integers N can be calculated with
the following expression.
Input
First line of the input contains T (≤ 10) the number of test cases. Each of these test cases consists of
2 lines. First line contains a integer K (1 ≤ K ≤ 50000). Next line contains K integers S1, S2, . . . , Sk.
(0 ≤ Si ≤ K − i).
Output
For each test case output contains N-th permutation of the integers from 1 to K. These K integers
should be separated by a single space.
Sample Input
4
3
2 1 0
3
1 0 0
4
2 1 1 0
4
1 2 1 0
Sample Output
3 2 1
2 1 3
3 2 4 1
2 4 3 1
题目大概:
有t组样例,每组样例有个数k,接下来k个数,分别试s1,s2...sk。
最终是求出k个数的第N个全排列是什么,N 用题目给出的公式算出。
思路:
由于题目要求全排列是按字典序大小来的,那么如果一个数列1  2  3  4.
当i=1时,s1=1时,符合条件的全排列,一定时 2 . . . 到2 . . .的某个数,一定是2开头。
因为(k-i)是剩下的i个数的全排列,第si,就是本位应该是第si+1大的数开头。
所以,最终只需要一位一位求出第i位的数就可以了,第i位的数是剩下的数中的第si+1大的数。
代码:

#include 
using namespace std;const int maxn=5e4+10;int c[maxn];int k;int a[maxn];int lowbit(int x){ return x&(-x);}void add(int x,int v){ while(x
0) { sum+=c[x]; x-=lowbit(x); } return sum;}int work(int d){ int l=1,r=k; while(l<=r) { int mid=(l+r)/2; if(sum(mid)

转载地址:https://blog.csdn.net/a1046765624/article/details/80765708 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:日记(周中)
下一篇:Killer Problem

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2024年03月11日 23时43分26秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

python格式化字符串总结_Python字符串处理方法总结 2019-04-21
python中true什么意思_python中的bool是什么意思 2019-04-21
jacobian 矩阵意义_Jacobian矩阵和Hessian矩阵的作用是什么? 2019-04-21
c++ jna 数据类型_JNA 使用总结 2019-04-21
python中如何遍历列表并将列表值赋予_python中如何实现遍历整个列表? 2019-04-21
apache php mysql架构图_Apache+PHP+MYSQL+Tomcat+JK架构设计技巧与应用实战 2019-04-21
xlnt库如何编译_最新mysql数据库源码编译安装。 2019-04-21
mysql 2003错误 10055_MYSQL无法连接---提示10055错误 2019-04-21
mysql redis缓存层_redis实现缓存的两种方式 2019-04-21
git 改local branch名字_用Git管理Latex写论文的工作流程 2019-04-21
mysql索引篇_MySQL索引篇 2019-04-21
有至少一个用MySQL_Mysql有用的面试题 2019-04-21
mysql select同时update_MySQLSELECT同时UPDATE同一张表 2019-04-21
mysql删除后数据库没变化_mysql之delete删除记录后数据库大小不变 2019-04-21
net mysql start3534_MySQL 5.7.14 net start mysql 服务无法启动-“NET HELPMSG 3534” 的奇怪问题... 2019-04-21
pta两个有序链表的合并_7-1 两个有序链表序列的合并 (20分) --- 内存问题再叙 2019-04-21
python问题描述怎么写_python写文件有时候写不进去怎么办 2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录? 2019-04-21
java 幂取模_快速幂取模算法 2019-04-21
java build path jre_java-如何在安装了jre 7后为Jre 6设置路径? 2019-04-21