2019HDU多校第五场1005 hdoj6628

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=6628
傻了 比赛中被卡死的一道题
方法：全排列+预处理 （next_permutation）
思路：将n分成大于9和小于等于9两种情况 大于9时 直接使用全排列函数对前K个进行排列即可得出答案，这个是一般情况
小于9时 因为最前面两个数不是按照一般情况的排列顺序，而是按照（n,1/n,2/n-1,1/n,3/n-1,2/n-2,1/.......）的情况，所以进行预处理 9!也就4W 预处理还是很快的
预处理思路：因为全排列不能根据两者之差进行全排列，用一个字符串存储两两之差，先处理出所有全排列，然后根据字符串大小，也就是两两之差的字典序大小用sort进行排序。
//
这里是重点
以上的思路是借鉴别人的 跑出来结果的是200ms 差强人意
于是接下来我进行了优化 发现当N=9时 因为k<10000 而7！=5040 ，因此N=9时的第二位最多也就是2，符合一般情况（这里有点说不清楚，QAQ，读者可以自己证明一下，可以参考上面的特殊情况的排列顺序）
于是预处理只处理到8为止，速度大幅上升
31ms是处理到8,200ms处理到9。

//
直接上代码

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=4e5+10;
const int INF = 0x3f3f3f3f;
int t,n,k;
struct node{
    int x[11];
    char y[11];
}a[11][maxn];
int cmp(node aa,node bb){
    return strcmp(aa.y,bb.y)<0;
}
void init(){ // 预处理 处理出n小于9的情况
    a[1][1].x[0]=1;
    a[2][1].x[0]=2;
    a[2][1].x[1]=1;
    a[2][2].x[0]=1;
    a[2][2].x[1]=2;
    int b[9]={1,2,3,4,5,6,7,8,9};
    for(int k=3;k<9;k++){    
        int cnt=0;
        do{
            cnt++;
            for(int i=0;i<k;i++){
                a[k][cnt].x[i]=b[i];
                if(i) a[k][cnt].y[i-1]=a[k][cnt].x[i]-a[k][cnt].x[i-1]+'A';
            }
        }while(next_permutation(b,b+k));
        sort(a[k]+1,a[k]+cnt+1,cmp);
    }
}
int main(){
    init();
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        if(n>=9){//if n大于等于9
            int b[30];
            b[0]=n;
            for(int i=1;i<n;i++){
                b[i]=i;
            }
            do{
                k--;
                if(k==0) break;
            }while(next_permutation(b,b+n));
            for(int i=0;i<n;i++){
                if(i) printf(" ");
                printf("%d",b[i]);
            }
            printf("\n");
            continue;
        }
        for(int i=0;i<n;i++){//else n小于9
            if(i) printf(" ");
            printf("%d",a[n][k].x[i]);
        }
        printf("\n");
    }
}

//是不是觉得这种解法太麻烦
接下来是梦月巨佬的解法。。。看完我只能说 tql
（只有1W种方法，于是直接暴搜，搜的是相对值而不是绝对值）

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=100010;
const int INF = 0x3f3f3f3f;
int t,n;
int k;
int vis[110];
int ans[110];
bool dfs(int pos,int low,int hi){//low hi 代表最低和最高值，这里的值都是相对值，在输出时要减掉对应的值
    if(pos==n){
        k--;
        if(!k){
            for(int i=0;i<n;i++){
                if(i) printf(" ");
                printf("%d",ans[i]-low+1);//减掉对应值
            }
            printf("\n");
            return 1;
        }
        return 0;
    }
    for(int i=hi-n+1;i<=low+n-1;i++){
        if(vis[i]) continue;
        ans[pos]=i;
        vis[i]=1;
        if(dfs(pos+1,min(low,i),max(hi,i))){
            return 1;
        } 
        vis[i]=0;
    }
    return 0;
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&k);
        memset(vis,0,sizeof(vis));
        ans[0]=n;
        vis[n]=1;
        dfs(1,n,n);
        vis[n]=0;
    }
} 

不难理解，但令人惊叹 这就是大佬⑧
只用了15MS。。。
我好菜啊