\(POJ\) \(1780\) \(Code\)(欧拉回路+模拟栈)
一、题目大意
- 1.提供密码的位数。
- 2.密码的输入可以一直保持，取后\(n\)位作为密码。如果密码正确则开锁。
- 3.设计一种方法使得在输入最少的情况下破译。（即保证每个密码只输入一次）
- 4.输出输入的数字的序列。
二、题目解析
去密码的前\(n-1\)位作为状态节点，将\(n\)位数密码作为边,建造有向图。
显然，每个点的入度和出度都为\(10\)，则一定存在欧拉回路。
利用简单\(dfs\)寻找欧拉回路。（这题好像是要求输出字典序最小的序列）
\(dfs\)应该不难写，但是这题如果直接递归会爆栈。所以需要手工用栈模拟递归的过程...
这题有两坑:
第一坑是用数字来当点的话，会\(MLE\)，因为每个数字可以连\(10\)条边，\(100w\)条边会\(MLE\)，即使用\(vector\)也会\(TLE\)。
这题可以用边来记录，对于n为1时直接输出，然后后面的，比如12,23这两个点就用边权值为123来表示这两个点，这样就把点和边的范围都缩小了10倍。
第二坑是用递归的dfs会爆栈，亲测即使加手扩栈也会爆。。（简直丧心病狂。。）需要用非递归版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;
int res[N], rl; // 欧拉路径数组
int st[N]; // 某条边是不是已经访问过了
int base[10]; // 预处理出10^i次方
int stk[N], top; // 模拟栈
int num[N]; // 点v入栈时，同步记录是使用哪条现实中的边号进入的
// 链式前向星
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号点进入栈中，模拟dfs
st[0] = 1, stk[++top] = 0;
while (top) { // 如果栈不空，就一直处理,其实就是一个循环版本的dfs
int u = stk[top]; // 取出栈顶元素
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] = e[i]; // 点e[i]入栈
num[top] = w[i]; // 配合e[i]，标识i这条边的真正边号w[i]
h[u] = ne[i]; // 删边，套路,防止回溯后做无用功，能优化一些性能,不写也可以过掉本题,可以提升100MS的性能
break; // 为啥要break呢？只有这样玩，才能真正的模拟递归！如果没有break,就开始横向平铺了，就不是一下跑到底了！
}
// 扫完u了，相当于递归完毕
if (i == -1) {
res[++rl] = num[top]; // 记录答案
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...
// 这样一次预处理，下面使用的时候就不用现算了，这比什么快速幂啥的还要靠谱，
// 不能指望pow(10,i)现算，太慢，而且POJ太老了，pow使用起来也是一堆障碍
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);
memset(num, 0, sizeof num);
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;
}