【模板】康托展开

题目

洛谷P5367康托展开

题解

假设一个1~n的全排列,将其中一种排列看做一个数字,则可求出它在全排列中从小到大的排名X+1(X表示在它之前的排列个数)。a[i]表示这个排列的第i位(从右往左数)的数字右边有几个数字比它小。(例子:集合1~5,排列(3,4,2,5,1)3的右边有1,2,如果1,2在3的位置上,则可以分别产生(5-1)!种排列。)

求a[i]时需要用树状数组,注意此处的树状数组下标并不表示序列位置,而是数值。从排列的右侧到左侧统计,每次查询已在数组中的比当前位数字小的数的个数,然后再将当前位的数字加入到树状数组中。

代码

Subscribe
提醒
guest
2 评论
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
cyx
cyx
2020年8月26日 下午12:16

【小白解析】
此题套用树状数组1的基本思路。add()函数中的sum[x]++所体现的具体意义为“当前排列中,数字x右侧小于(等于*)x的数字总和”。cnt(i)计算出给定排列的第i位num[i],并将其作为ask()函数的参数x。ask(x)函数随即表示“查找数字x右侧小于x的数字和”,其数学体现为求和sum[]数组的[1,x],读者可参考上一篇模板。
solve()函数从13行正式开始——需要注意的是,28行表示排列的位数是从尾到头依次读入num[]数组的,此处为应接阶乘操作。15行将排列最后一位加入sum[]中,随后开启的循环先计算出当前i个数字排列需要的阶乘(i-1)!:因为当前第一位的位置固定,不需要考虑更换。随后用cnt查找出当前考察位数num[i]右侧小于其的数字的数量,每出现一个,则代表有(i-1)!个排列小于当前排列,故答案加上temp*cnt(i)。
最后将结果加1(计算位数需要算上自己),即为所求结果。
*总感觉应该通过某种手段把等于给去掉,或者说我理解错误了。