蓝桥杯练习系统的一些题解思路

CodeingBoy 3月 25, 2017

BASIC-2 01字串

水题,这些01字串其实就是 0~31 的二进制表示字符串而已。因此有以下几种思路:

  1. 将 0~31 的每个数字转换为二进制数字符串再输出。这种方式的话要考虑长度不足 5 时要在前面补 0。
  2. 枚举 5 个 bit 的可能情况,然后根据这 5 bit 的排列输出。

BASIC-3 字母图形

观察给出的字符串,可以发现第二行开始,按照字母表顺序在前面插入字符,而超出长度的字符则被抛弃。

因此可以设一个字符串,它包含从 A~Z 的所有大写字母,第一行根据列数从这个字符串取字串即可。之后从这个字母表字符串中取一个字母插入到上一行字符串中,并截掉超出的部分。

BASIC-4 数列特征

水题,不解释。注意不需要保存每一个数。

BASIC-5 查找整数

水题,不解释。可惜不是先给出 pattern,否则应该可以边接收输入边查找。

BASIC-6 杨辉三角形

杨辉三角是一个下三角方阵,因此有 n 行* n 列,可以做一个 n * n 的二维数组来存放杨辉三角。

做题过程中犯了几个错误:

  1. 由于使用了双层循环,这个时候会下意识地把上面写好的循环复制过来用,但是循环条件忘了改,导致出错。
  2. 为了省掉无谓的计算,可以只对下三角元素进行计算,位于主对角线的元素的坐标是 (row, row)(row是当前的行序号,从0开始),但循环条件可能会下意识写成 row / 2。但row行其实有 row 个元素,因此应该写成 row。

另外在输出的时候 Java 会自动不输出0,因此不需要写屏蔽0的逻辑。

BASIC-7 特殊的数字

水题,这种数其实就是水仙花数。暴力测试可破。

BASIC-8 回文数

水题,先将数字拆成一位位的再逐一比较,或者转为字符串后再逐对比较。暴力测试可破。

BASIC-9 特殊回文数

在前一题的基础上增加对每一位数求和的检测即可。

BASIC-10 十进制转十六进制

原理网上有很多,这里就不赘述了。自己写转换函数的话注意对 0 的处理。

不过使用Java的同学有福了:可以使用 Integer.toHexString(num) 来直接获取答案,但输出的字母是小写字母,因此完整的写法是 Integer.toHexString(decNum).toUpperCase()。

BASIC-11 十六进制转十进制

原理网上也有很多,不赘述了。

自己编写函数转换的话需要注意int的范围限制。另外如果使用 Integer.valueOf(char) 来将char转为int的话,需要先将 char 转为 String,否则会直接返回该 char 对应的整数。

直接使用 Java 内建函数的要注意不能使用 Integer.valueOf(string, 16),因为 8 位的 FFFFFFFF 已经超出了int的表示范围,会抛出 NumberFormatException,应该使用 Long.valueOf(string, 16)。

BASIC-12 十六进制转八进制

这回发生了两个变化:一是从单个输入变成了多个输入,二是数字的规模增大。

最初的思路是先将数转为十进制,再转为八进制。可惜由于数字太大无法直接转换。之后发现 2、8、16 都是2的幂,1 位十六进制数代表 4 位二进制数,而 1 位八进制数代表 3 位二进制数,因此可以通过将数据分块,将每块3位(3*4=12)十六进制数转为二进制数,再将这 12 位二进制数转为 4 位八进制数。分块转换时,如果从前往后转换结果可能会不正确,而如果从后往前转换,最后一块可能会出现长度不足3的块,可以在一开始就检测字符串长度是否为3的模。如果不是,在头部补0直到满足即可。这样无论是哪种顺序都不会出错,并且保证块的长度都为 3。

当然了,先将十六进制数整个转换为二进制数,再将这个二进制数整个转换为八进制数也可以。

注意,虽然输入保证没有前导 0,但不保证中间没有 0,而如果 0 正好在分块的3位数前面会导致转换错误。所以在一个块转换完毕后要检查是否是 4 位的八进制数,位数不足则补 0。但经过这样处理后可能会产生前导 0,因此需要在输出前处理掉前导 0。

我用Java API 转换的时候是先转换为十进制再转换为八进制,因为 3 位十六进制不会超出 int 的范围,并且可以方便地转换为八进制。如果一定要转换到二进制再转换到八进制,需要多两次 API 调用。并且在十六进制转二进制和二进制转八进制的过程中仍然使用了十进制进行中转。

如果是自己写函数进行转换,一定要注意是否超时,最好是从前往后转换,如果从后往前转换,可能会在将结果插入到头部时浪费大量时间。

BASIC-13 数列排序

水题,排序有很多方法了,而且 C++ 和 Java 也都提供了现成的排序库函数,直接调用即可。

BASIC-14 时间转换

水题,只需要知道秒和其它时间单位之间的关系即可轻松做出。

BASIC-15 字符串对比

水题,按题目说的做即可。

BASIC-16 分解质因数

基本原理网上有很多了,这道题只是比较繁琐而已,不难。

求素数表的时候不需要为每一个数都求一个素数表,只需要求最大的那个数的素数表,然后使用比当前元素小的素数进行分解即可。

BASIC-17 矩阵乘法

这题也不难,但是比较繁琐。注意有可能出现 0 次幂。因此应该使用一个单位矩阵而不是输入矩阵去进行相乘。

BASIC-18 矩形面积交

稍微有点难度了……对于数学的东西有点不太上手。

题目只给出了一个矩形中的两个坐标,但是同时又声明边与X\Y轴平行,因此可以算出另外两个坐标(x1,y2)和(x2,y1)。

最初的思想是以矩形 A 为基准矩形,用矩形 B 的四个点判断是否落入矩形 A 的区域,如果落入则算出矩形 A 落入矩形 B 的点的坐标,再根据这两个点算出面积。但如果在 A 包含 B 的情形中,矩形 B 将有四个点落入矩形 A,矩形 A 则没有点落入矩形 B。在 A 和 B 左右重叠的时候,每个矩形都分别有 2 个点落入对方矩形。

第二个思想是检测矩形 A 和矩形 B 之间是否存在相交的边,若存在相交边,则算出相交的坐标,进而算出面积。但是仔细思考下来会发现这种办法无法很好地处理 A 包含 B 的情形,放弃之。

1 1 3 3
2 1 4 3

1 1 4 4
2 2 3 3

另外需要注意的一点是,题目输入的是实数,而不是整数。

判断相交点思想的实现

输入什么的都很好搞定,第一个难题是计算某个给定的点是否在一个矩形内,这时候只要判断点的坐标是否处在在这个矩形内坐标最小的点和坐标最大的点之间就可以了。题目的输入没有保证 A < B,因此为了以防万一,最小点和最大点采取了自己计算的策略。

