算法题做题记录

March 22, 2021 1 minute read

上次做UVA还是2018年9月，后来做了会力扣，一共也没做多少道题。转眼快三年过去，还是没有太大的长进，是时候重新沉下心来认真学习了。

OJ测试数据整理：这里

技巧

在以默认配置使用cin与cout时效率有些慢，可以通过关闭stdio同步提高效率：
```
std::ios::sync_with_stdio(false);
```
sstream的效率非常低，尽量少用。
vector容器的内存分配和初始化也是有线性时间复杂度的。
在使用STL查找算法时，如果序列有序，可以使用二分查找算法。 find可用于无序序列，是线性复杂度。

二分查找算法包括binary_search，lower_bound，upper_bound和equal_range。

因为set并不是有序序列，使用通用的二分查找算法的时间复杂度并不是log(n)，需要使用自己的查找方法，比如std::set::lower_bound。
在自定义sort比较函数时不能返回<=或>=，会造成循环比较。
在对pair类型进行排序时，可以通过改变数值的正负性，使其可以直接使用默认排序。
智能指针的效率比普通指针低一些。

UVA

UVA-202 Repeating Decimals

不存在循环小数时应该写1位，循环为(0)
小数位数（非循环部分加上循环部分，不是循环部分位数）超过50位时需用省略号(…)表示
每个条目的第二行起始都有三个空格，条目后需要有一个空行

UVA-213 Message Decoding

这道题在输入指令时会有多行，可能会把一条指令从中切断。这里可以编写一个函数，在读取指令时过滤掉换行和回车符。

需要清除一段指令末尾的换行符。

UVA-212 Use of Hospital Facilities

这道题没什么难度，主要是认真审题。分两个部分进行：先完成对所有病人的手术分配，然后完成康复分配。最后按照要求输出。

使用3个优先队列，分别表示手术室、康复室以及完成手术的病人。手术室和康复室的选择规则是相同的：在有效的房间中选择编号最小的。因此只需要两个变量：房间编号以及房间转为有效状态的时间，只是有一些细微的区别。病人队列需要三个变量：病人编号用于索引，病人接受手术的房间以及完成手术的时间，后两个用于排序。

在分配手术室时，手术室只要空下来就立刻有病人上来。只需要按照优先级将病人一个个送去手术就行了。

在分配康复室时，题目有一个前提条件：病人结束手术时一定有空余的康复室，因此康复室空下来后要等待病人做完手术。于是由于有效康复室的时间变量数值不一致，无法正确按照序号排序。因此在选择康复室时，需要先将所有有效康复室的时间变量更新为病人的出院时间，这样一来优先队列顶部就是序号最小的有效康复室了。

最后输出时要注意表格左边的空格。第一个病人的表格按照图上的样子输出即可。第二个表格行前是没有空格的，虽然看起来为了和上一个表格对齐需要添加一个空格。

另外，文中说输入文件包含一次单独的运行模拟，但是实际上会有多组数据。

UVA-227 Puzzle

这道题，在处理事件时如果发现完不成了，不能立即结束，必须读到0才行，否则可能会漏掉几行的操作语句。另外，在指令中会出现无效字符。

也可以在读取时多加验证，这样出现读取错误时返回的结果是 Runtime error，和WA区分开。

UVA-230 Borrowers

这道题书本的摆放顺序不是按书名的字典序来，而是先要按作者的字典序。但是又通过书名索引。于是按照摆放顺序建立一个存放书籍信息的数组，然后建立一个map将书籍与其在数组中的序号对应起来。

在借还书时通过map索引书籍并更新状态，复杂度为log(N)。在整理书架时直接从头到尾操作一遍数组即可，复杂度为N。

UVA-253 Cube painting

序号1和6、2和5、3和4的三组面分别互相平行。

将两个骰子命名为一和二，骰子一不动，通过旋转骰子二使两者的排列相同。首先查找骰子二中与骰子一的1面颜色相同的面，将其旋转到1点位置，那么此时两个骰子的面6的颜色需要一致。然后以面16为轴旋转骰子二，共有四种情况，判断是否有序列一致的时候。这种方式是一个双重循环，一共24种情况，但实际第一步的六种情况很多都直接跳过了。

翻了下提交，有些代码偷懒了，实际上并不严谨，竟然还通过了。。。

UVA-455 Periodic Strings

这道题一开始想当然了，比如下面这个字符串：

abaababaab

如果用aba去检验，会在第7到9位失败。这时如果直接将最小周期设为7位，最后结果是10位，就不对了。只能老老实实地判断每一种情况。

另外，这道题在两个答案间需要隔一个空行，如果没有这个空行会是WA而不是PE，心累。

UVA-508 Morse Mismatches

题目中的 fewest charachers 指的是字典序最小而不是字符数最小，看例子就知道了。

当能够精确匹配时没有什么问题。不能精确匹配时需要遍历所有的情况，找出所有满足短字符串是长字符串的前缀的单词，并选择编码字符数量相差最少的单词。而不能简单地选择字典序最接近的单词。

UVA-1587 Box

