2.4 数据结构基础
本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第6章。
习题6-1 平衡的括号（Parentheses Balance，UVa673）
输入一个包含“（）”和“［］”的括号序列，判断是否合法。具体规则如下：
（1）空串合法。
（2）如果A和B都合法，则AB合法。
（3）如果A合法，则（A）和［A］都合法。
【分析】
对输入的序列进行遍历，同时用一个栈维护当前遍历过但是未配对的括号，栈就用STL的stack。
（1）遍历到右括号，如果栈为空，说明无法匹配到左括号，直接退出。如果栈不为空，需与最近的左括号也就是栈顶的元素匹配。如果匹配直接出栈，继续处理序列中的下一个元素。否则直接退出。
（2）遇到左括号，入栈。
（3）遍历完之后如果栈不为空，则说明有无法匹配的左括号，序列非法。
完整程序如下：
习题6-2 S树（S-Trees，UVa712）
给一棵满二叉树，每一层代表一个01变量，取0时往左走，取1时往右走。例如图2.19中两个图都对应表达式x1∧（x2∨x3）。
给出所有叶子的值以及一些查询（即每个变量xi的取值），求每个查询到达的叶子的值。例如有4个查询：000, 010, 111, 110，则输出应为0011。
图2.19
【分析】
仔细观察可以发现，可以不用建立二叉树的结构，每遍历一个输入的字符，就沿树下降一层，目标叶子所在的区间就缩小一半，当处理完所有的xi之后，刚好到达叶子，区间缩小为只有一个元素。注意叶子结点的个数是2n而不是n。
完整程序如下：
习题6-3 二叉树重建（Tree Recovery，ULM 1997，UVa536）
输入一棵二叉树的先序遍历和中序遍历序列，输出它的后序遍历序列，如图2.20所示。
图2.20
【分析】
具体思路可以参考《算法竞赛入门经典（第2版）》6.3.3节的二叉树重建。
习题6-4 骑士的移动（Knight Moves，UVa439）
输入标准8*8国际象棋棋盘上的两个格子（列用a～h表示，行用1～8表示），求马最少需要多少步从起点跳到终点。例如从a1到b2需要4步。马的移动方式如图2.21所示。
图2.21
【分析】
使用Point类来存储位置，然后再存储向8个方向跳对应的8个向量，在BFS搜索位置遍历8个方向时就可以直接用向量计算来简化代码。而且在比较点坐标时也比较方便，具体请参考代码。完整程序（C＋＋11）如下：
习题6-5 巡逻机器人（Patrol Robot，ACM/ICPC Hanoi 2006，UVa1600）
机器人要从一个m*n（1≤m，n≤20）的网格的左上角（1，1）走到右下角（m，n）。网格中的一些格子是空地（用0表示），其他格子是障碍（用1表示）。机器人每次可以往4个方向走一格，但不能连续地穿越k（0≤k≤20）个障碍，求最短路长度。起点和终点保证是空地。例如对于图2.22所示左图的数据，图2.22的右图是最优解，路径长度为10。
图2.22
【分析】
首先，与习题6-3一样，同样可以使用Point类来简化处理逻辑。而当前状态除了包含当前坐标，还要包含已经穿越的障碍个数，这一点是和上题的关键区别，BFS即可。完整程序如下：
习题6-6 修改天平（Equilibrium Mobile，NWERC 2008，UVa12166）
用一个深度不超过16的二叉树，代表一个天平。每根杆都悬挂在中间，每个秤砣的重量已知。至少修改多少个秤砣的重量才能让天平平衡？如图2.23所示，把7改成3即可。
图2.23
【分析】
树在最终平衡之后，只要确定单个结点的重量，整个树的重量就可以确定。此时深度n（根结点深度为0）的子树重量为深度n-1子树重量的1/2。如果一个深度n的秤砣结点重量为x，则整棵树的重量就是x*2n。要求计算出需修改重量的秤砣的最小个数，反过来就是计算不需要修改的秤砣的最大个数。对于第n层的重量为x结点，假设它不需要修改，则最终平衡的树的重量就是T＝x*2n。遍历每个结点，计算出现次数最多的那个T的出现次数K，则（结点的个数－K）即是所求的答案。完整程序如下：
习题6-7 Petri网模拟（Petri Net Simulation，ACM/ICPC World Finals 1998，UVa804）
你的任务是模拟Petri网的变迁。Petri网包含NP个库所（用P1，P2…表示）和NT个变迁（用T1，T2…表示）。0＜NP，NT＜100。当每个变迁的每个输入库所都至少有一个token时，变迁是允许的。变迁发生的结果是每个输入库所减少一个token，每个输出库所增加一个token。变迁的发生是原子性的，即所有token的增加和减少应同时进行。注意，一个变迁可能有多个相同的输入或者输出。如果有多个变迁是允许的，一次只能发生一个。
如图2.24所示，一开始只有T1是允许的，发生一次T1变迁之后有一个token会从P1移动到P2，但仍然只有T1是允许的，因为2要求P2有两个token。再发生一次T1变迁之后P1中只剩一个token，而P2中有两个，因此T1和T2都可以发生。假定T2发生，则P2中不再有token，而P3中有一个token，因此T1和T3都是允许的。
图2.24
输入一个Petri网络。初始时每个库所都有一个token。每个变迁用一个整数序列表示，负数表示输入库所，正数表示输出库所。每个变迁至少包含一个输入和一个输出。最后输入一个整数NF，表示要发生NF次变迁（同时有多个变迁允许时可以任选一个发生，输入保证这个选择不会影响最终结果）。
【分析】
首先建立一个结构Transition表示一个变迁，包含所有的输入库所编号及其出现次数，使用map＜int，int＞来表示，例如题图中T2中P2出现两次。另外用一个vector＜int＞存储所有的输出Place编号。这个Transition只有在每个编号为i的输入库所中的Token个数≥ i在出现的次数时才被允许。
每一次变迁时，对于输入库所i来说，Token个数要减掉其在Transition的输入中出现的次数，然后所有的输出库所的Token增加1。完整程序（C＋＋11）如下：
习题6-8 空间结构（Spatial Structures，ACM/ICPC World Finals 1998，UVa806）
黑白图像有两种表示法：点阵表示和路径表示。路径表示法首先需要把图像转换为四分树，然后记录所有黑结点到根的路径。例如对于如图2.25所示的图像。
图2.25
四分树如图2.26所示。
图2.26
NW、NE、SW、SE分别用1、2、3、4表示。最后把得到的数字串看成是五进制的，转换为十进制后排序。例如上面的树在转换、排序后的结果是9 14 17 22 23 44 63 69 88 94 113。
你的任务是在这两种表示法之间进行转换。在点阵表示法中，1表示黑色，0表示白色。图像总是正方形的，且长度n为2的整数幂，并满足n≤64。输入输出细节请参见原题。
【分析】
因为题目实际上是要求在四分树的两种表示形式之间转换，那么很容易想到的就是要建立四分树的结构。
对于输入黑色点的情况，每一个点计算出其在Grid中对应的区域，然后给对应的区设置黑色标记即可。对于输入是Grid的情况，可以使用递归的方法建立四分树，然后使用DFS来搜索到所有的黑结点，并且在沿着树向下搜索的过程中记录相应的路径即可。完整程序如下：
习题6-9 纸牌游戏（“Accordian“Patience，UVa127）
把52张牌从左到右排好，每张牌自成一个牌堆（pile）。当某张牌与它左边那张牌或者左边第三张牌match（花色suit或者点数rank相同）时，就把这张牌移到那张牌上面去。移动之后还要看看是否可以进行其他的移动。只有位于牌堆顶部的牌才能移动或者参与match。当牌堆之间出现空隙时要立刻把右边的所有牌堆左移一格来填补空隙。如果有多张牌可以移动，先移动最左边的那张牌；如果既可以移一格也可以移3格时，移3格。按顺序输入52张牌，输出最后的牌堆数以及各牌堆的牌数。
样例输入：
样例输出：
【分析】
本题牵涉两种数据结构，一是栈（模拟牌堆），使用STL的stack即可；而多个牌堆之间实际上是链表的关系（中间牵涉牌堆的删除以及连接），自己定义一个LinkNode结构，内部包含一个stack。同时，加一个头结点方便处理。完整程序（C＋＋11）如下：
习题6-10 10-20-30游戏（10-20-30，ACM/ICPC World Finals 1996，UVa246）
有一种纸牌游戏叫作10-20-30。游戏使用除大王和小王之外的52张牌，J、Q、K的面值是10，A的面值是1，其他牌的面值等于它的点数。
把52张牌叠放在一起放在手里，然后从最上面开始依次拿出7张牌从左到右摆成一条直线放在桌子上，每一张牌代表一个牌堆。每次取出手中最上面的一张牌，从左至右依次放在各个牌堆的最下面。当往最右边的牌堆放一张牌以后，重新往最左边的牌堆上放牌。
如果当某张牌放在某个牌堆上后，牌堆的最上面两张和最下面一张牌的和等于10、20或者30，这3张牌将会从牌堆中被拿走，然后按顺序放回手中并压在最下面。如果没有出现这种情况，将会检查最上面一张和最下面两张牌的和是否为10、20或者30，解决方法类似。如果仍然没有出现这种情况，最后检查最下面3张牌的和，并用类似的方法处理。例如，如果某一牌堆中的牌从上到下依次是5、9、7、3，那么放上6以后的布局如图2.27所示。
图2.27
如果放的不是6，而是Q，对应的情况如图2.28所示。
图2.28
如果某次操作后某牌堆中没有剩下一张牌，那么把该牌堆永远地清除掉，并把它右边的所有牌堆顺次往左移。如果所有牌堆都清除，游戏胜利结束；如果手里没有牌了，游戏以失败告终；有时游戏永远无法结束，这时我们说游戏出现循环。给出52张牌最开始在手中的顺序，请模拟这个游戏并计算出游戏结果。
【分析】
这个题目在数据结构的选取方面关键有几点：
（1）牌堆所用的数据结构，因为要在两端进行操作，所以使用STL中deque（双端队列）最为合适：typedef deque＜int＞ Pile。
（2）要把当前的局面记录下来进行判重，可以将所有的牌堆中的牌编码成一个字符串：每张牌的牌面直接转成char，牌堆与牌堆之间用“|”之类的分隔符隔开，然后局面就可以用string来表示。同时使用一个set＜string＞来对局面的编码进行判重。
（3）所有的牌堆因为牵涉有删除以及移位操作，可用STL中的双向链表list＜Pile*＞来表示。
每一次的模拟过程就是以下几个步骤：
（1）依次判断牌堆和手中的牌是否已经清空，如果清空，直接输出结果。
（2）对当前局面进行编码，然后判重，如果重复直接退出。
（3）从手牌取出一张并且放到左边的牌堆，同时把这个牌堆放到所有牌堆的最后。
（4）针对最后的牌堆进行10-20-30的操作。操作完成之后判断牌堆是否已经清空，如果已经被清空，则从链表中删除这个牌堆。
完整程序（C＋＋11）如下：
习题6-11 树重建（Tree Reconstruction，UVa10410）
输入一个n（n≤1000）结点树的BFS序列和DFS序列，你的任务是输出每个结点的儿子列表。输入序列（不管是BFS还是DFS）是这样生成的：当一个结点被扩展时，它的所有孩子应该按照编号从小到大的顺序访问。
例如，若BFS序列为4 3 5 1 2 8 7 6，DFS序列为4 3 1 7 2 6 5 8，则一棵满足条件的树如图2.29所示。
图2.29
【分析】
根据题目描述可以得出结论：结点u及其直接孩子结点在DFS和BFS序列中出现的顺序一致且都是递增的，且孩子结点在BFS序列形成连续子序列。据此可以得到u的所有子结点，再根据子结点在DFS序列中的位置，就可以得到这两个子结点对应的子树对应的DFS序列以及子树的所有结点。
据此就可以设计出一个递归逻辑，读入一个子树的DFS序列，以及这个序列对应的BFS序列，构造这棵子树。
举例来说，对于以4为根结点的子树，输入的BFS和DFS序列分别是（灰色表示4的孩子结点）：BFS: 3 5 1 2 8 7，DFS: 3 1 7 2 6 5 8。则4的两个孩子结点分别是3和5。根为3的子树对应的BFS和DFS序列就是：BFS: 1 27 6，DFS: 1 7 2 6。而5为根的子树对应的两个子序列就是8。
根为3的子树，可以继续递归拆成两棵子树。
（1）子树1对应的子树序列：BFS: 7，DFS: 7。
（2）子树2对应的子树序列：BFS: 6，DFS: 6。
如此即可完整还原整棵树，算法的时间复杂度为O(n2)。完整程序（C++11）如下：
习题6-12 骰子难题（A Dicey Problem, ACM/ICPC World Finals 1999, UVa810）
如图2.30所示是一个迷宫，如图2.31所示是一个骰子。你的任务是把骰子放在起点（骰子顶面和正面的数字由输入给定），经过若干次滚动以后回到起点。
每次到达一个新格子时，格子上的数字必须和它接触的骰子上的数字相同，除非到达的格子上画着五星（此时，与它接触的骰子上的数字可以任意）。输入一个R和C行（1≤R,C≤10）的迷宫、起点坐标以及顶面、正面的数字，输出一条可行的路径。
图2.30
图2.31
【分析】
首先要建立表示骰子当前状态的结构，其中包括当前的行列编号，以及顶面和正面的数字（由此可以确定其他4个面的数字）。然后就是使用BFS来寻找最短路径。
需要注意以下几点：
（1）在状态中还要保留指向上一步状态的指针。
（2）代码中手工打表来建立由顶面和正面数字得到左面数字的映射，这样初始状态输入时就直接建立6个面的状态。
（3）每次骰子旋转时，可以根据上一次的状态首先确认新的顶面和正面状态，然后即可确认6个面的状态。
完整程序如下：
习题6-13 电子表格计算器（Spreadsheet Calculator, ACM/ICPC World Finals 1992, UVa215）
在一个R行C列（R≤20，C≤10）的电子表格中，行编号为A～T，列编号为0～9。按照行优先顺序输入电子表格的各个单元格。每个单元格可能是整数（可能是负数）或者引用了其他单元格的表达式（只包含非负整数、单元格名称和加减号，没有括号）。表达式保证以单元格名称开头，内部不含空白字符，且最多包含75个字符。
尽量计算出所有表达式的值，然后输出各个单元格的值（计算结果保证为绝对值不超过10000的整数）。如果某些单元格循环引用，在表格之后输出（仍按行优先顺序），如图2.32所示。
图2.32
【分析】
基本模型就是各个Cell之间的引用关系形成一个有向图，使用DFS递归求值，同时使用类似拓扑排序中的DFS逻辑来判断是否有循环引用。注意，表达式如果解析构造成树再递归计算，可能导致栈溢出。比较简洁的方法是直接对表达式进行解析，遇到Cell引用就递归计算对应的表达式同时判断循环引用，具体参见相关代码。另外，表达式可能以减号开头，解析时需要注意判断。完整程序如下：
习题6-14 检查员的难题（Inspector’s Dilemma, ACM/ICPC Dhaka 2007, UVa12118）
某国家有V（V≤1000）个城市，每两个城市之间都有一条双向道路直接相连，长度为T。你的任务是找一条最短的道路（起点和终点任意），使得该道路经过E条指定的边。
例如，若V=5、E=3、T=1，指定的3条边为1-2、1-3和4-5，如图2.33所示，则最优道路为3-1-2-4-5，长度为4*1=4。
图2.33
【分析】
首先考虑E条边都连通的情况。如果E条边组成的图存在欧拉道路（不需要是欧拉回路），则这条欧拉道路一定就是满足题目要求的最短道路。否则，记G中的奇度数点个数为P，则一定有P>2，最少需要使其中的P-2个点变成偶数度才能形成欧拉道路，而且题目强调了任意两个点都有一条边，那么可以增加(P-2)/2条边来形成欧拉道路。这样欧拉道路的长度就是“T*(E的边数+(P-2)/2)”。
需要强调的是，这里P一定是偶数，因为对于任意的无向图G，所有点的度数之和等于所有边的端点个数之和。而每条边有两个端点，所有点的度数之和一定是偶数，那么奇度数点的度数之和也必然是偶数。把P-2个奇度数点两两连接起来就能保证存在欧拉道路。
如果E条边不连通，不妨设这E条边形成了n个连通分量G，则需要首先要求每个G内部存在欧拉道路，不存在则参考单个连通分量的情况在G中构造欧拉道路。把每个G的欧拉道路首尾连接起来，至少需要n-1条边。所求答案就是T*（n-1+每个G中的欧拉道路长度之和）。而每个G要形成的欧拉道路长度和单个连通分量的情况类似。
举例来说，图2.33中存在两个连通分量：第一个中有4个奇度数点，不存在欧拉道路；第二个中无奇度数点，存在欧拉道路。则前者需要添加(4-2)/2=1条边（即3-4）形成欧拉道路。然后需要再添加一条边连接两个连通分量中的欧拉道路（即2-7）。问题的解就是7*T。完整程序如下：
