2021.2.4做题小结

2023-12-02 08:35:40

题意：RT

思路：模板题

注意细节啊，卡了好久

题意：给定一张N个点M条边的有向无环图，分别统计从每个点出发能够到达的点的数量。

思路：f(x)表示x能够到达的点的集合，用 N 位二进制数（bitset）存储每个 f(x) ，其中第 i 位表示 x 能否到 i。知如果有一条边 (u,v) 则 v 能到达的点 u 一定也可以到，所以 f(x)|=f(v)。记忆化搜索可做

或者先按照拓扑排序算法求出拓扑序，然后按照拓扑序的倒序进行计算

思路：深搜裸题

题意：给定一个不完整9×9 数独，未填部分用0表示，恢复数独。

思路：深搜，判断在那个方格值得注意：int pos1=ceil(x/3.0);int pos2=ceil(y/3.0);(pos1-1)×3+pos2;即为宫格标号。

注意：当跳转行的时候，不仅考虑下一行，还有考虑上一行

题意：给定一个数n，要找出一个最短的序列，满足： 1、第一个元素为1，最后一个元素为n 2、序列为升序 3、每个元素都是由它之前的两个元素（可以是同一元素）相加得到

思路：迭代加深，当搜索树的分支随深度增大得很快的时候，最适合用迭代加深

这题正好符合迭代加深的要求：搜索树每个节点扩展的情况很多，且答案节点位置较浅。

用序列中已有的数去构造后续的数，一次dfs只构造dep个。有一个强剪枝是ans[i]<=ans[i-1]×2，若已知ans[k]，迭代加深的最大深度为maxd，则后面最多还有maxd-k项，也就是若 ans[k]×2^k 小于 n 则在maxd次之内一定找不到答案

题意：从给定的 N 个数中选择几个，使它们的和最接近 W

思路：搜索选/不选当前位置的数-->2^45的复杂度，太高

观察部分分，发现 2^26 的复杂度是可以过的，所以考虑折半搜索，将礼物分成两半。

首先，搜索出从前一半礼物中选取若干个，可能达到的 w 之间的所有重量值，存放在 s 数组中，并对 s 数组进行排序。然后进行第二次搜索，尝试从后一半礼物中选出一些。对于每个可能达到的重量值 val，在 s 数组中二分查找 <= w-val 的数值中最大的一个，用二者的和更新答案即可(蓝书p112)

注意：两次dfs的函数名不要写混了！（调了我好久）

思路：多源bfs，目的是保证队列的单调性

思路：step[x][y][statu]记录从初始位置到达当前位置，当前形态的最少步数，bfs硬刚即可

注意：方向数组的运用

码农公寓