\(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;
}