求得相交点后会有两种可能情况:

  1. A 和 B 各有一点落在对方矩形,这是某个区域相交的情形
  2. A 和 B 各有两点落在对方矩形,这是左右重叠的情形
  3. A 或 B 之中有一个的四个点都落在对方矩形,而另外一个矩形没有点落在对方矩形,这是包含的情形

前两种可以通过计算最小最大点进而计算相交面积。后一种不仅可以计算计算最小最大点,也可以返回被包含矩形的面积。

不过在计算最小最大点的时候要注意查找的条件,在特殊的条件下有可能会出现最小点和最大点为同一个点的情况,进而计算失败。

BASIC-19 完美的代价

回文串的特征是每个字母都有偶数个,在长度奇数的串之中允许有一个字母有奇数个。因此可以先判断是否可以交换形成回文串,若否直接输出。

屏蔽了无法组成回文串的字符串之后,就可以考虑如何用最小的交换次数来组成回文串了。

题目提示是贪心算法,从贪心法的角度来看,应该保留那些已经放好位置的字符,但是如果其左右两边字符需要交换到别的位置,那么这些放好顺序的字母将被打乱。

那按照从两侧到中间的顺序来交换字母呢,这样子就可以避免已放好的字母不被打乱。考虑示例字符串,一开始将 m 交换到最右需要 2 步,最后将 a 放置好需要 1 步,似乎可以得出最优的结果。

被交换的字符从哪里来?从要放置到的位置开始,向前遍历直到找到与要放置字符一样的字符,这样就近选取交换字符可以节省步数。但最坏情况就是要放置的字符串未排序区的最左边了。

提交之后提示 WA,发现这样的办法对于 abb 这样的要在左侧进行交换的无能为力。只能通过在找不到交换字符时,与交换下一个字母来进行尝试。

修改后仍然提示 WA,看来是选用的方法不对了。查看了锦囊后发现好像什么也没说……

问题到底是出在哪里呢?对比输入输出数据后发现数据都对,最后发现是没把调试用的输出语句删掉……

注释后完美通过,真是佩服我自己……

另一种解法

上面的那种解法有点难处理,有点取巧的意思。一年后我又尝试重新完成这道题,结果就卡在一些难度比较高的输入上面了(如aaabbbbcccc)。

于是我又重新提出了另外一种解法:

  1. 将整个字符串各种字符的出现频率进行计数
  2. 使用以下方法,从左到右构建一个目标字符串:遍历原字符串左半边的字符,如果对应的字符频率尚大于2,加入到目标字符串中。
  3. 保存一份当前目标字符串的副本以备后用。
  4. 如果输入长度是奇数,找出奇数的那个字符,加入到目标字符串中。
  5. 逆序将之前那份副本字符串的字符逐一加入目标字符串,得到完整的回文。
  6. 从左到右遍历原字符串,检查左半边的字符是否与右半边的字符相同,若否,从不匹配的那边向另一边找出最近距离的字符,并交换。

原本的那种办法因为在找不到字符时只能与旁边字符交换,因此个人认为不太可靠。而最初按思想实现的时候,是通过先构建目标字符串,然后再进行交换计数的方法实现的,基本思想还是尽可能维持字符串的原本顺序——能不动的就不动,因此保持左半边的顺序。但是最初的目标字符串构造不太顺利,无法应对aaabbbbcccc这样的输入,因此就改成现在这样了。

BASIC-20 数的读法

题目看起来难度不大,第一件事就是把所有数字对应的拼音写出来做成数组。数字规模较大,因此最好使用 long 存储。

接下来就是分解十进制数上每位的位数了,再根据其的权重决定单位,最后拼接。

这里就有个问题了,示例中的数只能读作“十二亿”而不能是“一十亿二亿”,由于会牵涉到下一位,这就使得无法无脑拼接,因此要对十位和个位进行特殊的处理。

不过在实现上由于要考虑很多逻辑,因此实现起来比较麻烦。最后还是使用暴力分解来完成这道题。为了处理各种情形,逻辑写得又臭又长,真是不优雅啊。

重新思考

试着重新完成了这道题目。但还是差不多,使用了递归,使得函数可以处理 4 位数(可以将数字分解为几段 4 位数,满 4 位数后才会出现单位上的变化,如万、亿)。

BASIC-21 Sine之舞

看到公式应该能联想到递归,可惜公式太抽象了,还不如去看示例。观察示例规律后应该就能写出求 An 字符串的函数了。同理可应用到 Sn 函数上。

BASIC-22 FJ的字符串

这题比上一题好理解多了,仔细观察即可看出规律。每个字符串有一个类似于树形的结构。

BASIC-23 芯片测试

从每个芯片对其它芯片测试的角度出发,有几种情形:

  1. 所有芯片对被测芯片的结果一致。这种情况下无法根据结果找出坏芯片,但由于好芯片数多于坏芯片,因此对被测芯片的结果是准确的
  2. 芯片对被测芯片的结果不一致,且一种判断的个数多于另一种判断。由于好芯片数多于坏芯片,因此占比大的结果是准确的,做出占比小判断的是坏芯片
  3. 芯片对被测芯片的结果不一致,且一种判断的个数等于另一种判断。无法判断结果是否准确,也无法找出坏芯片

示例里面就是属于第三种情形,这种情形下应该如何判断呢?观察发现 1、3 对 2 号芯片符合第二种情形,这样即可判断 2 是坏芯片。因此对于第三种情形的记录无需处理,可以从其它结果入手进行推理。

BASIC-24 龟兔赛跑测试

题目不难,注意仔细读题。另外注意判定的顺序,应该先计算本回合行动完的结果再进行判断,否则会出现隐蔽的错误。

BASIC-25 回形取数

按题目意思做即可,但是有点麻烦。尝试了循环判断方向的思路,在一个用例上面报超时。之后换了个边界检测的思路还是超时。OJ 给的测试结果不是很稳定,有时候可以擦边通过(900 多 ms),有时候就直接运行超时。

参考了网上的思路,有空再研究一下这道题。

BASIC-26 报时助手

简单题,按题目逻辑做即可。注意复制题目字符串的时候要与题目保持一致,不能有空格等,在这里掉了两次坑。ORZ

这道题的逻辑代码写得又臭又长,应该有更简洁的解法。

BASIC-27 2n皇后问题

只要会解八皇后问题的话,这道题其实不难。只需要在八皇后问题的基础上再做一次八皇后选择即可。

BASIC-28 Huffman树

按题目说的做即可。

BASIC-29 高精度加法

按题目要求的做即可,注意右对齐和最高位的进位。

BASIC-30 阶乘计算

