题解 P1384 【幸运数与排列】

· · 题解

救救孩子吧！

两篇题解质量都超级高，以至于我这个蒟蒻啥也看不懂。

在经历了一天腥风血雨后，我决定将我的理解补充一下

直接上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,k,tot,tot2,temp=20,temp2,cnt,ans;
long long a[2100000],b[210],c[210],jc[210],re[210];
void dfs(long long now,long long ans){
    ans+=4*now;//找到所有在1~n范围内的幸运数 
    if(ans>n) return;
    a[++tot]=ans;
    dfs(now*10,ans);
    ans+=3*now;
    if(ans>n) return;
    a[++tot]=ans;
    dfs(now*10,ans);
}
bool isluck(int x){
    for(int i=tot;i>0;i--)  //判断是否是幸运数 
      if(x==a[i]) return true;
      else if(x>a[i]) break;
     return false; 
}
void work(){  //主体部分，首先处理出这个数或其后12位 
    long long temp3=k;
    while(temp){
        int xxx=temp3/jc[temp]+1;
        re[++cnt]=c[xxx];
        for(int i=xxx;i<=temp;i++)
          c[i]=c[i+1];
        temp3%=jc[temp];
        temp--;
    }
    re[++cnt]=c[1];//寻找幸运数位置上也是幸运数的个数 
    for(int i=1;i<=tot2;i++)
      if(isluck(re[b[i]-temp2+1])) //因为一共有n位，而re中只存了后temp位，所以位置是幸运数的有 b[i]-temp2+1，只要判断这些位置上面的是不是幸运数就好了 
        ans++;
}
int main()
{
    freopen("permutation.in","r",stdin);
    freopen("permutation.out","w",stdout);
    scanf("%lld%lld",&n,&k);
    jc[0]=jc[1]=1;
    for(int i=2;i<=20;i++)
      jc[i]=jc[i-1]*i;//预处理阶乘 
    if(n<=12&&jc[n]<k){//如果我们发现这n个数全排列的方案数都不够k种，输出-1 
        printf("-1\n");
        return 0;
    }
    k--;//逆康拓展开时，k应该为有多少个比它小的，所以要-- 
    dfs(1,0);
    if(tot==0){
        printf("0\n");
        return 0;
    }
    sort(a+1,a+tot+1);//排一下序，方便find 
    while(temp>0){
        if(jc[temp]<=k) break;//我们只需要转变后temp位即可获得第k小 
        temp--;
    }
    temp2=n-temp;//from temp2 to n 即后temp位都是什么数 
    for(int i=tot;a[i]>=temp2;i--)//我们将大于temp2的都加进b里，这样的数在最末尾 
      b[++tot2]=a[i];
    for(int i=temp2;i<=n;i++)
      c[i-temp2+1]=i;//将temp2~n的数存进c，方便逆康托展开 
    ans=tot-tot2;//难点，首先我们要理解，我们只动后temp位，前面是从小到大排序的，即如果这个数是幸运数，它所在的位置也是幸运数 
    work();
    if(ans==0)
      printf("-1\n");
    else printf("%lld\n",ans);
    return 0;
}

感谢@单曦增 的思路！！！Orz