第2章　 《算法竞赛入门经典（第2版）》习题选解

2.1　数组和字符串

本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第3章。

习题3-1　得分（Score，ACM/ICPC Seoul 2005，UVa1585）

给出一个由O和X组成的串（长度为1～80），统计每个字符的得分之和。每个O的得分为已经连续出现的O的个数，X得分为0。例如，OOXXOXXOOO的得分为1＋2＋0＋0＋1＋0＋0＋1＋2＋3。

【分析】

使用for循环对输入串的字符进行遍历，维护一个已经连续出现的‘O‘个数的计数器cnt以及串的得分和sum。初始cnt＝0，sum＝0。如果遇到‘O‘就＋＋cnt，然后把cnt加到sum中，如果遇到‘X‘就重置cnt为0。

完整程序（C＋＋11）如下：

习题3-2　分子量（Molar Mass，ACM/ICPC Seoul 2007，UVa1586）

给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分别为C、H、O、N，原子量分别为12.01、1.008、16.00、14.01（单位：g/mol）。例如，C6H5OH的分子量为6×（12.01g/mol）＋6×（1.008g/mol）＋1×（16.00 g/mol）＝94.108g/mol。

【分析】

依次扫描即可，注意原子后面不带数目的情况。扫描的过程中，维护一个当前已经输入的数字字符组成的数字cnt。一开始以及遇到一个新原子时，cnt＝-1，表示“还未开始计数”的状态。方便遇到原子后不带数目以及数字有多位的情况处理。

和习题3-1类似，也要在循环结束之后处理最后一个原子。完整程序如下：

习题3-3　数数字（Digit Counting，ACM/ICPC Danang 2007，UVa1225）

把前n（n≤10000）个整数按顺序写在一起：123456789101112…数一数0～9各出现多少次（输出10个整数，分别是0，1，…，9出现的次数）。

【分析】

因为n的最大值比较小，可以用建表的方式来计算。令C［n］［k］表示前n个数字写在一起，k（k＝0～9）总共出现几次，则有C［n＋1］［k］＝C［n］［k］＋x，其中x是k在n中出现的次数。直接按照这个公式就可以把所有答案提前计算出来，然后每读入一个n就直接输出预处理的结果即可。

习题3-4　周期串（Periodic Strings，UVa455）

如果一个字符串可以由某个长度为k的字符串重复多次得到，就可以说该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。

输入一个长度不超过80的字符串，输出它的最小周期。

【分析】

字符串的周期p只可能是闭区间［1，k］内能被k整除的数，然后从小到大遍历所有的p，看看对于每个i＝0～k-1是否符合S［i］＝S［i%C］，找到第一个全部符合的p就是所求结果。完整程序如下：

习题3-5　谜题（Puzzle，ACM/ICPC World Finals 1993，UVa227）

有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A、B、L、R，分别表示把空格上／下／左／右的相邻字母移到空格中。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration．”，例如图2.1执行ARRBBL0后为图2.2。

【分析】

使用以下结构表示坐标和向量：

然后直接模拟即可，可以将4种指令字符以及对应4个方向的向量存放到一个map＜char，Vector＞中，方便移动时计算新的空格位置。

完整程序如下：

习题3-6　纵横字谜的答案（Crossword Answers，ACM/ICPC World Finals 1994，UVa232）

输入一个r行c列（1≤r，c≤10）的网格，黑格用“*”表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。

首先把所有起始格按照从上到下、从左到右的顺序编号为1、2、3、…，如图2.3所示。接下来要找出所有横向单词（Across），这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down），这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。输入输出格式和样例请参考原题。

【分析】

还是和习题3-5一样，建立坐标和向量的结构方便进行位置的移动处理。依次扫描，用一个全局的Point数组eligible存放所有单词的起始点坐标，同时要用两个vector＜int＞，即across和down来分别记录扫描出的横向单词和竖向单词的起点坐标在eligible中的编号。

在读取两个方向单词时，使用两个向量计算来读取所有的单词，即dRight（0，1）和dDown（1，0），这样可以降低代码复杂度。具体请参见代码，完整程序如下：

习题3-7　DNA序列（DNA Consensus String，ACM/ICPC Seoul 2006，UVa1368）

输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长字符串的Hamming距离等于字符不同的位置个数，如ACGT和GCGA的Hamming距离为2（左数第1、4个字符不同）。

输入整数m和n（4≤m≤50，4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A、C、G、T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT

【分析】