这道题需要知道判断的充分条件。假设构成长方体的三条边有如下长度规则：a<=b<=c。我们将每个面的两条边从小到大排序，六个面按边从小到大排序（先比短边，短边相同比长边），得到一个序列。

在序列中1和2、3和4、5和6必须相同。排过序了，必须有三对相同的面。
对于序号为1、3、5的面，如果能够构成长方体，按照排序规则，这三个面的顺序必然为ab，ac，bc。换句话说，1的短边与3的短边、1的长边与5的短边、3的长边与5的长边，这三个条件需要满足。

这条规则对于存在相同长度的边的情况同样适用。

UVA-1589 Xiangqi

计算在当前情形下黑子的安全点，如果将能够移动到安全点，则不能被将死。

这道题会有吃子的情况，在吃子时需要去掉被吃的棋子，重新判定。

uDebug中那个双方将领面对面的情况应该是错误的，这种情况下棋局已经结束了。

UVA-1590 IP Networks

ip地址正好可以转化为无符号整数。只要找出最小的和最大的两个ip，取一下异或再取反，保留第一个0之前的1，就是子网掩码了。任选一个ip和mask与一下就是网络地址。

事实上网络地址本身是不能够作为ip分配出去的，ip段中的最后一个地址叫做广播地址，一般也不能被分配。题目里没说，就不需要考虑这些了。

UVA-1591 Data Mining

如果知道A和B的范围，直接穷举就能得到答案了。否则先要推导其范围。

这里先介绍一种数学方法，以此能够确定两个参数的范围。但是这种方法无法顾及到特殊情况（计算机的取整），不适合实际应用。

这道题是要找到一组A、B，使得 (P + P « A) » B 成为大于Q的所有情况中的最小值。将式子变形，得到：

\[\begin{cases} f(A,B) = P(1+2^A)/2^B = P*2^{A-B}(1+2^{-A}) \\ f(A,C) = P*2^C(1+2^{-A})\geq Q & C=A-B\leq A \end{cases}\]

显然在C确定的情况下，方程式的值域在如下范围中：

\[P*2^{C_1} < f(A, C_1) \leq P*2^{C_1+1}\]

任意整数Q必然位于上述一个特定的区间。因此先找到这个C，再确定A。

由于函数随A单调递减，从 A=0 开始尝试，直到方程式的值小于Q，那么前一个A值就是能够使空间K最小的值了。

再根据关系式算出B，答案就出来了。

你以为到这里就能AC了，想多了。

题目里说了，A和B都是非负整数，在这里A一定满足，但是B就不一定了。比如说下面这组数据：

// 输入 1024 7 65
// A = 2, B = -1
(7 + 7 << 2) << 1;

由于B是负数，位移符号的方向理应相反，程序可没有这么聪明，于是这个解就没有实际意义了。

这时只能将上面的参数C自增1，显然这时A取任何数值都满足 f > Q。由于方程式递减，A越大越好。但是A总该有个上限吧。这时需要从另一条规则入手了：当空间K相同时，A应尽可能小。列一下空间K的计算公式：

\[K = (n-1)P\frac {1+2^A}{2^B} + Q = (n-1)P(2^{A-B}+2^{-B}) + Q\]

A-B显然是大于0了，重点在第二项。记得那句话：一尺之棰，日取其半，万世不竭。在程序里，整数的最小单元就是1，小于1就直接变成0了，是有穷尽的。因此当它满足下列条件时，空间K就相同了：

int K1 = (n-1)*P >> B; // K1 = 0

转换成数学公式：

\[log_2((n-1)P) < B < log_2((n-1)P) +1\]

至此我们得到了最小的B和C，所对应的A（A=B+C）也是最小的。在这种情况下C一定大于0，因此A也一定大于0。

这时再美滋滋把代码提交，结果还是WA。。。

在这道题里还存在两种特殊情况：

当元素数为1时，并不存在偏移量（就是0），直接将A和B取0就行了。
在能够取得最优解的情况下，当元素数较少时，经过四舍五入，更大的偏移量会和较小的取得相同的结果。比如：
```
p = 1023, q = 1;
// 精确情况
A = 9, B = 19;
// 当n取不同值时的实际情况
n = 2, A = 0, B = 10;
n = 342, A = 8, B = 18;
// 当n继续增大时截尾效应就消除了
n = 343, A = 9, B = 19;
// 阈值处的情况
// 341 * 1023 * 257 >> 18 = 341
// 342 * 1023 * 257 >> 18 = 343
```
这也是因为向右位移操作会忽略小数部分。因此在计算A时因使用Pos(n-1)判断，当出现小于 Pos(n-1)+1 的解时A就满足条件了，这时再缩小区间没有意义。

现在交上去就AC了，但是我们还没有得出A和B的范围。

考虑到题目中P和Q的范围，Q/P一定在-10和10之间，P与Q的差在0和1023之间。

在第一种情况（Q落在区间内的情况有效）下，当P=1且Q=513时，A取得最大值9，此时B为0。由关系式 B=A-C 可知B不会超过19（上限19情况已出现在上面的特殊情况中）。