这回就需要实现大整数的乘法运算了,难度要比加法复杂很多。可以自己列一个竖式观察乘法的特点,主要是进位需要多注意。

乘法实现的步骤(以128* 256 为例子):

  1. 分拆乘数 256 为 2*10^2 + 5*10^1 + 6*10^0
  2. 将上面的结果分别乘以乘数 128,得到结果
  3. 将分别相乘的结果相加

ALGO-1 区间k大数查询

典型的选择问题,可以使用快速选择算法来解决。但由于快速选择算法是找到 k 个最小数的,需要先将找第 k 个最大数转换为找第 n – k 个最小数, 不过这个位置转换有点绕,在这上面浪费了不少时间。

掉了两个坑:

  1. 快速排序和快速选择虽然名字很像但是逻辑是不同的,写错了
  2. 快速选择使用的位置是相对位置,在绝对位置和相对位置之间转换容易出错

ALGO-2 最大最小公倍数

刚拿到这道题就不自主地开始查各种公倍数公因数怎么获得,然而从最小公倍数的定义出发可知公倍数其实就是 a * b,三个数的话就是 a * b * c。按这种思路,最大的最小公倍数岂不就是 n * (n-1) * (n-2)?

按照这种思路写了个代码后吃了鸡蛋。开始仔细考察可能出错的地方。是否是直接相乘出来的不是最小公倍数?修改后仍然吃鸡蛋。

最后看了锦囊,锦囊肯定了我之前的想法——可惜只完全适用于 n 为奇数的时候(看来都是用偶数测试啊)。

当 n 为偶数时,答案可能是 (n-1)*(n-2)*(n-3),也可能是 n*a*b,其中 a>=n-3。

这句话是什么意思呢?

n * (n-1) * (n-2) 的情况不再叙述。n * a * b 是什么情况呢?

搜索了一下,看到了如下的叙述(出处):

这个优先策略很简单,尽量先选最大的,然后往下选,但是,如果你选了最大的以后,比如例 1 中,选了 6,就无法选择 4 也无法选择 3,甚至 2,所以,这种情况就不能去选择 6,只能退一步选择 n-1

比如假设 n=6,如果我们按照 n * (n-1) * (n-2) 将会得到 6 * 5 * 4,考察 6 * 4 相乘的结果 24,它是一个最小公倍数吗?不是,最小公倍数其实应该是 12。这其中的原因就是因为 6 和 4 都有一个公因数 2(它也是它们的最大公因数)。 通过公式可以算出 24 / 2 = 12 是 6 和 4 的最小公倍数。

既然如此,那我们应该如何得到最大的公倍数呢?最大公倍数的公式是 a1 * a2 / gcd(a1, a2),只要我们选择的 a1 和 a2 的最大公因数为 1,我们就应该能得到最大的最小公倍数。

回到题目,观察 n、n-1、n-2、n-3,可以发现 n 不能整除 n-1 ,即他们的最大公因数为 1;而 n 和 n-2 有可能会出现上述所示的最大公因数不为 1 的情况,因此 n * (n-1) * (n-2) 不一定是最大的最小公倍数;观察 n 和 n-3,好像也不能被整除(然而并不会证明),而 n-1 和 n-3 之间好像也不能被整除。因此应该选择 n * (n-1) * (n-3) 作为最大的最小公因数。

搞明白之后题目就好做了,奇数直接输出 n * (n-1) * (n-2),偶数输出 n * (n-1) * (n-2) 和  n * (n-1) * (n-3) 较大的一个就好偶数应该判断 n 和 n-2 是否可以整除,再根据判定结果决定输出哪一个数。

然而怎么判断 n 和 n-2 是否可以整除呢?

  • n % (n-2) == 2 不行,举一个反例 9 和 7(结果 2)
  • n / (n-2) == 1 不行,举一个反例 6 和 4(结果 1)
  • 获得 n 和 n-2 的最大公因数呢?如果非 1 的话就说明它们之间不是互质关系……然而 n 和 n-2 都是偶数,最大的公因数至少为 2

好像都不行,最后参考了别人的代码,很多人的代码中都提到了将 n mod 3 == 0 作为条件。这是为什么呢?

还是搜索了一番,在这里找到了想要的解释:

如果是偶数的话,如果同时出现两个偶数肯定会不能构成最大值了,因为会被除以 2~~ 分两种情况:
(1) 如果 n 是偶数且不是三的倍数, 比如 8,那么跳过 n-2 这个数而选择 8 7 5 能保证不会最小公倍数被除以 2~~ 所以最小公倍数的最大值为 n * (n – 1) * (n – 3)
(2) 如果 n 是偶数且为三的倍数,比如 6,如果还像上面那样选择的话,6 和 3 相差 3 会被约去一个 3,又不能构成最大值了。那么最小公倍数的最大值为 (n – 1) * (n – 2) * (n – 3)

注意选用数字的类型,应该要选用 long long 或 BigInteger。

 

ALGO-3 K好数

做的过程中发现不允许存在前导 0,必须严格符合给定的位要求。这道题的第一想法是用回溯法来做,然而提示运行超时……

题目的提示是动态规划,由于还没有学动态规划所以也是一脸懵逼。决定尽可能观察规律:

  • 发现只要确定前一位的的数字,这一层的可选数字的可能性也就知道了,这样可以使用乘法来推出种类数,而不需要进行穷举
  • 由于第一位不允许前导 0,因此第一位有 K – 1 种可能
  • 根据前一位的取值,当前位的可能性数量会产生变化,如果前一位是 0 或者 K-1,有 K-1 种可能性(因为与前一位相邻的数字只有一个);如果前一位取值 1 ~ K-2,有 K-2 种可能性
  • 第一位有 K-1 种可能,其中取值 1 ~ K-1,因此第二位有 (K-2+1) * (K-2) + 1 * (K-1) 种可能(1~K-2 有 K-2+1 种可能,剩余的取值为 K-1 的情形有 1 种可能)
  • 设第二位可能性为 P2,第三位有 (P2-2+1) * (K-2) + 2 * (K-1) 种可能

观察可得知:

  • 最后一层的个数仅根据上一位的数字变动,如果上一位的数字是 0 或 进制-1,该层的 K 好数可能数为 进制-1(若上一位的数字是 0,则这一层不能使用 1 作为数字;同理可应用到 进制-1 的情况);反之,该层的 K 好数可能数为 进制-2 。
  • 其它层的 K 好数个数为下一层的累加,再除去上一位数字造成的限制的个数。

最底一层的 K 好数个数规律,红框框出的是不合规格的情况。

可以根据以上的信息列出状态转移方程,最初只使用一个数 i 作为层数,但发现还需要第二个数 j 上一位的数字。最终定义出状态转移方程:

