python/TangDou/AcWing/EulerPath/POJ1780.md

POJ 1780 Code(欧拉回路+模拟栈)

一、题目大意

• 1.提供密码的位数。
• 2.密码的输入可以一直保持，取后n位作为密码。如果密码正确则开锁。
• 3.设计一种方法使得在输入最少的情况下破译。（即保证每个密码只输入一次）
• 4.输出输入的数字的序列。

二、题目解析

去密码的前n-1位作为状态节点，将n位数密码作为边,建造有向图。

显然，每个点的入度和出度都为10，则一定存在欧拉回路。

利用简单dfs寻找欧拉回路。（这题好像是要求输出字典序最小的序列）

dfs应该不难写，但是这题如果直接递归会爆栈。所以需要手工用栈模拟递归的过程...

Code

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
const int N = 1100000, M = N << 1;
typedef pair<int, int> PII;
int res[N], rl; // 欧拉路径数组
int st[N];      // 某条边是不是已经访问过了
int base[10];   // 预处理出10^i次方
PII stk[N];     // 模拟栈,第一维记录节点序号，第二维记录边的边号
int top;

// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 循环版本的dfs求欧拉路径
void dfs() {
    // 标识边号为0的边已访问过，并且，让0号点,0号边进入栈中，模拟dfs
    st[0] = 1, stk[++top] = make_pair(0, 0);

    while (top) {               // 如果栈不空，就一直处理,其实就是一个循环版本的dfs
        int u = stk[top].first; // 取出栈顶元素
        int i;
        for (i = h[u]; ~i; i = ne[i]) {
            int id = w[i];        // 魔改的边权数组w[i]中记录的是边的真实数值，可以理解为边号
            if (st[id]) continue; // 如果这条边已经访问过，就不再搜索
            st[id] = 1;           // 标识这条边使用

            stk[++top] = make_pair(e[i], w[i]); // 点e[i]入栈
            h[u] = ne[i];                       // 删边，套路,防止回溯后做无用功，能优化一些性能,不写也可以过掉本题,可以提升100MS的性能
            break;                              // 为啥要break呢？只有这样玩，才能真正的模拟递归！如果没有break,就开始横向平铺了，就不是一下跑到底了！
        }
        // 扫完u了，相当于递归完毕
        if (i == -1) {
            res[++rl] = stk[top].second; // 记录答案
            top--;                       // 出栈
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("POJ1780.in", "r", stdin);
#endif
    int n;

    // 预处理出10^0=1,10^0=1,10^1=10,10^2=100,10^3=1000...
    // 这样一次预处理，下面使用的时候就不用现算了，这比什么快速幂啥的还要靠谱，
    base[0] = 1;
    for (int i = 1; i <= 6; i++) base[i] = base[i - 1] * 10;

    while (scanf("%d", &n) && n) {
        // n=1时需要特判，此时是一个孤立的点，不存在欧拉回路，直接输出答案就完了
        if (n == 1) {
            puts("0123456789");
            continue;
        }
        // 初始化链式前向星
        memset(h, -1, sizeof h);
        // 初始化边是不是访问过
        memset(st, 0, sizeof st);
        top = idx = rl = 0; // 栈清空,链式前向星的游标回零,结果数组的游标回零

        // 枚举每个数字，也就是每个节点,0~10^(n-1)-1,比如n=3，则0~999
        for (int i = 0; i < base[n - 1]; i++) {
            // 正向思考：现在我在i点处，通过向我的尾部不断加入0~9，会去向哪个节点呢？
            // 答：需要把你的最高位裁掉，然后，把新添加的数字放在尾部上
            // 办法就是对base[n - 2]取模，就去掉了最高位，然后乘10，就是左移，然后留出来了最后一位，再想办法拼接0~9
            int t = i % base[n - 2] * 10;
            // 因为使用了链式前向星，而且，本题要求输出字典序最小，所以大数在前，小数在后
            // 从i点出发，目标点是费劲拼出来的t+j,那么，边是啥呢？边可和目标点不是一个意思，它不能去掉首位，应该是i*10+j
            for (int j = 9; j >= 0; j--)
                add(i, t + j, i * 10 + j);
        }

        // 开始寻找欧拉回路
        dfs();

        for (int i = 1; i < n; i++) printf("0");            // 因为是一个一个下场的，最开始前面需要补0
        for (int i = rl; i; i--) printf("%d", res[i] % 10); // 参考前两题的解释
        puts("");                                           // 一组数据结束，需要换行
    }
    return 0;
}