Yao Lirong's Blog

Yao Lirong's Blog

Innovation For Everyone

loading
P1162 填涂颜色

题目来源:洛谷P1162 填涂颜色


  1. 如果被包围的部分没什么特点,那么就可以看看其他部分有没有什么特点,本题中就是可以从外围开始搜索,搜到墙就停下,最后没被搜到的部分就是被墙包围的部分
  2. 为了防止外围起点就是墙,或者是外围的0被墙分为好几部分导致我们无法搜索到被分割的部分,可以多开一圈数组,使得外围相互连接起来,确保不被包围的0一定可以被搜到
P1141 01迷宫

题目来源:洛谷P1141 01迷宫


BFS找连通块

  1. 连通块肯定还是DFS找得快,因为一开始不知道什么是连通块所以写了个BFS

  2. 搜索连通块不需要记录从某一个点出发最远能到达哪个点(BFS搜索最短距离),只需要记录从某一个点出发一共经过了多少个符合条件的点就行了(BFS搜索连通块),因为如果A和B联通,B和C联通,那么A和C必然联通,所以一次搜索能达到的所有点必定在同一个连通块内

P1019 单词接龙

题目来源:洛谷P1019 单词接龙


调了好几天,最后请教了醉神(@magolor),十分钟给我调好了…

  1. 这个程序一个问题就是循环根本就不会吧dict全循环一遍,那可能就是初始化出了问题: m=pointer 的位置,当时记得应该写一个副本 m 代替 pointer 被改变,但是写着写着忘了 m 具体应该在哪被初始化了,问题就出现在这
  2. 回溯的状态:一定要明确回溯应当回溯到具体那个状态,是ans_temp已经被改变的状态吗?还是未改变的状态?本题中是ans_temp未改变的状态
P1101 单词方阵

题目来源:洛谷P1101 单词方阵


dir 这个数组是很好用的,不需要为8个方向特意写8个不同的函数,只需要写一个函数但是改变取哪一个dir[i]来判定哪一个方向符合条件就行了

P1219 八皇后

题目来源:洛谷P1219 八皇后


我的解法

自己的程序出现的几个问题:

  1. 对角线表达式太过复杂,各层绝对值都可以简化,应该相信大部分情况下复杂的都是错误的
  2. 不需要记录这一行放没放过棋子,因为我们是按照一行一行的顺序放过来的,上一行必定有棋子,下一行必定无棋子
P1031 均分纸牌

题目来源:洛谷P1031 均分纸牌


标解

注意本题中平均数的运用

首先,一定要想到每堆排的张数减去平均张数,这样,题目就变成了移动正数,加到负数中,是大家都变成了0,这就意味着成功了60%!!!!(关键)。以例题来说,平均张数为10,原张数变为-1,-2,+7,-4,因为没有为0的数,所以从最左边出发,将-1移动到-2中,变为0,-3,+7,4,再讲-3向右移动……一次类推,直到全为0为止。没移动一次,步数便加1。关键是,负数怎么移动,其实,移动-x张牌,其实就是从另一堆中移动x张牌,步数相同。还有就是要过滤0,如排数为4,4,2,6,则减去平均数后为0,0,-2,2,就要从第三对开始移动。注意有些0是不能过滤的,如1,0,1,-2中的0。还有就是每次移动好都要过滤。如-2,2,1,3,-4,第一步后变为0,0,1,3,-4,可以省略第二堆的移动。

P2678 跳石头

题目来源:洛谷P2678 跳石头


这是一道标准的 “最大值最小”或“最小值最大“ 的题,遇到这种题,我们就可以使用 贪心+二分查找 的方法来做

二分答案/二分查找

有序(单调)的,有界的就可以用二分法查找。

P1090 合并果子

题目来源: 洛谷P1090 合并果子


一维数组做法

本题是一个简单的 Huffman树。Huffman编码 在 UTF-8 & Unicode 中都有它思想的体现,即出现频率高的编码长度短,出现频率低的编码长度长,用以缩短整体编码长度

这里我也运用了前面 P1309 的思想:因为每次需要重新排序的时候只有一个数据需要被插入整个数列当中,所以并不需要假定数据无序的 quick sort,反而是线性的排序更快

P1309 瑞士轮

题目来源:洛谷P1309 瑞士轮


  1. 胜者组和败者组分别是有序的,使用 mergesort 将两个有序同向数组进行归并(严格上来说不是归并排序),大大降低了时间复杂度 = O(n)。如果我们使用 quicksort,则默认整个数据是无序的,对每个数据都重新排序所以会超时
avatar
姚立嵘 Yao
让每个人享受科技的乐趣 (Innovation For Everyone)