d(i, j) 为第 i 层时,前一层的位数为 j 的 K 好数个数。

  • 最后一层时,d(i, j) = j == 0 || j == radix – 1 ? radix – 1 : radix – 2;。
  • 非最后一层时,d(i, j) 为累加 d(i+1, t) 的和(t 为 0 ~ radix 的整数,并且 t ≠ j -1 或 j + 1)。

以 K = 4,L = 3 举例,根据第一条我们可以推出:

  • d(3,0) = d(3,3) = radix – 1 = 3
  • d(3,1) = d(3,2) = radix – 2 = 2

我们可以发现,第二层的 K 好数实际上是将下一层(第三层)不相邻的 K 好数累加起来。因此第二层的 K 好数个数则分别为

  • d(2,0) = d(3,0) + d(3,2) + d(3,3) = 3 + 2 + 3 = 8
  • d(2,1) = d(3,1) + d(3,3) = 3 + 2 = 5
  • 同理可得 d(2,2) 和 d(2,3)

注意我们在计算第二层的个数时多次用到了第三层的数据,这就是重叠的子问题。如果使用回溯法我们要花额外的时间进行计算。

K = 4,L = 3 的部分情况举例

有了这些,就可以着手从底向上解决题目了。但是我们还有一个问题没有解决。那就是,第一层的该如何表示?

第一层由于没有前一位数,因此无法表示——难道使用d(1, -1)?我们可以使用分拆的思想,将以第零层的根的子树分解成森林,不以第一层的 K 好数个数为答案,而以第二层所有可能的个数的和作为答案。

分拆的思维图

最后注意需要模除相应的数,包括每次填表和累加后都需要模除。否则会出现数据溢出。

ALGO-5 最短路

由于带有负权边,需要使用 Bellman-Ford 算法。实现算法后提交发现运行错误,因此还需要使用队列进行优化。然而还是超时……

看了锦囊提示使用 Dijkstra 带堆优化的算法。 然而 Dijkstra 不是不能运用与带有负权边的图吗?然而发现可以堆优化/优先队列优化的 Dijkstra 可以处理负权边。

由于优先队列在 Java 有现成的容器,于是使用了优先队列优化的 Dijkstra。然而跑来跑去都是运行超时,换用 Map 或 List 优化取边效率也无法通过,只好作罢。

ALGO-6 安慰奶牛

看完题目搞不懂什么时候才应该要回去睡觉……这个题目牵扯到三个方面:

  • 选出最短的路程(也就是生成最小树)
  • 选择休息点
  • 计算时间

生成最小树不多说了,使用 Kruskal 算法即可。

选择休息点就有点麻烦了,因为不知道什么时候才应该回去睡觉(谁能告诉我?),只知道如下事实:

  • (每一天)要和休息点的奶牛交谈两次
  • 出去安慰奶牛走的道路要走两次(即一天中花在这条道路的时间应该按 2 倍算)

从选出最短的路程出发,应该可以使用原本的权值来进行生成最小树操作。选择休息点的时候,基于第一点考虑,可以选择交谈时间最小的节点。

看了看网上各人的题解,大家都在使用 2 * 道路权值 + 起始点奶牛交谈时间 + 终止点奶牛交谈时间作为权值。为什么呢? 2 * 道路权值这一点已经说过了,终止点奶牛交谈时间这也不难理解,但为什么还要加上起始点奶牛交谈时间呢?如果这样做,访问 1 <–> 2 <–> 3 的时候,农场 2 的时间不就被少加了一次?(出发时先安慰农场 1 的一次,到达农场 2 安慰农场 2 一次,接下来从农场 2 到农场 3 安慰 3 一次,返回 2 再安慰一次,返回 1 再安慰一次,总共安慰时间是 2 * C1 + 2 * C2 + C3)。而如果使用上面的算法,总共安慰时间是 (C1 + C2) + (C2 + C3) = C1 + 2 * C2 + C3,少加了 C1 一次。但如果将起始点时间 * 2,又会造成中间点的时间多加了一次。

仔细思考下来发现这种想法关键在于:从 A –> B 来看,单程花费的时间确实是道路权值 + 起始点奶牛交谈时间 + 终止点奶牛交谈时间,但没有计算返回时的时间,返回时的时间包括道路权值 + 起始点奶牛交谈时间,因此应该要加上这两个才对。但如果 A –> B –> C,A –> B 和 B –> C 之间多加的一次 B 点的奶牛交谈时间在返回时被抵消了,因此对于中间点而言可以计算出正确的结果。但是仍然少了一次 A 点返回的奶牛交谈时间。也可以理解为,终止点奶牛交谈时间是为返回时预备的,A –> B 的时间仅仅只有道路权值 + 起始点奶牛交谈时间,而返回时候再加一次道路权值 + 终止点奶牛交谈时间。这样就可以使用递归的思想进行解释:A –> B –> C 时,到达 B 后以 B 作为新的顶点再出发,出发返回到 B 后再进行交谈然后原路返回(或者称作“逆向出发”——B –> A)。

实现流程如下:

  1. 按照新的权值定义,使用算法计算出最小生成树。
  2. 选择安慰奶牛时间最小的农场作为休息点。
  3. 计算时间(新权值总和 + 休息点出边数 * 休息点奶牛交谈时间,注意中间点也需要计算时间)

注意,样例数据缺少一组边数据,数据是 4  5  12。

 

休息点的不同会引起路程的不同吗?

我一直感觉,随着休息点的不同,走过的路程也会不同。

ALGO-9 摆动序列

说是用动态规划求解。但看了题目数据,觉得用回溯法会更简单一些。在这之前,先理解“摆动”是怎么摆动法。

如果第i – 1个数比第i – 2个数大,则第i个数比第i – 2个数小;如果第i – 1个数比第i – 2个数小,则第i个数比第i – 2个数大。

也就是说,设有三个数 a b c,若 a>b,则 c>a;若 a<b,则 c<a。因此,选择最后一个数 c 时,要参考 a 和 b 的大小关系,再从待选择的数中选择合适的数。为了让这条数列尽可能地长,只选择刚好满足条件的 c。应该从待选数字集合中,穷举所有满足条件的 c 组成新的数列并一直递归下去,直到没有满足条件的 c。

提交后提示运行超时,同时内存跑了超多。测试了一下,k=20 的时候跑了好几秒。虽然答案满足题目(拿了 70 分),不过速度太慢。尝试优化了一下,拿到了 80 分但还是提示运行超时。

哈?不就是超时吗,既然你 k 的范围是有限的,我的答案又是对的(只是时间超时)。那么我可以在客户机上面先预先算出来,最后过 OJ 查表不就行了。于是就拿到了 100 分。

重构:动态规划

哈哈,上面的查表法不一定在所有情况下面都适用。为了锻炼自己的能力,还是需要使用动态规划的思路来做这道题。

