7
11
2016
0

July 11th 考试改错+总结

T1 排列perm

给定一个1~n的排列P,并规定操作:

选择排列中任意一段长度为2*b的区间,交换前半部分与后半部分

操作若干次所得到的所有排列的集合中,求原排列P是字典序从小到大第几个。

一个全排列,每次交换相邻两个数,可以得到所有全排列。但b>1时不成立。相邻的两次相同的交换操作没有意义,但如果两次相同交换操作不相邻则可能产生新的排列。

b==1时:

已知全排列求名次:康托展开 树状数组O(nlogn)

已知名次求排列:康托逆展开

bzoj3301

1、题目都要看,暴力分要拿稳。这也是需要能力的。

 

Category: 树套树 | Tags: | Read Count: 170

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com