2.2 函数和递归
本节选解习题来源于《算法竞赛入门经典（第2版）》一书的第4章。
习题4-1 象棋（Xiangqi，ACM/ICPC Fuzhou 2011，UVa1589）
考虑一个象棋残局，其中红方有n（2≤n≤7）个棋子，黑方只有一个将。红方除了有一个帅（G）之外还有3种可能的棋子：车（R）、马（H）、炮（C），并且需要考虑蹩马腿（如图2.7所示）和将与帅不能照面（将帅如果同在一条直线上，中间又不隔着任何棋子的情况下，走子的一方获胜）的规则。
输入所有棋子的位置，保证局面合法并且红方已经将军。你的任务是判断红方是否已经把黑方将死。关于中国象棋的相关规则请参见原题。
【分析】
要判断黑方是否必死，其实就是反过来判断黑方是否有种走法，在走出一步之后能不被红方的任何一个棋子将死。首先判断，黑方是不是可以直接将红方将死，如果可以，就无须进行下一步的判断。
然后挨个尝试黑方的各种合法走法（水平或者垂直，但是不能走出黑子的大本营）。如果所有走法都会导致被红方某个棋子吃掉，说明红方必胜。
需要特别注意的是，黑方走子时是可以吃掉红方棋子的，如果有这种情况，需在吃子之后再判断输赢。
从实现过程中来说，有一个公共的过程可以抽取：就是判断一个棋子是否可以从一个点p1直接水平或者垂直地走到另外一个点p2，中间有0个（车要吃子或者黑将直接将军）或者恰好1个棋子（红炮要将军）。实现中，需要将跳马的8个方向封装成向量。
习题4-2 正方形（Squares，ACM/ICPC World Finals 1990，UVa201）
有n行n列（2≤n≤9）的小黑点，还有m条线段连接其中的一些黑点。统计这些线段连成了多少个正方形（每种边长分别统计）。
行从上到下编号为1～n，列从左到右编号为1～n。边用Hij和Vij表示，分别代表边（i，j）-（i，j＋1）和（i，j）-（i＋1，j）。例如图2.8最左边的线段用V11表示。图2.8中包含2个边长为1的正方形和1个边长为2的正方形。
【分析】
对于每一个点（i，j），记录一个向右延伸和向下延伸的最长线段长度hExp和vExp，则二者都可以根据这个点上出发的线段类型来递推：
（1）如果存在向右的线段，则“hExp（i，j）＝hExp（i，j＋1）＋1；”。
（2）如果存在向下的线段，则“vExp（i，j）＝vExp（i＋1，j）＋1；”。
图2.7
图2.8
顺序遍历每一个点P（i，j），依次判断以P为左上顶点的可能正方形的边长s，其中s为1到min（hExp（i，j），vExp（i＋1，j））的整数。然后可以根据s计算出正方形的左下以及右上顶点，再根据这两个点对应的hExp和vExp是否大于等于s，即可判断能否形成长度为s的正方形。完整程序如下：
习题4-3 黑白棋（Othello，ACM/ICPC World Finals 1992，UVa220）
你的任务是模拟黑白棋游戏的进程。黑白棋的规则为：黑白双方轮流放棋子，每次必须让新放的棋子“夹住”至少一枚对方棋子，然后把所有被新放棋子“夹住”的对方棋子替换成己方棋子。一段连续（横、竖或者斜向）的同色棋子被“夹住”的条件是两端都是对方棋子（不能是空位）。图2.9中的白棋有6个合法操作，分别为（2，3），（3，3），（3，5），（6，2），（7，3），（7，4）。选择在（7，3）放白棋后变成图2.10（注意有竖向和斜向的共两枚黑棋变白）。注意（4，6）的黑色棋子虽然被夹住，但不是被新放的棋子夹住，因此不变白。
图2.9
图2.10
输入一个8×8棋盘以及当前下一次操作的游戏者，处理以下3种指令：
- □ L指令打印所有合法操作，按照从上到下、从左到右的顺序排列（没有合法操作时输出No legal move）。
- □ Mrc指令放一枚棋子在（r，c）。如果当前游戏者没有合法操作，则是先切换游戏者再操作。输入保证这个操作是合法的。输出操作完毕后黑白双方的棋子总数。
- □ Q指令退出游戏，并打印当前棋盘（格式同输入）。
【分析】
直接进行模拟即可，需要注意的是，可以将棋子移动的方向预先定义成8个向量，然后使用之前提到过的坐标和向量的运算。
习题4-4 骰子涂色（Cube painting, UVa253）
输入两个骰子，判断二者是否等价。每个骰子用6个字母表示，如图2.11所示。
例如，rbgggr和rggbgr分别表示如图2.12和图2.13所示的两个骰子。二者是等价的，因为如图2.12所示的骰子沿着竖直轴旋转90°之后就可以得到如图2.13所示的骰子。
图2.11
图2.12
图2.13
【分析】
本题可以参考《算法竞赛入门经典—训练指南》中第1章例题8的思路，通过确定顶面和正面的编号来确定所有面的编号，使用程序生成所有面的24种排列。枚举输入的第一个立方体的所有姿态的编码，逐一和第二个骰子的编码比较即可。
习题4-5 IP网络（IP Networks, ACM/ICPC NEERC 2005, UVa1590）
可以用一个网络地址和一个子网掩码描述一个子网（即连续的IP地址范围）。其中，子网掩码包含32个二进制位，前32-n位为1，后n位为0，网络地址的前32-n位任意，后n位为0。所有前32-n位和网络地址相同的IP都属于此网络。
例如，网络地址为194.85.160.176（二进制为11000010|01010101|10100000|10110000），子网掩码为255.255.255.248（二进制为11111111|11111111|11111111|11111000），则该子网的IP地址范围是194.85.160.176～194.85.160.183。输入一些IP地址，求最小的网络（即包含IP地址最少的网络），包含所有这些输入地址。
例如，若输入3个IP地址：194.85.160.177、194.85.160.183和194.85.160.178，包含上述3个地址的最小网络的网络地址为194.85.160.176，子网掩码为255.255.255.248。
【分析】
首先需要将输入的IP地址都转换成二进制表示，然后得到这些二进制数的最长公共前缀P的长度L。则最小网络IP的前L位就是P，剩余的位都是0。子网掩码的前L位都是1，剩余都是0。网络地址从二进制转换到十进制的过程可以提取成公共函数，在输出结果时复用。完整程序如下：
习题4-6 莫尔斯电码（Morse Mismatches, ACM/ICPC World Finals 1997, UVa508）
输入每个字母的Morse编码、一个词典以及若干个编码。对于每个编码，判断它可能是哪个单词。如果有多个单词精确匹配，任选一个输出并且后面加上“!”；如果无法精确匹配，可以在编码尾部增加或删除一些字符以后匹配某个单词（增加或删除的字符应尽量少）。如果有多个单词可以这样匹配上，任选一个输出并且在后面加上“?”。
莫尔斯电码的细节参见原题。
【分析】
输入时，首先建立字符到对应Morse编码的映射map。每输入一个单词，通过这个map将每一个字符翻译成Morse编码，然后建立所有Morse编码到对应单词的映射map<string ,vector<string> > context。
然后对于每一个输入的Morse编码M，首先在context中查找M对应的所有可能的单词v。如果v中只有一个单词，则输出这个单词即可；如果v中包含多个单词，则任意输出一个再加“!”。
如果不存在对应的v，则查找context中所有符合以下条件的Morse编码CM：CM为M的前缀或者M为CM的前缀。找到其中长度和M相差最小的那个CM输出即可。找到的所有CM可以用map<int,string>存放，key为CM和M的大小的差，value就是CM本身。因为map本身就是根据key来排序的，直接输出第一个元素即可。完整程序（C++11）如下：
习题4-7 RAID技术（RAID!, ACM/ICPC World Finals 1997, UVa509）
RAID技术用多个磁盘保存数据。每份数据不止在一个磁盘上保存，因此在某个磁盘损坏时能通过其他磁盘恢复数据。本题讨论其中一种RAID技术。数据被划分成大小为s（1≤s≤64）比特的数据块保存在d（2≤d≤6）个磁盘上。如图2.14所示，每d-1个数据块都有一个校验块，使得每d个数据块的异或结果为全0（偶校验）或者全1（奇校验）。
图2.14
例如d=5，s=2，偶校验，数据6C7A79EDFC（二进制01101100 01111010 01111001 11101101 11111100）将这样保存，如图2.15所示。
图2.15
其中加粗块是校验块。输入d, s, b校验的种类（E表示偶校验，O表示奇校验）以及b（1≤b≤100）个数据块（其中“?”表示损坏的数据），你的任务是恢复并输出完整的数据。如果校验错或者由于损坏数据过多无法恢复，应报告磁盘非法。
提示：
如果没有RAID的知识背景，上述简要翻译可能较难理解，细节建议参考原题。
【分析】
因为输入是按照每个Disk依次进行，所以需要把每个Disk看成行，这个与题图的行列是反过来的，这一点需要注意。
本题的本质就是要对每一列的01数据进行还原，首先是要检查每一列是否有多个未知数据，如果多于1个，则无法还原，磁盘非法。对于全是已知数据的列，所有数据的异或运算结果必须符合校验种类：E时为0，O时为1。如果不符合，表示校验错误。
如果数据全部合法，则按照列的顺序对修复过的数据进行依次组合，注意校验块所在的行是依次循环递增的，在组合时要注意忽略校验块。另外，如果组合后的数据位数不是4的倍数，需要进行补0操作。
在组合的过程中，可以使用bitset来存储每4位的数据结果，bitset.to_ulong()可以方便地把结果转换成整数来输出。注意bitset的第0位是从右边算起，而我们组合时需要从左边算起，需要进行处理。
习题4-8 特别困的学生（Extraordinarily Tired Students, ACM/ICPC Xi’an 2006, UVa12108）
课堂上有n个学生（n≤10）。每个学生都有一个“睡眠-清醒”周期，其中第i个学生醒Ai分钟后睡Bi分钟，然后重复（1≤Ai, Bi≤5），初始时第i个学生处在他的周期的第Ci分钟。每个学生在临睡前会察看全班睡觉人数是否严格大于清醒人数，若是才睡，否则再清醒Ai分钟。问经过多长时间后全班都清醒。如果用（A,B,C）描述学生，图2.16描述了3个学生(2,4,1)、(1,5,2)和(1,4,3)在每个时刻的行为。
图2.16
注意：
有可能并不存在“全部都清醒”的时刻，此时应输出-1。
【分析】
可以用一个循环来模拟每分钟的行为，首先看看是否还有睡着的，如果没有，直接输出结果即可，然后依次判断每个学生的行为并且进行模拟。
问题是整体状态有可能进入死循环，为了避免这种情况，可以将每个学生的状态放在一起编码成字符串，然后使用set判重，如果发现重复，说明不会再清醒了，输出-1即可。完整程序如下：
习题4-9 数据挖掘（Data Mining, ACM/ICPC NEERC 2003, UVa1591）
有两个n元素数组P和Q。P数组每个元素占SP个字节，Q数组每个元素占SQ个字节。有时需直接根据P数组中某个元素P(i)的偏移量Pofs(i)算出对应的Q(i)的偏移量Qofs(i)。当两个数组的元素均为连续存储时Qofs(i)=Pofs(i)/Sp*Sq，但因为除法慢，可以把式子改写成速度较快的Qofs'(i)=(Pofs(i)+Pofs(i)<<A)>>B。为了让这个式子成立，在P数组仍然连续存储的前提下，Q数组可以不连续存储（但不同数组元素的存储空间不能重叠）。这样做虽然会浪费一些空间，但是提升了速度，是一种用空间换时间的方法。
输入N、SP和SQ（N≤220，1≤SP, SQ≤210），你的任务是找到最优的A和B，使得占的空间K尽量小。输出K、A、B的值。多解时让A尽量小，如果仍多解则让B尽量小。
提示：
本题有一定实际意义，不过描述比较抽象。如果对本题兴趣不大，可以先跳过。
【分析】
注意是对32位整数进行位移操作，那么A和B必然是0～31的整数。所有的A、B组合就只有32*32个，完全可以使用暴力方式遍历求解。
另外，Q的不同元素不可以重叠，这就要求Qofs'(i)>i*Sq。只需考虑i=1的情况就可以确定Q中一个元素的存储空间，也就是说要求Qofs'(1)=(Sp+Sp<<A)>>B≥Sq，找到一组符合要求的A、B之后即可得：K=Qn-1+Sq=(Sp*(n-1)+(Sp*(n-1))<<A)>>B+Sq。这里Q的最后一个元素之后不需要多余的存储空间。
从小到大遍历A和B，发现更小的K时更新答案，即可得到题目要求的解。
习题4-10 洪水！（Flooded! ACM/ICPC World Finals 1999, UVa815）
有一个n*m（1≤m, n<30）的网格，每个格子是边长10米的正方形，网格四周是无限大的墙壁。输入每个格子的海拔高度，以及网格内雨水的总体积v，输出水位的海拔高度以及有多少百分比的区域有水（即高度严格小于水平面）。
【分析】
原题保证了水会从海拔最低的格子开始淹，然后依次上升。可以把所有n*m个格子按照海拔从低到高排列，编号从0开始计。从i=1到n*m，依次计算，如果体积为v的水把编号0～i-1的每个格子都淹没所形成的水位高度wl，如果wl<格子i的高度，则说明水无法淹没格子i。这样就得到了水位高度wl和有水的格子个数i，求百分比即可。因为格子边长是10，可以将v除以100，然后把格子边长作为1来处理，这样每个格子底面积就为1，方便计算。完整程序如下：