ALGO-10 集合运算

还算简单,自己琢磨琢磨应该能做出来

ALGO-11 瓷砖铺放

看到题目想到两个类似的题目——斐波那契数列和上楼梯,要求使用递归解决问题,那我们可以使用与求斐波那契数列类似的办法进行解决。即在摆放了长度为 n 的瓷砖的状态下,摆放方法的总数为摆放长度为 n+1 的方法数和摆放长度为 n+2 的瓷砖的方法数的和。设 d(i) 为摆放了长度为 i 的瓷砖的状态下,摆放方法的总数,d(i) = d(i+1) + d(i+2)。并且d(n) = 1,n 为题目要求的长度(因为摆放了这个瓷砖就满足了题目要求的长度,算作一种办法)。当 i > n 时,d(i) = 0(因为超过了题目要求的长度,不能算作一种办法)。

ALGO-12 幂方分解

先搞明白题目的意思,题目还算好做。由于数必定大于或等于 2^n,可以从 n = 15(2^15 = 32768,题目给出的数字≤20000 ) 开始往回遍历,一旦给出的数字大于等于 2^n,就将数字分解出来继续遍历。那么对于次方的分解应该在哪里做呢,最初是打算得到所有的次方数后再对括号进行解析分解替换,但其实可以在分解过程后得到一个次方数后立刻递归进行次方的分解,这样就可以得到分解了的字符串并立刻添加到括号中形成结果。

注意定义递归的边界。

ALGO-15 旅行家的预算

既然是要最小的费用,那么就去花费最低的油站去加油就好了。但是在到达花费最低的那个油站(设为 i)之前,要在起点与 i 之间的最低价油站(设为 j)加好从 j 到 i 的油,不难发现可以使用递归求解。但是注意还有油箱容量这一限制。

可以将出发点和终点都抽象成油站,出发点可以抽象为油站 0,终点可以抽象为油站 n+1(设有 n 个油站),这样子就可以进行统一化处理了。

提交后只拿到了 25 分。发现是没有处理途中油站为 0 和无解的情况。处理没有油站的情况拿到了 50 分,还剩下无解的情况,无解是什么情况呢?假设途中没有油站,并且在出发点加不到到终点的油量,即为无解。扩展开来就是在途中的任意油站加不到到达下一个目的地的油量(由于油箱油量的限制)即为无解。处理无解情况后得到了 75 分。

继续检查,发现还忽视了一个变量——行进到某个油站的油量,假设距离很长,途中只有一个油站,到达终点的油量超过了油箱容量,那么要想到达终点,就必须在途中加油,但到达途中加油站时,油料并未完全消耗殆尽,此时盲目地加油就不可取了。对这种情况进行修正后仍然只得到了 75 分。查看了数据后发现,我的程序太不贪心了——在最低价格不是加满油而是只加刚好能到达下一目的地的油量。又是油量限制方面的问题,处理后得到满分。

ALGO-17 乘积最大

仔细观察数字可以看出对于数字为 n,使用 k 个乘号的情况下,可以将状态转移方程函数定义为 d(n, k)。现在应该怎么描述这个方程呢?

先定义边界条件——当 n 只有两位数且有至少一个乘号可用的时候,最大乘积为两个一位数相乘。而当没有乘号可用时,直接返回该数。考虑题目 d(312, 1) 的情况,数字的长度为 3,因此可以在 3-1=2 个位置里面插入进行枚举。因此初步的转移方程为 d(n, k) = max(i * d(j, k-1)),其中 i 为乘号左侧的数,j 为乘号右侧的数。

使用输入样例测试时发现还需要定义多一个边界:当 n 只有一位数并且还有乘号可用时,应该取负无穷,因为使用的乘号既不能多也不能少。

提交之后竟然满分通过……真是太感动了TAT。

ALGO-19 方格取数

看完题目觉得“取走后的方格中将变为数字0”这个条件没什么用,整个题目可以抽象为一个最长路问题。然而后面谈到“此人从A点到B 点共走两次,试找出2条这样的路径,使得取得的数之和为最大。”,也就是说第一次走过的路径在第二次不会再走。

不管怎么样,先考虑第一次的情况,每一次行进都必定向右边行进一格,但是在 x 轴上可以选择 x 或者 x+1,行进可以选择两种方向:向下或者向右。有一种 TSP 动态规划问题的味道?

定义状态转移方程为:设 d(r, c) 为从 r 行 c 列为终点所取得的最大值,则 d(r, c) = max(d(r, c-1), d(r-1, c)) + a(r, c),a(r, c) 为 r 行 c 列的数字。

使用逆推法算出第一次的总和为 36,不知道是否正确。但在第一轮之中应该将取到的数改为 0。问题来了,应该将这个过程放到哪里呢?貌似不能放到每次迭代求 d(r, c) 的过程中,否则会把没有选择的值也设为 0。因此只能在决定最终路径后再将路径上的数字改为 0,涉及到了答案的回溯,比较麻烦。

提交后得到了 80 分,想不出来哪里错了(实现太复杂),看了一下数据,是路径选择上面的问题:第一轮选的太好了,把最大的数都给选走了,导致第二轮不能选到最多的非零数。为了选到最多的非零数,应该优先考虑往下走

ALGO-22 数的划分

 

ALGO-33 数列

看题目说明就有点二进制的感觉,30、31、30+31这些可以对应二进制中的 1、10、11。

那问题就很简单了,既然 N 为要求的位置上的数。那么先将 N 转为二进制,接下来使用 k 作为权重值,将这个“二进制”数转为十进制即可。

提交后拿到了 90 分,还有 10 分到底是怎么回事看来看去没有头绪,看了输入输出数据也没发现有什么问题(输出和程序给出的不匹配)。

搜索后发现是数据超出了 int 的范围,参见这里这里这里。目前准备将错误提交给练习系统管理员。

ALGO-38 接水问题

直接用循环计算每一秒的情况即可:对于已经装完水的水龙头,将下一个人补上,直到没有要继续装水并且所有人装水完毕,输出当前的时间即可。

ALGO-39 数组排序去重

水题,去重可能要花点心思,但也不难。

ALGO-42 送分啦

还真的是送分……

ALGO-48 关联矩阵

关联矩阵是什么?简单地说,就是节点与边的关联次数的矩阵。如果节点 i 与边 j 有一端端接,mij 就等于 1。如果在有向图中,出边表示为 1,入边表示为 -1。了解了这些题目就很简单了,只需要根据输入的数据,对矩阵元素进行适当的加减即可。

ALGO-49 寻找数组中最大值

水题

ALGO-57 删除多余括号

 

ALGO-58 字串逆序

水题

ALGO-59 快速排序

