《算法竞赛入门经典》3.3节例题总结

算法竞赛入门经典》3.3节中例举的竞赛题目中多有一些巧妙的程序编写思想的体现或小技巧,在此予以总结。

例题3-1 Tex中的引号 (Tex Quotes, UVa 272)

边读入边操作

本题的测试数据是以行为单位,因此在编写程序时很容易想到先将每行内容作为字符串读入,再遍历字符串寻找引号进行操作。这种做法耗费的时间与空间开销至少有以下三个方面:

  1. 需要建立一个缓冲区字符数组用以存放读入的字符串(且题中没有给出这个字符数组的大小上限)
  2. 读入字符串耗费的时间
  3. 遍历字符串查找引号耗费的时间、

此外还有一个问题不易解决:

要替换的左双引号 ``和右双引号''均是两个字符,而要被替换的引号"却是一个字符,不能直接在找到引号后将要替换的左(右)双引号直接插入字符串对应位置

此时考虑另外一种思路:以字符为单位进行读入,在读入的同时立即进行判断,即可避免缓冲区的空间开销,亦可省去读入字符串的时间。

小技巧

  1. 条件运算符在此处的使用printf("%s", q ? "``" : "''");可使程序变得更简洁。
  2. q = !q

例题3-2 WERTYU (WERTYU, UVa 10082)

使用常量数组

将键盘字符序列存储于一个常量数组中来将错误按键——正确按键的转换变为对数组下标的操作(因为错误按键与正确按键在键盘字符序列中相邻)。文中指出的另一种使用常量数组的方法亦是一种值得注意的打表思路。

例题3-3 回文词 (Palindromes, UVa 401)

在同一循环中并行处理多个条件的判断

以此避免多个条件需要循环多次的时间开销。

字符串数组msg[]的巧妙设计

巧妙地利用回文串和镜像串判断变量pm的取值范围(\({0, 1}\))来计算msg[]的下标,进而输出想要的字符串,从而避免使用条件语句,使程序更简洁。

例题3-4 猜数字游戏的提示 (Master-Mind Hints, UVa 340)

更换思路,避免直接判断

在计算B的值时,文中解法避免了对两个字符串进行搜索、统计,转而利用易于统计的直观条件,直接对数字1-9的出现次数进行判断,再减去易于统计的的A的部分,从而避免了繁杂的搜索、统计过程,曲线救国。

例题3-5 生成元 (Digit Generator, UVa 1583)

打表

本题算法的时间复杂度是O(N),如果连续给出接近n上限的测试数据则可能导致TLE。为解决这一问题,直接对1~100000的n值进行打表,之后再使用查表法输出数据。

例题3-6 环状序列 (Circular Sequence, UVa 1584)

善用模运算

由于本题操作对象的特性(环形),因此不必每次都实际进行将环状串“旋转”的操作,而是可以通过记录环状串的某种表示法在环状串中的开始位置来表示单种情况,又由于环状串的连续性(不会有插入和删除操作),因此只需用普通的字符数组存储输入串,对于需要越过输入串的结尾,重新从开头开始的情况,使用模运算计算下标,如s[(p + i) % n]

updatedupdated2023-03-112023-03-11