在第二种情况（Q落在区间右侧）下，C大于0。此时的P和Q应有如下关系：

\[P+2^{C-1}P < Q < 2^{C}P \quad (n>0)\]

因此C至少取2，P最大为341。

由K的公式可知B不大于29，当取下述数值时，B具有最大值29（情况不唯一）：

n = 1048576;
p = 341;
q = 1024;

将上面的公式取对数可得：

\[log_2(Q/P) < C < log_2(Q/P-1) +1 < log_2(Q/P) +1\]

由此可得A的范围：

\[A = B+C < log_2((n-1)Q) + 2 = 32\]

A最大为31得证。

既然知道了A和B的范围（A不超过31，B不超过29），就不需要使用上述复杂方法计算了，穷举即可。

翻了下网上的文章，有的人是通过C++语言中整数不超过64位将A和B限定在32之内。毕竟超过这个范围，那段代码就无法正确运行了。我觉得题目中的范围也考虑到了这一点。

于是这道题只要通过穷举就能完成了。So easy!

UVA-1594 Ducci Sequence

这又是一道类似循环小数的题，但是如果记录每一次的情况，会消耗大量的时间。我用sstream将数据转换成string放到map中，操作中还包含了很多次的索引查找，最终用了1500毫秒。

在题目中说计算超过1000次就可看作陷入死循环，因此可以不记录每一次的情况。这样做只用了120毫秒。用时最短的答案激进地将最大次数设定为了50次，结果只要10毫秒。

UVA-1598 Exchange

这里需要4个列表：订单列表，价格物资列表，购买队列和出售队列。其中订单列表和价格物资列表需要索引时间最短，因此使用数组。购买队列和出售队列为优先级队列。订单列表包含订单类型、价格以及物资剩余数量，剩余数量为0的表示失效订单。由于一个价格在特定时间只会有一种状态（买或卖），价格列表只需要一个。

当出现新的交易订单时，首先处理可能发生的交易，并将失效的订单移除优先队列。如果新订单仍有物品剩余则将其加入队列。

当进行取消操作时，先判断订单有效性。如果订单有效，则在价格物资列表中扣除对应数量并使该订单失效。如果订单价格为牌价且该订单是当前牌价的唯一订单，则更新牌价（将优先队列头部的所有失效订单出列）。

报价时，牌价为队列头部订单的价格，数量查询列表获得。

本方案的主要耗时在优先队列的入列和出列（复杂度为log(n)）。

UVA-10391 Compound Words

一开始用了这个方法：比较所有与当前单词首字母相同的单词，如果确实是前缀，那么查找剩余部分是否为一个单词。发现比别的答案慢了很多。原因是当单词数量很多时，比较次数会非常多。题目中有12万单词，就算平分给每个首字母，一个首字母也有5000，每个单词平均下来也要查找个上百次。况且比较操作是线性复杂度，两次比较就相当于一次查找了。

于是只要将单词分割，查找前后两部分是否都是单词就行了。毕竟单词本身不会特别长，平均下来处理一个单词也就查找个十几次。

UVA-10763 Foreign Exchange

可以使用两个数组，一个储存(from, to)序列，另一个储存(to, from)序列。在排序后如果这两个序列不同说明交换不成功。

有的答案（看那些耗时小于50毫秒的）使用单个数组解决问题，方法为先升序初始化数组，然后根据每个交换生的情况交换对应位置。如果最终的数组和初始时相同，则说明能够进行交换。这种方法存在两个问题：

这道题虽然不允许学生从A到A，但允许多个学生从A到B。如果有两个学生都是从A到B，算法会认为交换能够进行而实际不可以。
题目指出学生数量不超过50万，但并没有给出位置序号的范围。这里将数组范围开到50万是欠妥当的。

UVA-11809 Floating-Point Numbers

c++的双精度数的阶码(exponent)有11位，尾数(mantissa)有52位。题目中阶码需要30位，因此不能直接用double做。

根据题目，一共只有300种情况，可以采用穷举。测试中输入的数据在300组左右，因此可以先将对照值放在表中。考虑到输入的数为科学计数法，可将对照值取10的对数后分离小数与指数部分。

读数据时可以使用string，将e用空格替代后使用stringstream读出小数和指数。

在比较时先比较指数，指数相同时比较小数。题目中提到输入数据的有效数字为15位，但由于我们对对照值取了对数，精度会降低，无法确定误差阈值。这里可以选取所有情况中误差最小的情况为结果。

UVA-12108 Extraordinarily Tired Students

这道题的坑点在于有可能会陷入死循环。我用的方法很基本，就是检查是否有重复情况出现。和计算循环小数相同，当学生的状态与之前的某个时间点一致时，他们就在这段区间里出不来了。

这样的话需要有一个集合保存所有的状态。不知道有没有更好的方法。有的人是将当前状态与第一次的情况对比，但是这样的话要先证明初始状态一定在循环中，尽管在感觉上这是成立的。

UVA-12333 Revenge of Fibonacci

Share on

Twitter Facebook LinkedIn

Qianhuang Chen