直接写普通的快速排序会运行超时,所以需要优化一下。

天哪,我已经连快速排序都没法手写了……

ALGO-61 奇偶判断

水题

ALGO-62 平方计算

水题,但是如果取余的不是二次方的话,可以使用 ab mod m == (a mod m)(b mod m)mod m 来计算(在《算法竞赛入门经典》第十章有讲)。

ALGO-63 乘法表

水题

ALGO-64 大小写判断

水题

ALGO-67 最大值与最小值的计算

水题

ALGO-68 判定数字

水题

ALGO-69 字符串逆序

水题

ALGO-70 最长字符串

水题

ALGO-71 比较字符串

水题,但是可以多尝试几种解法

ALGO-72 成绩的等级输出

水题,不过被题目的数据坑到了……

ALGO-73 统计字符次数

水题

ALGO-82 输出米字形

先将数组用“.”填充。接下来计算出中心点和填写在中心点的字母,然后从中心向四周循环填写对应的字母即可。为了提高效率,可以在一个循环内对两个方向进行填充,或者用绝对值简化字母公式。

ALGO-83 阶乘

要求算出 n 阶乘最右边非 0 的数字。我的策略是从 1 到 n 进行相乘,每一次相乘后去掉末尾的 0,并对去零后的结果取最后一位继续相乘。但是这种办法在 n≤24 之前才有效,n≥25后就无效了。后来还是允许去零后的结果不超过 100000,这样子就可以计算出正确的结果。尝试允许去零后的结果不超过 100000,正确解的范围扩大到了 n≤40。

我认为我的这种策略总体上是正确的,只是细节有误,所以开始观察 24! 和 25! 的差别。按照前面的策略,取 24! = 620448401733239439360000 的后四位数 3936,乘以 25,得到 98400,这里是可以得到 25! 的最后一位数 4 的。观察运算过程:

3 9 3 6

*     2 5

1 5 0
7 5
2 2 5

7 5

9 8 4 0 0

可以看到在6 * 25 和 3* 25 时产生了进位,也就是说,随着上一个阶乘的最后一位数得到 10 的倍数,最后一个非零位就会在左边出现,并由左边的一位决定。反映到例子中,6 * 25 = 150,此时最后一位非零位就从个位跑到了十位上,受到 3 * 25 的影响,恰巧 3 * 25 = 75(这里由于位置的关系应该乘以 10),再加上 150 就等于 75*10 + 150 = 750 + 150 = 900,此时最后一位非零位又到了百位上,受到 9 * 25 = 225 的影响,再加上 900 就等于 225 * 100 + 900 = 23400。这一次,非零位的位置没有再变动,因此可以取百位 4 作为最后一位非零位。

搞清楚了过程,应该怎么使用程序代码描述出来呢?由于后续的计算需要使用到末尾的 n 位数,因此应该保留相乘后的结果的 n 位数(即对运算结果取 10^n 的模),我就规定 n = 5 好了(随便取的)(等等,那这和上面的解决办法有啥不同)。其次,修改运算过程,即每一次都先用最后一位进行运算,若运算后的结果为 10 的倍数,在去掉末尾的 0 之后,再加上第二位相乘的结果。

修改之后好像还是一个样子……在 n≤40 时正确,往上就不正确了,这应该是允许保留更多位数导致的。最后发现是 Windows 的计算器精度不够高导致的,到网上搜了阶乘表,核对后正确。提交后满分通过。

当然了,这事还没完。ACM 题目有一种方法就是查字典,因此我们可以将 1 到 100 的最后一位数先预先计算出来,写到一个字典(数组)里面,运行的时候直接去这个字典里面查询即可,避免运算。提交后依旧满分,但是计算性能的提升只有 20ms 左右,看来好像不那么灵啊。

ALGO-84 大小写转换

水题

ALGO-90 出现次数最多的整数

蛮简单的一道题,由于是从小到大输入,因此可以不用存储输入,直接记下连续数字的出现次数即可。

不过还是掉坑了……边界条件没有处理好,题目的测试样例也要求处理数字个数为 0 的情况。

ALGO-91 Anagrams问题

水题,统计两个单词的每个字母的出现次数再比较即可。

ALGO-95 2的次幂表示

同 ALGO-12

ALGO-98 数位分离

水题

ALGO-100 整除问题

水题

ALGO-101 图形显示

水题

ALGO-102 数对

水题

ALGO-103 完数

按题目说的做即可

ALGO-104 阿尔法乘积

按题目说的做即可,有两点要注意的:

  1. 计算阿尔法乘积的过程可以(也应该使用)使用递归
  2. 输入数据应该使用 long(还好给的数据直接在 int 下面就报错了,否则是要找老半天啊……)

ALGO-105 黑色星期五

计算出要计算的日期到 1998 年 1 月 1 日的相差日数,并模除 7 即可得到那一天是星期几。但是要注意计算 1 日到 13 日的相差日数的时候会有重复(1+0 是 1 日,1 + 13 是 14 日),因此要减去 1 日(加上 12 日)。

PS:活用电脑的日历功能。

ALGO-110 字符串的展开

按题目说的做即可,难度不大。但需要细心一点,做题的时候因为漏掉了一些条件而导致失分。但是这题最坑的是要求重复检查——“a-b-c”要匹配到“a-b”和“b-c”并且不能有重复的 b,这样子就很坑了嘛。

ALGO-117 友好数

根据题目条件需要判断两个数的约数和是否等于另外一个数,怎么求得约数呢?观察给出的约数表可以看到约数范围是 1~n/2,因此可以得出,如果 n 可以整除 1~n/2 之间的数,那么那个数就是约数。

ALGO-119 寂寞的数

要求输出小于等于 n 的寂寞数,根据题目有正推(根据 n 算出 d(n))和逆推(根据 d(n) 算出 n)两种思路。当然是正推比较好做啦,直接使用 1~n 作为生成元,对于有 d(n) 的值做上标记。最后将没有标记的 n 的输出即可。

由于 d(n) 会大于 n,因此需要注意范围溢出的问题。

ALGO-120 学做菜

水题,循环匹配即可

ALGO-122 未名湖边的烦恼

为了避免“没有冰鞋可租的尴尬场面”,最好的情形当然是全部还鞋的人都先还鞋,然后借鞋的人再来借;最糟糕的情形是前面刚还了一双,后面一个人立刻就借走了。如果用字母表示,设 r 为还鞋的人,b 是借鞋的人,在 m = 3、n = 2 的情形下,最好情形是 rrrbb,最坏情形是 rbrbr。那么题目就是在问 rrrbb~rbrbr 之间有几种排列方法?

统计一下  rrrbb~rbrbr 之间可能会出现的序列:

  • rrrbb
  • rrbbr
  • rbrrb
  • rrbrb
  • rbrbr

