rockethon2015 B题 Permutations 规律+构造 - c++编程基础

题意：求使所给公式值最大的第m个排列。

思路：假设已知使f(p)最大的n-1的排列，那么对于使f(p)最大的n的排列，把n放在(n-1)两边均可。因为n放在(n-1)两边，增值为

1+2+...+n,而如果不放在两边，(n-1)到n之间的值 n摆放位置，对于i,如果m<2^(n-i-1),

那么i摆在pos，不然放到可放到的最后面,即last位置。因为接下来(i+1)一定在i左边，而之后比(i+1)大也一定在i左边。详见代码：

/*********************************************************
  file name: B.cpp
  author : kereo
  create time:  2015年02月08日 星期日 21时45分31秒
*********************************************************/
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        #include
        #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              using namespace std; typedef long long ll; const int sigma_size=26; const int N=50+10; const int MAXN=100000+50; const int inf=0x3fffffff; const double eps=1e-8; const int mod=1000000000+7; #define L(x) (x<<1) #define R(x) (x<<1|1) #define PII pair
             
               #define mk(x,y) make_pair((x),(y)) int n; ll m; int ans[N]; ll base[N]; int main(){ base[0]=1; for(int i=1;i