Math
昨晚CF的B题，由于昨晚和别人聊天，就没做啦，也是因为昨晚OJ太不给力，第一题始终不给答案，我比较蛋疼。
http://codeforces.com/contest/513/problem/B2
第二题是找mth permutation 使得所有子序列的最小值累加和达到最大，什么意思呢，所有permutation有一个最大和，而且有很多个，从这些里找到
字典序第m个，今天实验室聚餐吃完，我坐在躺椅上想，发现实际就是2^(n-1)个，然后1<=m<=2^(n-1), 因为最大，1不能再中间，不然某一次2元就有两个1 ，
而实际最大sum 一定是sum(i=1->n) (i(i+1)/2), 由此2也不能是边上，但是可以12… 因此我YY了一个算法，就是for 1->n, 每次从当前的边界两个选一个，然后剩下的里面也是
边界选2， 例如这样就有1.。。2 12.。。。 2.。。1 。。。。21 这样四个，其实2^(n-1) 是从算法里算出来的= =， 然后就可以了哇谁，算法复杂度瞬间从n^2*n!降到n了
其实直接上类似求第k个全排列就不需要枚举全部，例如LC上的康拓编码，和那个如出一辙，找规律。
另外我已经第N+1 次饭了 ULL m=1<<(n) 的错误了，当n>=32, 一定要写 ULL m=1ULL<<(n), 因为整数常数默认int, 浮点数默认double, 要么就别装逼，用一个pow, 就不会出错，
然后循环里一直除2
代码如下
int main()
{
while(cin>>n>>m)
{
int ans[n];m--;
int s=0, e=n-1;
for(int i=1;i<n;i++)
{
ULL mod=(1ULL<<(n-1-i));
if(m/mod==0) ans[s++]=i;
else ans[e--]=i;
m%=mod;
}
ans[s]=n;
for(int i=0;i<n;i++) cout<<ans[i]<<" ";
cout<<endl;
}
return 0;
}
再附上暴力法
bool u[maxn];
int num[maxn];
vector<int> cur, ans;
int sum, n, ki;
ULL m;
int f(vector<int> cur)
{
int sumf=0;
for(int i=0;i<n;i++)
{
int minx=INT_MAX;
for(int j=i;j<n;j++)
minx=min(minx, cur[j]), sumf+=minx;
}
return sumf;
}
void dfs(int i)
{
if(i>=n)
{
int fsum=f(cur);
if(fsum==sum)
{
if(ki==m)
ans=cur;
ki++;
}
return ;
}
for(int j=0;j<n;j++)
{
if(!u[j])
{
u[j]=1;
cur.push_back(num[j]);
dfs(i+1);
cur.pop_back();
u[j]=0;
}
}
}
int main()
{
while(cin>>n>>m)
{
int ans[n];m--;
int s=0, e=n-1;
for(int i=1;i<n;i++)
{
ULL mod=(1ULL<<(n-1-i));
if(m/mod==0) ans[s++]=i;
else ans[e--]=i;
m%=mod;
}
ans[s]=n;
for(int i=0;i<n;i++) cout<<ans[i]<<" ";
cout<<endl;
/*
sum=0;
for(int i=1;i<=n;i++) sum+=(i*(i+1)), num[i-1]=i;
sum/=2;
ki=1;cur.clear();ans.clear();memset(u, 0, sizeof u);
dfs(0);
for(int i=0;i<n;i++) cout<<ans[i]<<" ";
cout<<endl;*/
}
return 0;
}