Code POJ - 1780（栈模拟dfs）

时间：2022-09-20 15:47:31

题意：

　　就是数位哈密顿回路

解析：

　　是就算了。。。尼玛还不能直接用dfs，得手动开栈模拟dfs

　　emm。。。看了老大半天才看的一知半解

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <cctype>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#include <bitset>

#define rap(i, a, n) for(int i=a; i<=n; i++)

#define rep(i, a, n) for(int i=a; i<n; i++)

#define lap(i, a, n) for(int i=n; i>=a; i--)

#define lep(i, a, n) for(int i=n; i>a; i--)

#define rd(a) scanf("%d", &a)

#define rlld(a) scanf("%lld", &a)

#define rc(a) scanf("%c", &a)

#define rs(a) scanf("%s", a)

#define pd(a) printf("%d\n", a);

#define plld(a) printf("%lld\n", a);

#define pc(a) printf("%c\n", a);

#define ps(a) printf("%s\n", a);

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = 1e6 + , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff;

int n, tot, ss;

int stk[maxn], cnt[maxn], ans[maxn];    //stk存最后的结果   cnt里存的是每层的dfs的i的值  ans里是每层没有取模时的v

int f[maxn];

void no_dfs(int u)

{

    while(cnt[u] < )

    {

        int tmp = u *  + cnt[u];

        cnt[u]++;

        ans[tot++] = tmp;      //为什么先记录 在取模呢？ 因为我们需要的是每次的那个“边” ，而这个no_dfs函数的作用是求出来所有层的dfs在同一个i时的值

        u = tmp % f[n-];

    }

}

int main()

{

    f[] = ;

    for(int i = ; i <= ; i++) f[i] = f[i-] * ;

    while(cin >> n && n)

    {

        mem(cnt, );

        ss = tot = ;

        no_dfs();

        while(tot)

        {

            int x = ans[--tot];

            stk[ss++] = x % ; //取模既能得到最后一位 也就是“边”

            no_dfs(x / );     //相当于dfs中回溯到上一层

        }

        for(int i = ; i < n - ; i++)

            cout << "";

        for(int i = ss - ; i >= ; i--)

            cout << stk[i];

        cout << endl;

    }

    return ;

}

相关文章