有两种思路:

  • 将借鞋的人抽取出来,在队列只留下还鞋的人,再将借鞋的人插入到合适的位置。
  • 将还鞋的人和借鞋的人与之匹配(允许还鞋的人匹配不到借鞋的人,但借鞋的人必须与一个还鞋的人匹配),我们可以根据这种思路构建排队序列。

根据后一种思路,可以使用增量构造法逐步构造队列,并且对队列的种类数进行计数。

ALGO-123 A+B Problem

水题

ALGO-124 数字三角形

相当熟悉的题目,题目要求求出经过的路线总和最大,因此可以转化为最长路问题,使用动态规划解决问题。

状态转移方程如下:

d(i, j) = max(d(i+1, j), d(i+1, j+1)) + a(i, j);

其中 d(i, j) 代表从点 i, j 出发能走到的最长路径(数字综合),a(i, j) 代表 i, j 点的路径长度(数字)。

接下来使用填表法自底而上计算出最长路 d(0,0)。一次AC。

ALGO-129 特殊的数字四十

水题

ALGO-139 s01串

递归还是蛮简单的,不过替换的时候要注意不能叠加替换——0 变为 1 后不能继续继续变为 01。当然了,可以不用递归,使用循环就可以搞定。

ALGO-143 字符串变换

前 4 种操作应该还是很简单的,第 5 种操作需要花一点心思,要维护一个连续计数来判断是否要插入缩写。

ALGO-145 打印下述图形

水题

ALGO-147 水仙花数

这个题目都做烂了吧……

ALGO-150 递归求二项式系数值

水题

ALGO-156 表达式计算

题目不难,应该在学习栈这个数据结构的时候都遇到过了。需要先将中缀表达式转换为后缀表达式(逆波兰式)再进行计算。

但是在编写中缀转后缀的这个过程中就很坑爹了,首先由于我是诸位读取字符串的,所以读取到多位的数字就需要花点心思,不过也不难。

难的是第二步,关于逆波兰式的转换,我是参考《大话数据结构》第二版中的说明:

从左到右遍历中缀表达式中的每个数字和符号,若是数字就输出,即成为后缀表达式的一部分,若是符号,则判断其与栈顶符号的优先级,是右括号或优先级低于栈顶符号(乘除优先加减)则栈顶元素依次出栈并输出,并将当前符号进栈,一直到最终输出后缀表达式为止。

这段话说的没有问题,但是表述不清:如果不是右括号或者优先级高于栈顶符号,那要怎么做呢?

因此对这段话做一些补充:

  • 若符号是右括号或优先级低于栈顶符号,则栈顶元素出栈,重复这一步直到前述条件不满足
  • 将符号入栈

这里又涉及一个优先级的概念,大家都知道乘除优先级高于加减,但括号呢?毫无疑问,括号的优先级高于乘除,但如果将栈中的括号与读出的加减乘除比较,会直接判断成“优先级低于栈顶符号”,因此需要做特别处理。

做题时参考了这里,步骤说的挺详细的。

ADV-71 判断回文

水题

ADV-141 判断名次

既然已知 1、3、5 都说了假话,那么直接将其说的话取反,配合其它条件应该就可以获得可能的名次了。但是将条件转换为可能的名次就麻烦了,我想到的一个办法是,构建一个数组,如果某一个人可能获得对应的名次就标记为 1,否则为 0。

但是上述方法在没有提供某个人的信息是就会出现某个人可能什么名次都得不到的情况(因为开始的时候假设每个人都不能得到任何名次,后续根据条件再补足)。所以应该根据真话的反条件,禁用某人不可能得到的名次。

计算出来的结果不对,发现自己把题目理解错了!这里的奇数名次都是不能预先得知的。

PREV-1 核桃的数量

这道题其实就是让求最小公倍数,为什么呢?看看条件:

  1. 各组的核桃数量必须相同
  2. 各组内必须能平分核桃(当然是不能打碎的)
  3. 尽量提供满足 1,2 条件的最小数量(节约闹革命嘛)

条件 2 规定了某一组的核桃数量必须是该组人的倍数。又由于条件 1 规定每个组的核桃数必须相同,因此各组的核桃数应该是三个组每个组人数的倍数。设各组的核桃数为 x,则 x 应该是 a, b, c 的倍数。也就是 x 是 a, b, c 的公倍数。

结合条件 3 即可得出 x 应该是 a, b, c 的最小公倍数的结论。

PREV-2 打印十字图

水题。只要观察总结规律,并且耐心实现即可。

PREV-4 剪格子

只要从左上角的格子不断加入格子,使得加入的格子的总和和没有被加入的格子的总和相等即可。使用 DFS 搜索可破。

加入的格子的总和大于没有被加入的格子的总和时继续搜索没有意义(因为格子总和只增不减),可以进行剪枝。

PREV-5 错误票据

水题。判断重复的元素可以得出重号的,而要找出缺号的,则可以排序然后从小到大遍历,当前数字和前一个数字的差不为 1 的数字即为缺号的后一个数字。

PREV-6 翻硬币

由于是求最少翻动次数,可以先逐位比较字符串,确定一个翻动范围,翻动范围外的硬币不能翻动,避免不必要的翻动。

如果翻动范围只有 2 枚硬币,那翻动次数无疑就是 1 了。

如果翻动范围内有 2 枚硬币的状态发生了改变,那翻动次数就是 n-1。

但如果有 3 枚硬币的状态发生改变呢?根据模拟,好像并没有解。

4 枚呢?如果他们有相邻的一对,那么那一对只需要翻动一次即可。

假如不相邻呢?

假如我们要将 XXXXXXXX 转换为 OXOXOXOX

第一种方法是:
OOXXXXXX
OXOXXXXX
OXOXXXOO
OXOXXOXO
OXOXOXXO
OXOXOXOX

一共 6 步。

这是最短的吗,左边确实是最短的,右边我们可以减少两步:
OOXXXXXX
OXOXXXXX
OXOXXOOX
OXOXOXOX

其实这也和上面说的边界理论所符合,只翻动边界内的硬币,边界外的不需要翻动。

假如是不平衡的呢,比如要从 OXXXXXXO 转换为 OXOXXOXO。从边界角度出发,我们需要将中间的 XXXX 变为 OXXO。

那应该是:
OOOO
OXXO

还是:
XOOX
OXXO

然而步数都一样,随便哪种都行。

那如果是 XXXXX 到 OXXXO 呢?

除了:
OOXXX
OXOXX
OXXOX
OXXXO

还有更好的办法吗?比如:
XOOXX
OXOXX
OXXOX
OXXXO

然而步数都一样。

