【HDOJ6628】permutation 1（dfs）

题意：求1到n的排列中使得其差分序列的字典序为第k大的原排列
n<=20，k<=1e4
思路：爆搜差分序列，dfs时候用上界和下界剪枝
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 typedef unsigned int uint;
 5 typedef unsigned long long ull;
 6 typedef pair<int,int> PII;
 7 typedef pair<ll,ll> Pll;
 8 typedef vector<int> VI;
 9 typedef vector<PII> VII;
10 #define N  1100000
11 #define M  4100000
12 #define fi first
13 #define se second
14 #define MP make_pair
15 #define pi acos(-1)
16 #define mem(a,b) memset(a,b,sizeof(a))
17 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
18 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
19 #define lowbit(x) x&(-x)
20 #define Rand (rand()*(1<<16)+rand())
21 #define id(x) ((x)<=B?(x):m-n/(x)+1)
22 #define ls p<<1
23 #define rs p<<1|1
24 
25 const ll MOD=998244353,inv2=(MOD+1)/2;
26       double eps=1e-6;
27       int INF=1e9;
28 
29 int b[100],c[100],ans[100],d[100],n,K;
30 
31 int read()
32 {
33    int v=0,f=1;
34    char c=getchar();
35    while(c<48||57<c) {if(c=='-') f=-1; c=getchar();}
36    while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar();
37    return v*f;
38 }
39 
40 void dfs(int k,int l,int r)
41 {
42     if(l>r) return;
43     if(K==0) return;
44     if(k==n)
45     {
46         K--;
47         if(K==0)
48         {
49             rep(i,1,n) ans[i]=c[i]+l;
50         }
51         return;
52     }
53     rep(i,1-c[k]-n,n-c[k]-1)
54     {
55         int t=c[k]+i+n;
56         if(!b[t])
57         {
58             b[t]=1;
59             c[k+1]=c[k]+i;
60             dfs(k+1,max(l,-c[k+1]+1),min(r,n-c[k+1]));
61             b[t]=0;
62         }
63     }
64 }
65 
66 int main()
67 {
68     int cas=read();
69     while(cas--)
70     {
71         n=read(),K=read();
72         rep(i,1,n+n) b[i]=0;
73         b[n]=1;
74         dfs(1,1,n);
75         rep(i,1,n-1) printf("%d ",ans[i]);
76         printf("%d
",ans[n]);
77     }
78 
79     return 0;
80 }