POJ 1780 Code 题解 欧拉通路 利用栈实现递归

题目链接：POJ 1780 Code
题意：

有一个保险箱，其密码为n位十进制数字，这个保险箱只要输入包含密码的子串，保险箱就会会打开，例如密码为123，而对于输入1241234由于输入中包含123这个子串，此时保险箱就会打开。有一种比较暴力的方式可以破解保险箱，即依次从最小的数字输入到最大的数字，例如密码是两位数字，只需要依次输入00,01,02,...,99一定就能打开保险箱，但是这是一种 比较笨的方法，有一种巧妙的方法可以最差在$10^n+n-1$次按键就打开保险箱（笨办法需要最多$n\times 10^n$次按键），你需要输出这样的按键顺序。即输出一个最短长度的字符串，这个字符串包含所有的可能密码子串。

题解：

首先我们需要明白为什么最短的字符串长度为$10^n+n-1$。首先我们一定要输入任意一个可能密码，这个可能的密码的长度是$n$，对于这个密码，我们在其后面追加一个按键的时候，其有效的输入就变成了原密码的后$n-1$位与当前的按键进行拼接，在最优的情况下我们可以保证，每一次按键会产生一个之前没有出现过的密码串，因此对于所有的密码串可能：第一次需要输入$n$个按键，后面最优情况下每一个密码串只需要输入一个按键，总共需要$n+10^n-1$次按键。
如何找到这样的序列？我们可以将所有的$n-1$位的可能性看成点，对于每一个点建立$10$条边，这些边有一个权重依次为$[0,9]$之间的整数，这些边连接到的点为出发点的编号与权重拼接后的的后$n-1$所表示的状态。例如当$n$为$3$的时候，我们有一百个点，点的编号依次为$00,01,02,03,...,99$对应$2$位密码串的所有情况，以$00$号结点为例，若建立的边边权为$1$那么，拼接后变成$001$此时的后两位为$01$因此这条边连接$00$和$01$这两个结点边权为$1$。不难发现这样建立后图中每个结点的入度与出度均为$10$，且图是一个强连通图，因此欧拉回路存在。
那么这道题和欧拉回路又有什么关系呢？实际上上面建立的图的欧拉回路的起点编号与经过的边的边权组成的序列即为所求序列。首先点的编号长度为$n-1$，一共有$10^{n-1}$个点而每个点有$10$条边，因此一共有$10^n$条边，因此串的长度为$10^n+n-1$。由于每个点的编号一定是不同的，因此在每个编号后依次追加的$10$种按键产生的长度为$n$的可能密码串一定是不同的，因此一共会产生$10^n$种密码串，这也就覆盖了所有的密码情况。因此我们只需要求出欧拉回路即可找到要求的字符串。
需要注意的是，这个题目如果使用递归来实现Hierholzer的话，由于POJ上的栈空间太小会发生栈溢出，因此需要使用栈来实现递归。同时这道题目对常数要求较为严格，由于POJ只支持C++98因此移动语义并不存在，因此要避免过多使用STL与创建过多的临时变量。

代码：POJ1780

原文地址：https://blog.csdn.net/qq_45523675/article/details/136039180

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！