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 sequenceof K non-negative integers S1, S2, . . . , Sk. From this sequence of integers N can be calculated withthe following expression.InputFirst line of the input contains T (≤ 10) the number of test cases. Each of these test cases consists of2 lines. First line contains a integer K (1 ≤ K ≤ 50000). Next line contains K integers S1, S2, . . . , Sk.(0 ≤ Si ≤ K − i).OutputFor each test case output contains N-th permutation of the integers from 1 to K. These K integersshould be separated by a single space.Sample Input432 1 031 0 042 1 1 041 2 1 0Sample Output3 2 12 1 33 2 4 12 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大的数。代码:#includeusing 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 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.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
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
python问题描述怎么写_python写文件有时候写不进去怎么办
2019-04-21
qpython3安装lxml_在python的lxml中使用xml目录?
2019-04-21
java 幂取模_快速幂取模算法
2019-04-21