思路

这道题其实如果想通了就不难，我们可以发现最小的那个数放在前面和后面那个序列算出来值都是一样的，就像

[1,4,3,2]

和

[4,3,2,1]

算出来是一样的。

那该怎么做呢？我们可以这么想：就拿上面那个序列举例，算这个序列总的计算结果可以分解成把

1

去掉后剩下的序列的计算结果再加上

3

个

1

。所以，除了

n

的每个数都可以放前面或后面，也就是两种方案。这样，我们得出长度为

n

的排列总共有

2^{n-1}

种最大值方案。

剩下的就很简单了。我们先判断

2^{n-1}

是否小于

k

，如果小于，则取不到第

k

种方案，输出

-1

。接下来，因为它会按字典序排序，我们就把所有方案给分成

1

在前或后两种。我们把前指针命名为

totf

，后指针命名为

totb

，把答案数组命名为

a

。如果在前面，就把

a_{totf}

设为

1

，再把

totf

加

1

。反之将、把

totb

减

1

。这下，我们把

1

处理好了，在将其去掉后的子序列处理

2

，后面以此类推。

Code

~~估计这里很多人期待吧~~

CPP

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int inf=2e9;
const db eps=1e-7;
int n,a[200005],totf,totb;
ll pot[70],k;
void dfs(int u,ll add)
{
    if(u==n)
    {
        a[totf]=u;
        return ;
    }
    if(n-u>42||pot[n-u-1]+add>=k)
    {
        a[totf]=u;
        totf++;
        dfs(u+1,add);
    }
    else 
    {
        a[totb]=u;
        totb--;
        dfs(u+1,add+pot[n-u-1]);
    }
}
void solve()
{
    cin>>n>>k;
    totf=1;
    totb=n;
    if(n<=42&&pot[n-1]<k)
    {
        cout<<"-1\n";
        return ;
    }
    dfs(1,0);
    //cerr<<"ok";
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    cout<<"\n";
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pot[0]=1;
    for(int i=1;i<=45;i++)
    {
        pot[i]=pot[i-1]*2;
    }
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

提交记录

十年OI一场空，不开LONG LONG 见祖宗

题解：CF2040C Ordered Permutations

文章操作

思路

Code

十年OI一场空，不开LONG LONG 见祖宗

相关推荐

评论

题解：CF2040C Ordered Permutations