这样推下来,好像对于可以交换的情况,排除成对的情况,最优步数好像都是 距离 – 1。为了节省步数,我们需要让不成对的两个硬币组成距离最近的一对,例如之前的 XXXXXXXX 转换为 OXOXOXOX,应该将 OXOXOXOX 组合成对,而不是将 OXOXOXOX 组合成对。

这样子做了之后,提交 OJ 只拿到了 66 分。是否还存在一些情况使得这些成对没有最优呢?例如 OXXXXXXOXXOXXXXXXO?如果按从左到右的遍历方法,将会是 OXXXXXXOXXOXXXXXXO 而不是  OXXXXXXOXXOXXXXXXO。然而后一种不是最优的。

最后查看了锦囊,思路是正确的,后来查看了样例数据,发现是成对的情况使得后面组合成对的时候反而不是最优的,去掉检测成对的情况就正确了。

为什么检测成对反而是画蛇添足?

出现错误的是这一组数据:
oooo****o*****oo*****oooo***oooooooo*******
*oo***oo
oo*****o****o****oooooo***oooooo****o**
0010010101000001100000100010001001111000000000000100

第三行为出现更改的数组,1 表示两个字符串上的两位字符不相同。

先检测成对的话,数组的变化是这样的:
oooo****o*****oo*****oooo***oooooooo*******
*o***oo***o****
o****oo*****oooo*oo***o*ooooo*******
0010010101000001100000100010001001111000000000000100

接下来组合成对:
o1o1o*22o*****o****oo3****3*ooo4o*oooooooo*****4
000000000000000000100000000000000000000000000

注意第四对,由于中间的成对 1 被消掉因此第四对的距离增长了。

如果不消去成对,会怎么样呢:
o1o1o*22o****o3*3****oo4****4*ooo5o*5*6*6o7o*o*ooooo*****7**
0000001000001 1 000000000000011 1 1 00000000000000

第一组和第二组并无变化,第三组刚好是直接前后关系因此也无变化,第四组无变化。直到第五组,第五组的距离为 3,第六组成对距离 1,第七组距离 13。而消去成对的最后一组距离 19,第五组、第六组、第七组的距离总和为 17,差值 2。而消去成对的结果为 31,不消去的结果为 27,31-27=4,还有 2 个距离去哪了?(成对消去的距离忘记统计了……)

仔细观察,可以发现检测成对的话,会使得最后一对翻转的过程中,重复地翻转过了成对的地方,即:
10000000000000000001
01000000000000000001
00100000000000000001
00010000000000000001
00001000000000000001
00000100000000000001
00000010000000000001

00000000000000000011
00000000000000000000

相比于:
10011110000000000001
0
1011110000000000001
0
0111110000000000001
0
0001110000000000001
0
0000010000000000001
0
0000001000000000001


00000000000000000000

可以看到在翻转中间的 4 个,后者只需要 2 次翻转(应该是 3 次翻转的,最后一次翻转把下一位的也一并翻转了 ),前者需要 4 次。

PREV-7 连号区间数

读完题目后就直接去实现并查集了,后来对比样例输入和输出才发现理解得不对……

重新读了题目,大致了解了流程:将数组分为不同的子集(不含空集),然后对这些子集中的元素进行排序,如果排序后这个子集的数字是连续的,那就可以被称为一个连号区间。

例如样例输入 3 2 4 1,可以分成 {3}、{2}、{4}、{1}、{3 2}、{2 4}、{4 1}、{3 2 4}、{2 4 1}、{3 2 4 1} 这些子集。

  • 由于 {3}、{2}、{4}、{1} 只有一个元素,它们都是连号区间。
  • 由于输入是 1~N 的全排列,那么 {3 2 4 1} 这个子集排序后必定是 1~N 的连续的升序排列。因此这个子集必定是连号区间。
  • {3 2} 排序后变为 {2 3},是一个连续的升序排列,是一个连号区间。
  • {2 4} 排序后变为 {2 4},虽然是升序排列,但是并不连续,不是一个连号区间。
  • 同理可得 {4 1}、{2 4 1} 不是连号区间,{3 2 4} 是连号区间。
  • {3}、{2}、{4}、{1}、{3 2}、{3 2 4}、{3 2 4 1} 是连号区间,一共 7 个。

实现的流程也呼之欲出了:

  1. 枚举长度 2 ~ 数组长度-1 的子集
  2. 对这些子集排序
  3. 判断是否连续
  4. 若连续,连号区间数 +1
  5. 加上单个元素的子集数(数组长度)和 1(所有元素的子集)即为答案

枚举子集本来想使用《算法竞赛入门经典》中的二进制法,但发现如果 N = 50000 的情况下数据无法 hold 得住。于是换用位向量法。但是位向量法会生成位置不连续的组合,因此需要做一些调整。

第一版本的代码使用的是遍历来检查是否连续,提交后提示运行超时。看来应该让并查集出场了。运用了并查集后,还是运行超时,和我预先的估计一样——都是遍历,只是判断的方式不同,看来要转换思路才行。

看了别人的思路才发现自己真的想多了……(出处

思路:在某个区间内如果它的最大值减去最小值等于它的区间长度,那么它就是连号区间!

真是想多了,这样子连续的判定完全是 O(1) 的事情了,不需要 O(n)。

更糟糕的是,更换连续判定代码后仍然超时,发现是生成子集的过程太慢了。

重写好了,这回不玩什么高深的黑科技了,老老实实用最原始的技术:

  1. 使用循环枚举子集
  2. 使用循环找出最大最小数
  3. 判断是否连续
  4. 若连续,连号区间数 +1

不用半个小时就实现完毕,提交后一次正确。自己的思路还是要多拓宽才行啊。

PREV-31 小朋友排队

读完题目后觉得应该是贪心法无疑。由于“如果有两个小朋友身高一样,则他们谁站在谁前面是没有关系的。”,同高度的应该避免交换。又由于“当要求某个小朋友第 k 次交换时,他的不高兴程度增加 k。”因此交换距离最长的应该先交换。

实现流程如下:

  1. 检测每个小朋友应该交换的距离
  2. 选择距离最长的交换

仔细想下来又觉得不一定对…… 但不管如何,先实现了再说。

实现了一个 O(n2) 的算法提交后,提示运行超时。将数据输入进去发现是交换用的算法有问题。费力气修复后发现与答案有出入,应该是思路还存在问题了……

换了一种类似插入排序的思路,答案接近了许多。在这上面改进可以得到类似鸡尾酒排序的思想。然而还是不行。

本文采用 CC BY-NC-SA 3.0 协议进行许可,在您遵循此协议的情况下,可以自由共享与演绎本文章。
本文链接:https://blog.codeingboy.me/thoughts-of-lanqiao-exercises/

发表评论

电子邮件地址不会被公开。 必填项已用*标注