题解 | #牛牛摆木棒#

牛牛摆木棒

http://www.nowcoder.com/practice/a8db7bce8a4e48029bda368a0bc61345

题意

称一个 $1\sim n$ 的排列为波浪形的排列当且仅当 $\forall i(2\le i\le n-1)$ ， $(a_i-a_{i-1})(a_i-a_{i+1})>0$ 。
求 $1\sim n$ 的第 $k$ 个波浪形的排列。

解法1：DFS（TLE）

不妨把波列形的排列看成小虫的游走。小虫从 $1\sim n$ 的任意点，任意方向出发，选择前方任意一个未访问过的点，到达后掉头。这样最终产生一个排列。

可以按字典序暴力搜索所有排列，第 $k$ 个排列即为答案。

下图为 $n=3$ 的DFS树：
图片说明

代码

const int N=25;
class Solution {
   public:
    /**
     *
     * @param n int整型 木棒的个数
     * @param k long长整型 第k个排列
     * @return int整型vector
     */
    int a[N];
    bool vis[N];
    bool flag;
    long long cnt;
    void dfs(int n, int k, int pos, bool dir) {
        if (pos == n) { // 搜到一个排列
            //for (int i = 0; i < n; ++i) printf("%d ", a[i]);
            ++cnt;
            //cout << cnt << endl;
            if (cnt == k) flag = true; // 搜到第 k 个排列
            return;
        }
        if (pos == 0) {
            for (int i = 1; i <= n; ++i) {
                a[pos] = i;
                vis[i] = true;
                dfs(n, k, pos + 1, 0); // 先向左爬
                vis[i] = false;
                if (flag) return;
                vis[i] = true;
                dfs(n, k, pos + 1, 1); // 再向右爬
                vis[i] = false;
                if (flag) return;
            }
        } else if (!dir) {
            int cnt = 0;
            for (int i = 1; i < a[pos - 1]; ++i) {
                if (vis[i]) continue;
                a[pos] = i;
                vis[i] = true;
                dfs(n, k, pos + 1, 1); // 去左边的点向右爬
                vis[i] = false;
                if (flag) return;
            }
        } else {
            int cnt = 0;
            for (int i = a[pos - 1] + 1; i <= n; ++i) {  
                if (vis[i]) continue;
                a[pos] = i;
                vis[i] = true;
                dfs(n, k, pos + 1, 0); // 去右边的点向左爬
                vis[i] = false;
                if (flag) return;
            }
        }
    }
    vector<int> stick(int n, long long k) {
        // write code here
        cnt = 0;
        flag = false;
        for (int i = 1; i <= n; ++i) vis[i] = false;
        dfs(n, k, 0, 0);
        vector<int> ret;
        for (int i = 0; i < n; ++i) ret.push_back(a[i]);
        return ret;
    }
};

复杂度分析

空间复杂度：保存dfs树链信息 $O(n)$
时间复杂度：需要逐个枚举满足要求的排列。不太方便精确分析，但粗略估计个数在 $\frac{n!}{2^n}$ 到 $\frac{n!}{2^{\frac{n}{2}}}$ 之间，复杂度比 $O(n!)$ 略低。

解法2：DP+DFS

记 $dp[i][j]$ 为小虫前方有 $i$ 个未访问的点，后方有 $j$ 个未访问的点时的方案数。
有递推关系 $dp[i][j]=\sum_{0\le k\le i-1}dp[i+j-1-k][k]$ 。
图片说明
而dfs树上每棵子树的size恰好与dp值相对应。利用size信息，我们便可以判断答案在那棵子树中。
dfs时，我们只需要搜索答案所在的那条链即可。

代码

const int N=25;
class Solution {
public:
    /**
     * 
     * @param n int整型 木棒的个数
     * @param k long长整型 第k个排列
     * @return int整型vector
     */
    long long dp[N][N];
    int a[N];
    bool vis[N];
    void init(){
        int lim=20;
        dp[0][0]=1;
        for(int sum=1; sum<=lim; ++sum){
            for(int i=0; i<=sum; ++i){
                int j=sum-i;
                dp[i][j]=0;
                for(int k=0; k<i; ++k){
                    dp[i][j]+=dp[sum-1-k][k]; // 递推
                }
            }
        }
        for(int i=1; i<=lim; ++i) vis[i]=false;
    }

    void dfs(int n, int pos, long long cur, bool dir){
        if(pos==n) return;
        if(pos==0){
            for(int i=1; i<=n; ++i){
                long long sz=dp[i-1][n-i]; // 子树大小
                if(cur>sz) cur-=sz; // 跳过子树
                else{ // 进入子树
                    a[pos]=i;
                    vis[i]=true;
                    dfs(n, pos+1, cur, 0);
                    vis[i]=false;
                    break;
                }
                sz=dp[n-i][i-1];
                if(cur>sz) cur-=sz;
                else{
                    a[pos]=i;
                    vis[i]=true;
                    dfs(n, pos+1, cur, 1);
                    vis[i]=false;
                    return;
                }
            }
        } else if(!dir){
            int cnt=0;
            for(int i=1; i<a[pos-1]; ++i){
                if(vis[i]) continue;
                cnt++;
                long long sz=dp[n-pos-cnt][cnt-1];
                if(cur>sz) cur-=sz;
                else{
                    a[pos]=i;
                    vis[i]=true;
                    dfs(n, pos+1, cur, 1);
                    vis[i]=false;
                    return;
                }
            }
        } else{
            int cnt=0;
            for(int i=1; i<=n; ++i){
                if(vis[i]) continue;
                cnt++;
                if(i<=a[pos-1]) continue;
                long long sz=dp[cnt-1][n-pos-cnt];
                if(cur>sz) cur-=sz;
                else{
                    a[pos]=i;
                    vis[i]=true;
                    dfs(n, pos+1, cur, 0);
                    vis[i]=false;
                    return;
                }
            }
        }
    }
    vector<int> stick(int n, long long k) {
        // write code here
        init();
        dfs(n, 0, k, 0);
        vector<int> ret;
        for(int i=0; i<n; ++i) ret.push_back(a[i]);
        return ret;
    }
};