1.3 相关题库
【1.3.1 Perfection】
【问题描述】
1994年Microsoft Encarta的数论论文：“如果a，b，c是整数，且a=bc，那么a称为b或c的一个倍数，a和b或c称为a的一个约数或因数。如果c不是1/-1，则b称为一个真约数（proper divisor）。偶整数包括0，是2的倍数，例如，-4，0，2，10。奇数是非偶的整数，例如，-5，1，3，9。一个完全数（perfect number）是正整数，等于其所有的正的真约数的总和，例如，6等于1+2+3，28等于1+2+4+7+14，6和28就是完全数。一个不是完全数的正整数称为不完全数，并且根据其所有的正的真约数的总和小于或大于该数，被称为是不足的（deficient）或充裕的（abundant）。因此，9（真约数1，3）是不足的，而12（真约数1，2，3，4，6）是充裕的。”
给出一个数字，确定它是完全的、充裕的还是不足的。
输入:
一个由N个正整数组成的列表（不大于60000），1≤N<100。一个0标识列表结束。
输出：
第一行输出“PERFECTION OUTPUT”，接下来的N行对每个输入整数输出其是完全的、充裕的还是不足的，见如下样例。具体格式为：在输出行前5位相应的整数向右对齐，然后给出两个空格，接下来是对整数的描述。最后一行输出“END OF OUTPUT”。
试题来源：ACM Mid-Atlantic 1996
在线测试地址：POJ 1528，ZOJ 1284，UVA 382
提示
首先计算出当前整数的所有真约数，然后判断真约数的总和是大于、小于还是等于给出的数字：
若给出的数字>真约数的总和，则是充裕的（输出DEFICIENT）。
若给出的数字<真约数的总和，则是不足的（输出ABUNDANT）。
若给出的数字==真约数的总和，则是完全的（输出PERFECT）。
【1.3.2 Uniform Generator】
【问题描述】
计算机模拟通常需要随机数。产生伪随机数的方法之一是通过如下形式的函数：seed(x+1)=［seed(x)+STEP］%MOD其中“%”是取模操作符。
这样的函数将产生介于0和MOD-1之间的伪随机数（seed）。这种形式的函数的一个问题是，它们将一遍又一遍地生成相同的模式。为了尽量减少这种影响，就要仔细选择STEP和MOD的值，使得所有的值在0和MOD-1之间（包含0和MOD-1）均匀分布。
例如，如果STEP=3，MOD=5，函数将重复循环产生伪随机数序列0,3,1,4,2。在本实例中，在0和MOD-1之间（包含0和MOD-1）的所有数字由函数的每次MOD迭代产生。这里要注意，由产生相同的seed(x+1)函数的特性，每次seed(x)出现意味着如果一个函数产生所有在0和MOD-1之间的值，通过每次MOD迭代均匀产生伪随机数。
如果STEP=15，MOD=20，函数产生序列0,15,10,5（如果初始的伪随机数不是0，就产生其他的循环序列）。这是一个STEP和MOD的糟糕的选择，因为不存在初始的伪随机数能产生从0到MOD-1的所有值。
你的程序要确定选择的STEP和MOD的值是否能产生伪随机数的均匀分布。
输入：
输入的每一行给出一个整数的有序对STEP和MOD(1≤STEP,MOD≤100000)。
输出：
对于输入的每一行，从第1列到第10列向右对齐输出STEP的值，从第11列到第20列向右对齐输出MOD的值，从第25列开始向左对齐输出“Good Choice”或“Bad Choice”。如果选择的STEP和MOD的值在MOD个值产生的时候，能产生在0和MOD-1之间的所有值，则输出“Good Choice”；否则输出“Bad Choice”。在每个测试用例输出后，程序要输出一个空行。
试题来源：ACM South Central USA 1996
在线测试地址：POJ 1597，ZOJ 1314，UVA 408
提示
我们按照如下方法确定伪随机数是否为均匀分布。设seedi为第i次产生的伪随机数。按照题意，伪随机数产生的函数为seedi+1=（seedi+step）%MOD从seed0出发，连续迭代上述函数MOD-1次：如果产生的MOD-1个伪随机数为［1‥MOD-1］，则产生的伪随机数是均匀分布的；否则为非均匀分布的。
【1.3.3 WERTYU】
【问题描述】
一种常见的打字错误是将手放在键盘上正确位置的一行的右边。因此，将“Q”输入为“W”，将“J”输入为“K”，等等。请对以这种方式键入的消息进行解码。
输入：
输入包含若干行文本。每一行包含数字、空格、大写字母（除Q、A、Z外），或者如图1.3-1中所示的（除了倒引号(')）。用单词标记的键（Tab、BackSp、Control，等等）不在输入中。
输出：
对于输入的每个字母或标点符号，用图1.3-1所示的QWERTY键盘上左边的键的内容来替代。输入中的空格也显示在输出中。
试题来源：Waterloo local 2001.01.27
在线测试地址：POJ 2538，ZOJ 1884，UVA 10082
提示
先根据图片中的键盘，离线计算转换表，存储每个键字对应的左侧键（注：根据题意，单词键（Tab键、BackSp键、Control键等）及每一行在最左边的键（Q、A、Z）不在转换表中。此外所有字母都是大写的）。以后每输入一个字母或标点符号，直接输出转换表中对应的左侧键。
【1.3.4 Soundex】
【问题描述】
Soundex编码是将基于它们的拼写听起来相同的单词归类在一起。例如，“can”和“khawn”，“con”和“gone”在Soundex编码下是等价的。
Soundex编码涉及将每个单词转换成一连串的数字，其中每个数字代表一个字母：
1表示B、F、P或V
2表示C、G、J、K、Q、S、X或Z
3表示D或T
4表示L
5表示M或N
6表示R
字母A、E、I、O、U、H、W和Y在Soundex编码中不被表示，并且如果存在连续的字母，这些字母是用相同的数字表示的，那么这些字母就仅用一个数字来表示。具有相同Soundex编码的单词被认为是相等的。
输入：
输入的每一行给出一个单词，全大写，少于20个字母长。
输出：
对每行输入，输出一行，给出Soundex编码。
试题来源：Waterloo local 1999.09.25
在线测试地址：POJ 2608，ZOJ 1858，UVA 10260
提示
由左至右将单词的每个字母转化为对应数字并略去重复数字，即可得到单词的Soundex编码。
【1.3.5 Mine Sweeper】
【问题描述】
扫雷游戏（Minesweeper）是一个在n×n的网格上玩的游戏。在网格中隐藏了m枚地雷，每一枚地雷在网格上不同的方格中。玩家不断点击网格上的方格。如果有地雷的方格被触发，则地雷爆炸，玩家就输掉了游戏；如果一个没有地雷的方格被触发了，就出现0到8之间的整数，表示包含地雷的相邻方格和对角相邻方格的数目。图1.3-2给出玩该游戏的部分连续的截图。
在这里，n为8，m为10，空白方格表示整数0，凸起的方格表示该方格还未被触发，类似星号的图像则代表地雷。图1.3-2中最左边的图表示这个游戏开始玩了一会儿的情况。从第一张图片到第二张图片，玩家点击了两个方格，每次玩家选择一个安全的方格。从第二张图片到第三张图片，玩家就没有那么幸运了，他选择了一个有地雷的方格，因此游戏输了。如果玩家继续触发安全的方格，直到只有m个包含地雷的方格没有被触发，则玩家获胜。
请编写一个程序，输入游戏进行的信息，输出相应的网格。
输入：
输入的第一行给出一个正整数n≤10。接下来的n行描述地雷的位置，每行用n个字符表示一行的内容：句号表示一个方格没有地雷，而星号代表这个方格有地雷。然后的n行每行给出n个字符：被触发的位置用x标识，未被触发的位置用句号标识，样例输入相应于上面中间的图。
输出：
输出给出网格，每个方格被填入适当的值。如果被触发的方格没有地雷，则给出从0到8之间的值；如果有一枚地雷被触发，则所有有地雷的方格位置都用一个星号标识。所有其他的方格用一个句号标识。
试题来源：Waterloo local 1999.10.02
在线测试地址：POJ 2612，ZOJ 1862，UVA 10279
提示
试题给出了地雷矩阵g［i］［j］和触发情况矩阵try［i］［j］（1≤i,j≤n），要求计算和输出网格。
【1.3.6 Tic Tac Toe】
【问题描述】
三连棋游戏（Tic Tac Toe）是在3×3的网格上玩的一个少儿游戏。一个玩家X开始将一个X放置在一个未被占据的网格位置上，然后另外一个玩家O则将一个O放置在一个未被占据的网格位置上。X和O就这样被交替地放置，直到所有的网格被占满，或者有一个玩家的符号在网格中占据了一整行（垂直、水平或对角）。
请编写一个程序，输入网格，确定其是否是有效的三连棋游戏的一个步骤。也就是说，通过一系列的步骤可以在游戏的开始到结束之间产生这一网格吗？
输入：
输入的第一行给出N，表示测试用例的数目。然后给出4N-1行，说明N个用空行分隔的网格图。
输出：
对于每个测试用例，在一行中输出"yes"或"no"，表示该网格图是否是有效的三连棋游戏的一个步骤。
试题来源：Waterloo local 2002.09.21
在线测试地址：POJ 2361，ZOJ 1908，UVA 10363
提示
由于X先走且轮流执子，因此网格图为有效的三连棋游戏的一个步骤，一定同时呈现下述特征：
1）O的数目一定小于等于X的数目。
2）如果X的数目比O多1个，那么不可能是O赢了三连棋。
3）如果X的数目和O的数目相等，则不可能是X赢了三连棋。
也就是说，网格图为无效的三连棋游戏的一个步骤，至少呈现下述5个特征之一：
1）O的个数大于X的个数。
2）X的个数至少比O的个数多2。
3）已经判出O方和X方同时赢。
4）已经判出O方赢但O的个数与X的个数不等。
5）已经判出X方赢但双方棋子个数相同。
否则网格图为有效的三连棋游戏的一个步骤。
【1.3.7 Rock,Scissors,Paper】
【问题描述】
Bart的妹妹Lisa发明了一个在二维网格上玩的新游戏。在游戏开始的时候，每个网格可以被三种生命形式——石头（Rocks）、剪刀（Scissors）、布（Papers）中的一种所占据。每一天，在水平或垂直相邻的网格之间，不同的生活形式就要引起战争。而在每一场战争中，石头击败剪刀，剪刀击败布，布击败石头。在一天结束的时候，胜利者扩大其领土范围，占领了失败者的网格；而失败者则让出位置。
请编写一个程序，确定n天之后每种生命形式所占领的领土。
输入：
输入的第一行给出t，表示测试用例的数目。每个测试用例首先给出不大于100的3个整数：分别表示网格中行和列的数目的r和c，以及天数n。接下来，网格用r行表示，每行c个字符，在网格中每个字符为R、S或P，分别表示石头（Rocks）、剪刀（Scissors）、布（Papers）。
输出：
对于每个测试用例，输出在第n天结束的时候网格的情形。在连续的测试用例之间，输出一个空行。
试题来源：Waterloo local 2003.01.25
在线测试地址：POJ 2339，ZOJ 1921，UVA 10443
提示
由于每个位置在一天结束的时候要改变，因此可引用两个矩阵：一个表示昨天，一个表示今天。今天矩阵是在昨天矩阵的基础上计算产生的，昨天矩阵和今天矩阵的对应元素反映了这一天该位置的变化情况：
一个'R'变成'P'当且仅当'R'有一个'P'相邻，即昨天矩阵中'R'的相邻格为'P'，则今天矩阵中'P'的位置填'R'。
一个'S'变成'R'当且仅当'S'有一个'R'相邻，即昨天矩阵中'S'的相邻格为'R'，则今天矩阵中'R'的位置填'S'。
一个'P'可以变成'S'当且仅当'P'有一个'S'相邻，即昨天矩阵中'P'的相邻格为'S'，则今天矩阵中'S'的位置填'P'。
例如：
按照上述规则计算rc个格子，得出了这一天的变化结果。显然从初始矩阵出发，按上述规则依次进行n次矩形计算，便可得出n天结束时的网格。
【1.3.8 Prerequisites?】
【问题描述】
大学一年级学生Freddie选修k门课程。为了符合获得学位的要求，他必须从几个类别中选修课程。你来判断Freddie所选修的这些课程是否符合学位要求。
输入:
输入由若干测试用例组成。对于每个测试用例，输入的第一行包含k（1≤k≤100），表示Freddie选择的课程数；以及m（0≤m≤100），表示选修课程的类别数。接下来给出包含k个4位整数的一行或多行，分别表示Freddie选修课程的编号。每个类别用一行表示，包含c（1≤c≤100），表示在该类别中课程的数量；r（0≤r≤c），表示该类课程必须修的最低数量；以及在该类别中c门课程的编号。每门课程的编号是一个4位整数。相同的课程可以在若干个类别中。Freddie选修的课程的编号，以及在每个类别中的课程编号，当然都是不同的。在最后的测试用例后，给出包含0的一行。
输出：
对于每个测试用例，如果Freddie的课程选修符合获得学位的要求，则输出一行"yes"；否则输出"no"。
试题来源：Waterloo local 2005.09.24
在线测试地址：POJ 2664，UVA 10919
提示
设第i类选修课程的课程数为ci，这些课程组成集合donei，必须修的最低课程数为ri，(1≤i≤m)。
首先将Freddie选中的k门课程放入集合take［］。
然后依次分析Freddie选中的每类选修课程:
对于其中第i类选修课程来说，若ri≤take［］∩donei，则说明被Freddie选中的课程数超过了最低标准，设可选标志yesi=true。
最后分析Freddie选中的m类选修课程：若∩1≤i≤m{yesi}==true，则Freddie的课程选修符合获得学位的要求；否则不符合要求。
【1.3.9 Save Hridoy】
【问题描述】
如果横幅配上了优美的语句，就可以激励我们大家，这也是伟大的。那么，我们制作大横幅，将优美的语句写在上面，可以使得这个世界更美丽。带着我们的良好愿望，我们今天要制作这样的一条横幅——一条挽救一个生命的横幅，一条拯救人类的横幅。
本题的程序产生包含文字“SAVE HRIDOY”的横幅。我们将用不同的字体大小以及水平和垂直两种可能的方向来制作这面横幅。正如我们用普通的单色文字制作大小不同的横幅一样，我们将使用两种不同的ASCII字符表示黑色和白色的像素。在这个过程中最小可能的横幅（字体大小为1）水平方向的文字如图1.3-4所示。
黑色像素用“*”字符标识，白色像素用“.”字符标识。在这面横幅上，每个字符用5×5网格表示，一个单词中的两个连续的字符之间由一条垂直的虚线分隔，两个单词之间由三条垂直的虚线分隔。垂直横幅（字体大小为1）的情况下，在一个单词的两个连续字母之间用一条水平虚线分开，两个单词之间用三条水平虚线分开。见第二个样例输入/输出就可以知道垂直横幅是如何形成的。对于字体大小为2的横幅，每个像素用2×2的像素网格表示。所以实际上一个字体大小为2的横幅的宽度和高度是字体大小为1的横幅的两倍。
输入：
输入至多30行，每行给出一个整数N(0输出：
如果N是正整数，那么就要画一个水平方向的横幅；如果N是负整数，那么就要画一个垂直方向的横幅。这两类情况的输出的详尽描述如下：
如果N是正整数，那么就输出5N行。这些行实际就画出水平的横幅。一个单词中的两个连续的字母之间用N个垂直点的虚线分开；两个单词之间用3N个垂直点的虚线分开。
如果N是负数，则输出5L10+11L行，其中L是N的绝对值。在一个单词中两个连续的字符用L个点水平虚线分开；两个单词之间用3L个点水平虚线分开。
在每个测试用例输出后，输出两个空行。
【1.3.10 Find the Telephone】
【问题描述】
在一些场所，将一个电话号码的数字与字母关联，记住电话号码是很常见的。以这种方式，短语MY LOVE就表示695683。当然也存在一些问题，因为有些电话号码不能构成一个单词或词组，1和0没有与任何字母关联。
请编写一个程序，输入短语，并根据下表找到对应的电话号码。一个短语由大写字母（A～Z）、连字符（-）以及数字1和0组成。
输入：
输入由一个短语的集合组成。每个短语一行，有C个字符，其中1≤C≤30。输入以EOF结束。
输出：
对每个短语，输出相应的电话号码。
试题来源：UFRN-2005 Contest 1
在线测试地址：UVA 10921
提示
由左至右分析短语中的每个字符：若为连字符或1或0，则原样输出；否则严格按照题目给出的字母与数字的转换表输出字母对应的数字。
【1.3.11 2 the 9s】
【问题描述】
有一个大家所熟知的技巧，如果一个整数N是9的倍数，就来计算其每位数字的总和S；如果S是9的倍数，那么N也是9的倍数，这是一个递归的测试，基于N的递归深度称为N的9度（9-degree of N）。
给出一个正整数N，确定其是否是9的倍数；如果是，给出其9度。
输入：
输入的每行包含一个正数。给出数字0的一行表示输入结束。给出的数字最多可包含1000位。
输出：
对于每个输入的数，指出是否是9的倍数；如果是9的倍数，则给出其9度的值。见样例输出。
试题来源：UFRN-2005 Contest 1
在线测试地址：UVA 10922
提示
使用统计分析法分析两个简单的案例：
1）n=999999999999999999999。
递归第1层：999999999999999999999共21位，21位数字的总和为9×21=189。
递归第2层：189的3位数字的总和为1+8+9=18。
递归第3层：18的2位数字和为9，正好为9，递归结束。
由此得出999999999999999999999为9的倍数，其9度的值为3。
2）n=9999999999999999999999999999998。
递归第1层：9999999999999999999999999999998共31位，31位数字的总和为30×9+8=278。
递归第2层：278的3位数字的总和为2+7+8=17。
递归第3层：17的2位数字的总和为1+7=8。8为一位数，非9的倍数，递归结束。
由此得出9999999999999999999999999999998非9的倍数。
由上可以看出，尽管确定N是否为9的倍数的方法是递归定义的，但没必要编写对应的递归程序，迭代式地统计当前数的各位数的和（若非首次迭代的话，当前数即为上次迭代时各位数的和）。实际上，每次迭代并不需要判断当前数是否为9的倍数，只是看最后产生的一位数是否为9：如果是，则n为9的倍数，迭代次数即为其9度的值；否则n非9的倍数。
【1.3.12 You can say 11】
【问题描述】
给出正整数N，确定其是否是11的倍数。
输入：
输入的每行包含一个正整数，以包含0的一行为输入结束标志。给出的数字可以多达1000位。
输出：
对于输入的每个数，指出是否是11的倍数。
试题来源：UFRN-2005 Contest 2
在线测试地址：UVA 10929
提示
方法1：递推。
显然S=K，即奇数位和偶数位的数和相同。
以上并没有考虑进位。如果有进位，设有m1个偶数位和m2个奇数位有进位（m1+m2≤n）。m1个偶数位的进位分别加入了m1个奇数位，其结果是，偶数位的数和减了10m1、奇数位的数和加了1m1，这样奇数位数和与偶数位数和的差就减少了11m1；m2个奇数位的进位分别加入了m2个偶数位，使得奇数位的数和减了10m2、偶数位的数和加了1m2，最终使得奇数位数和与偶数位数和的差增加了11m2。由此得到结论：A的奇数位数和与偶数位数和的差是11的倍数（包括0）。
在这个结论的基础上引出奇偶位差法：
从右至左，分别将奇数位的数字和偶数位的数字加起来，再求它们的差。如果这个差是11的倍数（包括0），即∑l2i=0a2i-∑l2i=1a2i-1=11*k，则A一定能被11整除。
【1.3.13 Parity】
【问题描述】
我们定义一个整数n的奇偶性为该数的二进制表示的每位数的总和对2取模。例如，整数21=101012在其二进制表示中有3个1，因此其奇偶性为3(mod2)，也就是1。
本题要求计算一个整数1≤I≤2147483647的奇偶性。
输入：
输入的每行给出一个整数I，输入以I=0结束，程序不用处理这一情况。
输出：
对于输入中的每个整数I，输出一行“The parity of B is P(mod 2).”，其中B是I的二进制表示。
试题来源：UFRN-2005 Contest 2
在线测试地址：UVA 10931
提示
在十进制转化为二进制的过程中顺便记录1的个数。
【1.3.14 Not That Kind of Graph】
【问题描述】
请编写程序，用图表表示一个股票随着时间而变化的价格。在一个单位时间内，股票可以涨（Rise）、跌（Fall）或持平（Constant）。将你的股票价格用‘R’、‘F’和‘C’的一个字符串表示，请用图表表示，使用字符'/'(斜线)、'＼'(反斜线)和'_'(下划线)。
输入:
输入的第一行给出测试用例的数目N，接下来给出N个测试用例。每个测试用例包含一个字符串，至少1个，至多50个大写字符（R、F或C）。
输出：
对每个测试用例，输出一行"Case #x:"，其中x是测试用例的编号。然后输出图表，如样例输出所示，包含x轴和y轴。x轴比图表长一个字符，在y轴和起始图表之间有个空格。在任何行都没有后续的空格，不要输出不必要的行。x轴总是出现在图表下方。在每个测试用例结束的时候，输出一个空行。
试题来源：Abednego's Graph Lovers' Contest,2005
在线测试地址：UVA 10800
提示
输入一个字符串，每个字符为R(Rise)、C(Constant)或F(Fall)，要求画出相应的图表。
我们采用一个二维字符矩阵存储图表。在输入字符串的过程中边将字母转换为相应的线条字符，边调整整个图表的上下界。
输出字符矩阵按自上而下的顺序进行，在输出当前行前，先统计出当前行的实际列宽，然后在列宽范围内输出该行的图表信息。
【1.3.15 Decode the tape】
【问题描述】
你的老板刚刚发掘出一卷旧的计算机磁带，磁带上有破洞，磁带可能包含一些有用的信息。请弄清楚磁带上写了些什么。
输入：
输入给出一卷磁带的内容。
输出：
输出在磁带上写的信息。
（续）
试题来源：Abednego’s Mathy Contest 2005
在线测试地址：UVA 10878
提示
由输入样例可以看出，计算机磁带每行为10个信息单元a0‥a9，其中a0为开始标志'|'，a6为空格，其他位置空格表示数字0，‘o’表示数字1，即i位置为‘o’，代表整数ai=29-i7≤i≤9
28-i2≤i≤5。一行的信息为一个字符的ASCII码，对应的字符即为磁带该行的内容。
【1.3.16 Fractions Again?!】
【问题描述】
对每个形式为1k(k>0)的分数,可以找到两个正整数x和y，x≥y,使得1k=1x+1y本题的问题是，对于给出的k，有多少这样的x和y对？
输入：
输入不超过100行，每行给出一个k的值(0输出：
对每个k，输出相应(x,y)对的数量，然后输出x和y的值的排序列表，如样例输出所示。
试题来源：Return of the Newbies 2005
在线测试地址：UVA 10976
提示
给出k的值，求出等式1k=1x+1y的所有正整数的解［x，y］（x≥y）。显然，任何y的有效值在k+1和2k之间，包含k+1和2k。对所有可能的y的值进行循环，每次检查是否相应的x是一个整数，即
【1.3.17 Factorial!You Must be Kidding!!!】
【问题描述】
Arif在Bongobazar买了台超级电脑。Bongobazar是达卡（Dhaka）的二手货市场，因此他买的这台超级电脑也是二手货，存在一些问题。其中的一个问题是这台电脑的C/C++编译器的无符号长整数的范围已经被改变了。现在新的下限是10000，上限是6227020800。Arif用C/C++写了一个程序，确定一个整数的阶乘。整数的阶乘递归定义为：Factorial(0)=1
Factorial(n)=nFactorial(n-1)当然，可以改变这样的表达式，例如，可以写成：Factorial(n)=n(n-1)*Factorial(n-2)这一定义也可以转换为迭代的形式。
但Arif知道，在这台超级电脑上，这一程序不可能正确地运行。请编写一个程序，模拟在正常的计算机上的改变行为。
输入:
输入包含若干行，每行给出一个整数n。不会有整数超过6位。输入以EOF结束。
输出：
对于每一行的输入，输出一行。如果n!的值在Arif的计算机的无符号长整数范围内，输出行给出n!的值；否则输出行给出如下两行之一：
试题来源：GWCF Contest 4-The Decider
在线测试地址：UVA 10323
提示
根据题意，如果n!值大于6227020800，输出"Overflow!"；如果n!值小于10000，输出"Underflow!"。显然，正整数n只有在8～13之间才能输出。但问题是，本题没有限制n的正负。如果n是负数，则n!的值不可能在Arif的计算机的无符号长整数范围内。但究竟是上溢还是下溢，还需要做进一步区分：
伽玛函数（gamma function）作为阶乘的推广，是定义在复数范围内的亚纯函数，通常写成Γ(x)=∫+∞0e-t*tx-1dt=limn→∞n!nxx(x+1)…(x+n)。
利用分部积分法，可以得到Γ(x)=(x-1)*Γ(x-1)。容易计算得出初始解Γ(1)=1。由此递推，可得到这样一个结论：当函数的自变量是正整数时，函数值就是前一个整数的阶乘，即Γ(n+1)=n!。按照题意，若n>13，则上溢；若n<8，则下溢。
当函数的自变量n为负数时，则需根据n的奇偶性确定溢出性质：
若n为偶数,则计算Γ(n)需进行奇数次负数连乘，结果趋向-∞，即出现下溢。
若n为奇数，则计算Γ(n)需进行偶数次负数连乘，结果趋向∞，即出现上溢。
由此得出算法：
先离线计算出f［i］=i!(8≤i≤13)，以后每输入一个n，判断：
若n为负数，且绝对值为奇数，或者n>13((n<0&&(-n)%2==1)n>13)，则上溢,输出"Overflow!"；若n为负数，且绝对值为偶数，或者n<8((n<0&&(-n)%2==0)n<8)，则下溢，输出"Underflow!"；否则输出f［n］。
【1.3.18 Squares】
【问题描述】
在一个N*N格点方阵中给出一些长度为1的线段，请计算出一共有多少个正方形。
输入：
输入包含若干测试用例，每个测试用例描述了一个N*N（2≤N≤9）格点方阵以及若干内部连接的水平和垂直线段。每个有N2个点的格点方阵有M条内部连接的线段，格式如下：
第1行：N，表示格点方阵的一行或一列中的点数；
第2行：M，表示内部连接线段的数量。
接下来的M行中每行为如下两种类型之一：H i j，表示在第i行连接第j列到第j+1列的点的水平线段；或者V i j，表示在第i列连接第j行到第j+1行的垂直线段。
每行的信息从第1列开始，以EOF标识输入结束。样例输入的第一个测试用例表示上面的图。
输出：
对每个测试用例，用"Problem #1"、"Problem #2"等标识相应的输出。每个测试用例输出给出每种大小的正方形的数量。如果任何大小的正方形都没有，要输出相关的信息来说明。两个连续的测试用例之间，输出两个空行包夹一行星号，见如下样例所示。
试题来源：ACM World Finals 1989
在线测试地址：UVA 201
提示
首先，很直观的想法是：
用一个01矩阵表示边是否存在，然后枚举左上角的顶点和边长，检查每条边是否都存在。时间复杂度为O(n4)。
当然，有一个很简单的优化方法，那就是预处理计算出每个点往下、往右可以延伸多长，这样可在O(1)时间内直接找出每种大小的正方形数量，使得整个算法的时间复杂度为O(n3)。
但是这种做法会给我们这样一种感觉，那就是存在很多冗余。试想一个点作为左上角存在边长为K的正方形，虽然它不一定存在边长为K-1的正方形，但是我们至少可以确定，边长为K-1的正方形的两条边是必然存在的。我们尝试着来去除这种冗余计算。
我们把一个正方形拆成左上和右下两部分（如图1.3-6）。
那么两个部分可以构成一个正方形的充要条件就是：
1)两个顶点在同一条倾斜135度的直线上。
2)右下部分的两条边与左上部分的两条边有交点（如图1.3-7）。
对于给定的一个，我们按照图1.3-8所示的斜线顺序进行处理。
如果读者对堆+树形数组并不熟悉也无妨，我们可以通过枚举每个可能的左上角和正方形的可能大小，判断对应的子正方形是否存在，并累计每种大小的正方形个数。
【1.3.19 The Cow Doctor】
【问题描述】
Texas是美国拥有牛最多的州，根据2005年国家农业统计局的报告，德州的牛的数量为1380万头，高于第2名的州与第3名州的牛数和：在Kansas有665万头牛，在Nebraska有635万头牛。
有几种疾病威胁着牛群，最可怕的是“疯牛病”，也就是牛海绵状脑病（Bovine Spongiform Encephalopathy，BSE），所以能够诊断这些疾病是非常重要的。幸运的是，现在有许多测试方法可以用来检测这些疾病。
进行一项测试的过程如下。首先，从牛身上提取血液样本，然后将这个样本与试剂混合。每种试剂检测几种疾病。如果与试剂混合的血液样本有这些疾病，那么可以容易地观察到它们会发生反应。然而，如果一种试剂可以检测几种疾病，那么我们无法确定在血液样本中的疾病是产生相同反应的几种疾病中的哪一种。现在有的试剂可以检测多种疾病（这样的检测可以用来立即排除其他疾病），而有的试剂用来检测很少的疾病（可以用来对问题作出精确的诊断）。
试剂可以相混合产生新的试剂，如果我们有一种试剂可以检测疾病A和B，又有另一种试剂可以检测疾病B和C，那么把它们混合获得一种试剂可以检测疾病A、B和C。这就是说，如果我们有这两种试剂，那么我们就不需要一种可以检测疾病A、B和C的试剂——这样的试剂可以通过混合两种试剂来获得。
生产、运输、储存许多不同类型的试剂是非常昂贵的，并且在许多情况下也是不必要的。请除去尽可能多的不必要的试剂。如果一种试剂被除去，就要求能从剩下的试剂中混合产生等价的试剂。（“等价”表示混合的试剂可以检测出被删除的试剂所能检测的相同的疾病，不会多，也不会少。）
输入：
输入包含若干个测试用例。每个测试用例的第一行给出两个整数：疾病数n（1≤n≤300），试剂数m（1≤m≤200）。接下来的m行对应m种试剂。每行首先给出一个整数k（1≤k≤300），表示试剂可以测出多少种疾病。后面的k个整数表示k种疾病，这些整数取值在1到n之间。
输入以n=m=0结束。
输出：
对每个测试用例，输出一行，只有一个整数：可以除去的试剂的最大数目。
试题来源：ACM Central Europe 2005
在线测试地址：POJ 2943,UVA 3524
提示
由于疾病数n的上限为300，因此我们将每50种疾病分为一组，共分成t=n-150组，疾病i分在第i-150组，组内序号为i%50。每组状态可由50位二进制数表示，第i位为1代表组内序号为i的疾病存在。我们在输入数据的同时构造a［］［］表，其中a［i］［j］为试剂i中第j组的状态。
然后枚举每个不同的试剂对i和j（i≠j）：若试剂i的t组状态a［i］［］分别是试剂j的t组状态a［j］［］的子集，则a［i］［］并入b［j］［］，最终使得b［j］［］成为试剂j所检测的所有疾病中可被其他试剂所替代的部分。
最后枚举所有试剂：若试剂i的t组状态a［i］［］与b［i］［］相同，说明试剂i检测的所有疾病可被其他试剂替代，则去除的试剂数加1。
【1.3.20 Wine Trading in Gergovia】
【问题描述】
正如你可能从漫画“Asterix and the Chieftain’s Shield”中知道的，Gergovia由一条街组成，城市中的每个居民都是葡萄酒商。你想知道城市的经济是如何运作的吗？非常简单：通过每人从城市里的其他居民那里购买的葡萄酒。每天每位居民决定他要买或卖多少葡萄酒。有趣的是，供给和需求总是一样的，所以每个居民都能得到他想要的东西。
然而还有一个问题：将葡萄酒从一个房子运送到另一个房子需要一定的工作量。由于所有的葡萄酒都同样出色，Gergovia的居民并不关心哪个人和他们进行交易，他们只关心卖或者买葡萄酒的具体数量。他们会非常精明地算出一种交易方式，使得运输的工作总量最小。
本题要求你重构在Gergovia的一天的交易。为了简便起见，本题设定房子是沿直线建造的，两幢相邻的房子之间的距离相等。将一瓶葡萄酒从一幢房子运送到相邻的一幢房子要耗费一个单位的工作量。
输入：
输入包含若干测试用例。每个测试用例首先给出居民数量n（2≤n≤100000）。下一行给出n个整数ai（-1000≤ai≤1000）。如果ai≥0，则表示生活在第i间房子的居民要买ai瓶葡萄酒；否则，如果ai<0，他就要卖ai瓶葡萄酒。本题设定所有ai的总和为0。
最后一个测试用例后跟着只包含0的一行。
输出：
对每个测试用例，输出满足每个居民的要求所需要的最小的运输工作总量。本题设定这一数字是一个带符号的64位整数（用C/C++，使用数据类型long long或int64；用Java，使用数据类型long）。
试题来源：Ulm Local 2006
在线测试地址：POJ 2940
提示
先来看一组最简单的数据：
-2 2
把右侧往左侧挪2个，最小的运输工作总量为2。也可以看做是左侧往右侧挪-2个，答案同样为2，这两种想法是等价的,因为最终每个位置上的数应该是0。
设now为当前剩余(或亏欠)葡萄酒数，ans为目前最小的运输工作总量。初始时now和ans为0。
顺序扫描每个房间i(1≤i≤n):ans=ans+|now|,now=now+ai。最后得出的ans即为最小运输工作总量。
【1.3.21 Power et al.】
【问题描述】
我们发现任何数的指数是非常令人烦恼的，因为它呈指数增长。但本题只要求你去做一个非常简单的工作。给出两个非负整数m和n，请找出在十进制数下mn的最后一位数。
输入：
输入少于100000行。每行给出两个整数m和n（小于10101）。以两个0的一行作为输入结束，程序不用处理这一行。
输出：
对于输入的每个测试用例，输出一行给出一位数，这个数字是mn的最后一位的数字。
试题来源：June 2003 Monthly Contest
在线测试地址：UVA 10515
提示
这种题目看似无从入手，其实非常简单。既然只要求个位数，那么其他位的数就不必考虑了，因为个位数不会因相乘的进位而发生变化。举一个数字来说，8的1998次方。首先看看8的n次方的个位的规律：
8的1次方个位为8
8的2次方个位为4：8*8=64
8的3次方个位为2：4*8=32
8的4次方个位为6：2*8=16
8的5次方个位为8：6*8=48
8的6次方个位为4：8*8=64
8的7次方个位为2：4*8=32
仔细看下，8是以每4个连续的次方为一个循环。19984为499余2，不大于1998且能被4整除的最大正整数为1996。按照8的n次方个位的规律，81996的个位数为6。81998＝81996+2，其个位数就是4！。依次类推，2、3、7都是以每4个连续的次方为一个循环的；4和9是以每2个连续的次方为一个循环的；5和6的任何次方的最后一位数即为底数的个位数。由此得出算法：
取m的最后1位k，n的最后2位d。mn的最后一位数字为：
【1.3.22 Connect the Cable Wires】
【问题描述】
Asif是East West University的一个学生，现在他为EWUISP工作以支付他相对较高的学费。有一天，作为他工作的一个部分，他被要求将电缆线连接到N个房间。所有的房间位于一条直线上，他要使用最少条电缆线完成他的任务，使得所有的房间都能接收有线电视服务。一个房间或者从主传输中心获得连接，或者从与它相邻的左边或右边的房间获得连接，而与它相邻的左边或右边的房间已经被连接了。
请编写一个程序，确定能使每个房间接收有线电视服务的电缆线的不同组合的数目。
例如，如图1.3-9所示，有两个房间，那么可能有3种组合。
圆表示主传输中心，小矩形表示房间。
输入：
每行给出一个正整数N(N≤2000)，N的含义在上述段落中已经描述过，N为0表示输入结束，程序不必处理。
输出：
对于每一行输入，产生一行输出，给出可能安排的数目。本题的数字小于1000位。
试题来源：The Next Generation-Contest I 2005
在线测试地址：UVA 10862
提示
设：
f［i］表示当前合法方案数(每一个横向连通块都有一个地方连线中心)；
g［i］表示当前总方案数(最后一个横向连通块没有中心连线的方案数)。可得
f［i］=f［i-1］*2+g［i-1］（若最后一个连通块有中心连线，可以连一条直接连接一个连通块的线或新建一个连通块并连线中心，否则连向上一连通块并连向中心）
g［i］=g［i-1］+f［i-1］（连向上一个连通块或新建一个连通块）
令h［i］=g［i+1］=f［i］+g［i］，可得f［i］=f［i-1］+h［i-1］，h［i］=h［i-1］+f［i］（这是为了减少调用高精度计算的次数）。
