AcWing 842. 排列数字（周四）

复习

• AcWing 1242. 修改数组（周一）
• AcWing 1234. 倍数问题（周二）
• AcWing 1171. 距离（周三）

前言

害，周二周三的题其实对我来说都太难了。感觉现在学习有点递归算法的感觉，就是学一个发现另外的东西不会。今天写一个 dfs 的模板题好了，明天再写一个 dfs 的模板题，下周再学一下 tarjan 算法。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+1e5+10;
int p[N];
int find(int x){
    if(x!=p[x]){
        p[x]=find(p[x]);
    }
    return p[x];
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<N;i++){
        p[i]=i;
    }
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        x=find(x);
        cout<<x<<" ";
        p[x]=x+1;
    }
    return 0;
}

周二那个题，还有昨天的题确实太难了，等一个好天气，我有足够的时间和勇气的时候再去写那个题。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=10;
int path[N];
bool st[N];
int n;
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            cout<<path[i]<<" ";
        }
        puts("");
        return ;
    }
    for(int i=1;i<=n;i++){
        if(!st[i]){
            path[u]=i;
            st[i]=true;
            dfs(u+1);
            path[u]=0;
            st[i]=false;
        }
    }
}
int main(){
    cin>>n;
    dfs(0);
    return 0;
}

思路

排列数字感觉需要注意的点就是，路径存的下标是从 0 开始的，然后数字是从 1 开始计算的，恢复现场是在递归结束之后，回溯之前，这样子可以保证前面的搜索不会影响下一次搜索。搜索树最开始是有 n+1 层，我们从根节点，第 0 层开始搜索，一直搜索到最下面那层结束，然后回溯。深搜，或者叫暴搜，是一条路径走到底再考虑其他路径。