对于所求结果序列S来说，Hamming距离和最小意味着S中每一列的字符都在m个序列的对应列上出现次数最多。可以依次对m个序列中每一列的字符进行统计，字典序最小并且出现次数最多的那个就是S中这一列的字符。完整程序如下：

习题3-8　循环小数（Repeating Decimals，ACM/ICPC World Finals 1990，UVa202）

输入整数a和b（0≤a≤3000，1≤b≤3000），输出a/b的循环小数表示以及其循环节长度。例如a＝5，b＝43，小数表示为0．（116279069767441860465），循环节长度为21。

【分析】

首先简单介绍一下长除法，以3/7为例，如图2.4所示。

本题实际上就是模拟长除法的计算过程，其中每一次除法时都有被除数和余数，当被除数出现重复时就表示出现循环节了。所以需要记录每一次的被除数及其在循环小数中的位置，需要注意当除数不够除，每一次补零也需要记录其对应的位置。

完整程序如下：

习题3-9　子序列（All in All，UVa10340）

输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他字符顺序不变），得到字符串s。例如，abcde可以得到bce，但无法得到dc。

【分析】

可以使用两个变量i和j对两个字符串s和t同时进行遍历，对于每个i，如果t［j］！＝s［i］，那么一直对j进行递增操作，如果j越界，说明t［j…］中不存在等于s［i］的字符，查找失败。如果对于每个i匹配成功，则说明问题有解，否则无法从t中删除字符得到s。完整程序如下：

习题3-10　盒子（Box，ACM/ICPC NEERC 2004，UVa1587）

给定6个矩形的长和宽w_i和h_i（1≤w_i，h_i≤1000），判断它们能否构成长方体的6个面。

【分析】

注意长方体的6个面一定是可以形成3对相同的矩形，并且边的长度刚好只有3个。对输入的矩形的长宽进行处理，使得长x≥宽y。输入完按照先x后y对输入的矩形进行排序。排序完成之后，如果输入合法，应该就是3对矩形，每一对都应该完全一致；否则非法。

记排完序的矩形为rects［6］，则长方体的3条边就是rects［0］．x、rects［4］．x、rects［5］．y，此时就可以按照这3个边长，把6个矩形重新构造出来，与输入数据比对。如果相同，说明合法，否则非法。

习题3-11　换低档装置（Kickdown，ACM/ICPC NEERC 2006，UVa1588）

给出两个长度分别为n₁、n₂（n₁，n₂≤100）且每列高度只为1或2的长条，需要将它们放入一个高度为3的容器（如图2.5所示），问能够容纳它们的最短容器长度。

【分析】

数据范围比较小，可以直接遍历上方长条的所有位置，看看能不能和下方匹配即可。可以引入一维坐标，其中下方的长条起始点放在100，依次遍历上方长条所有可能的起始点b2，b2的可能范围是［100-n₁, 100＋n₁＋n₂］。对于一个起始点b2，依次尝试放置序列的每一个点，看看数轴上对应点的两个长条对应列的高度和是否大于3，如果大于3，说明放不到容器里面；否则继续。这样用O（n₁*n₂）的时间复杂度就可以求出最短的容器长度。

习题3-12　浮点数（Floating-Point Numbers，UVa11809）

计算机常用阶码－尾数的方法保存浮点数。如图2.6所示，如果阶码有6位，尾数有8位，可以表达的最大浮点数为。注意小数点后第一位必须为1，所以一共有9位小数。

这个数换算成十进制之后就是0.998046875*2⁶³＝9.205357638345294*10¹⁸。你的任务是根据这个最大浮点数，求出阶码的位数E和尾数的位数M。输入格式为AeB，表示最大浮点数为A*10^B，0＜A＜10，并且恰好包含15位有效数字。输入结束标志为0e0。对于每组数据，输出M和E。输入保证有唯一解，且0≤M≤9，1≤E≤30。在本题中，M＋E＋2不必为8的整数倍。

【分析】

根据题意可以推算出最大值。因为两边都比较大，所以可以同时求以10为底的对数：。

可以遍历所有可能的M，根据上述公式求出E的值，然后再用E和M求出lgv和输入的值进行比较，如果相等，说明M、E就是所求的值。做两个浮点数相等判断时，二者之差的绝对值如果小于1e-6，则认为二者相等。完整程序（C＋＋11）如下：

注意，本题代码使用了C＋＋11中提供的round函数（属于C语言的math标准库）来做四舍五入操作，不再需要使用类似floor（x＋0.5）这样的技巧。

浮点数在计算机科学中是非常重要的课题，有兴趣的读者可以参考如下链接：http://share.onlinesjtu.com/mod/tab/view.php?id=176。