记录一些简短的题解,部分内容可能来自之前的 旧博客 ,内容不完整,如果必要您可以前往旧博客查看。 出于时间原因很可能没有代码,至多只有片段,如果你需要我的代码,可以联系我的 QQ 或者邮箱,可以在 关于 页面找到。

CF1105E Helping Hiasat ▷ 2019-02-07

可以发现,在两个 1 操作之间的人中最多满足一个。我们可以两两连边,这样问题就转换为最大独立集问题,按照套路此时我们作补图,将最大独立集转换为求补图最大团。使用 Bron Kerbosch 即可。

CF1100F Ivan and Burgers ▷ 2019-02-06

整体二分,注意不能用多个线性基来更新一个答案。

洛谷3601 签到题 ▷ 2019-02-06

考虑到一个数只能被小于根号的质数筛到,暴力做即可。

洛谷2996 拜访奶牛 ▷ 2018-07-06

贪心的话最大值是 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]

洛谷2921 在农场万圣节 ▷ 2018-06-29

可以看做一张有n个节点的图,每个节点有且仅有一条向外连接的边(可以连自己)。那么图中只可能是环与链的组合。而且链的终点是环,进入环后就不会从环中出去,故一个链只可能接一个环,一个环只可能被一或多的链接。

故我们可以把整个分隔为一个个的环,并把接到他们的链找出来。

  • 环内节点的答案 = 环的长度;
  • 环外节点的答案 = 环的长度 + 当前节点到环的距离。

几趟 O(n) 的搜索就可以搞定问题!