BZOJ4179 - B

今天模拟赛的第二题,还是大水题,但是由于 SPFA 打错调了好久,还有这个 SB 出题人怎么说都不说一句读入的 $L$ 是 long long 范围的啊,你™咋不上高精

好了,回归正常的题解。本题可以理解为 POI2000 病毒 的加强版(连样例都一样),于是按照惯例,我们只需要建造一棵 AC 自动机。如果能够找到环,那么一定能够产生无限长度的答案串,直接输出 Yes 即可。否则就是一棵 DAG ,跑一下 SPFA (或 BFS)求出最长的答案串,和要求的 $L$ 比较一下就好。

我不会说我写了个 SPFA 还写挂调了两个小时的…

洛谷2962 - 灯

一道非常神奇的题目。

尽管洛谷题解给的都是高斯消元,但实际上这题“普通”的DFS就可以AC。

因为直接DFS一遍的复杂度高达 $O(2 ^ n)$ ,所以我们从两边开始搜索,并把状态存在map里,复杂度降低为 $O(n \times 2 ^ {\frac{n}{2}})$ ,可以水过此题。

LJOJ1244 - 埃及分数

您可以去 Vijos 上搜索此题,不过温馨提示, Vijos 的数据是错的,详情可以参考那题的讨论。

这是一道IDA*经典题,集成了启发式搜索迭代加深的特点进行剪枝。

  • 迭代加深
    本题中,我们限定DFS搜索的层数,如果超过这个层数,就进行剪枝。

  • 启发式搜索
    我们设立一个估价函数,考虑最优情况下的步数。
    本题中我们按照分母从小到大的顺序来DFS埃及分母,所以之后遇到的值就必定大于当前取到的值。
    我们可以通过这个特性来写估价函数,即(a / b) / (1 / u)(其中a / b表示当前的值,u表示剩下能够取到的最小分母)
    做其他题目时一定要注意估价函数所估计的值之多劣于实际情况,而不能比实际情况更优

洛谷2996 - 拜访奶牛

首先,这题无法用贪心实现,下面是一个反例:

贪心反例

贪心的话最大值是 $5$,然而可以在中途放弃一个点从而取到最大值 $6$ 。

我们使用 $f[i][0]$ 来表示到第 $i$ 个点但不取这个点所能获得的最大值,用 $f[i][1]$ 表示到第 $i$ 个点且取这个点所能获得的最大值。

先将每个点都DFS遍历一遍,在回溯时进行DP( $u$ 是当前节点,$G[u][i]$ 是孩子节点):

  • 如果当前节点不选,那么孩子节点选或不选均可
    $f[u][0] += max(f[G[u][i]][0], f[G[u][i]][1]) $

  • 如果当前节点选中,那么孩子节点只能不选
    $f[u][1] += f[G[u][i]][0] $

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×