AtCoder Beginner Contest 187 题解(A-F)

A - Large Digits

简单模拟。

B - Gentle Pairs

(O(n^2))暴力枚举,记枚举到的两个点为((x_1, y_1))((x_2, y_2)),那么只需要(|y_2 - y_1| le |x_2 - x_1|)就对答案有1的贡献。

C - 1-SAT

首先扫一遍全部的串,把不以!开头的串都放到一个支持快速查找的容器中。

然后再扫一遍全部的串,对于以!开头的串,将!除去后,看之前的容器里是否有这个串,有的话就说明冲突了,将当前串输出。

否则,就说明没有冲突。

D - Choose Me

对于城市((a, b)),如果T某在这座城市演讲,自身收益增加(a + b),对方收益减少(a),总的收益就是(2a + b)

将所有城市按收益高低排序,贪心地选收益高地。

E - Through Path

首先注意到是在无根树上进行地操作,不妨设节点1为根,一遍dfs跑出所有节点的深度以及dfs序。

假设现在要对u v执行操作1,增量为(x)

  1. 如果(depth_u < depth_v),那么相当于除了以(v)为根的子树之外都要加(x)。可以转换为对整棵树加(x),再对子树减(x)
  2. 反之,就是只需要对以(v)为根的子树加(x)

然后,就可以用利用dfs序将子树加转化为区间加。然后一个线段树区间加法,单点求值解决。

因为最后只需要单点求值,所以树状数组应该也可以用。

F - Close Group

这题就是最小团覆盖,一个经典NP难问题,就是降低了问题规模让你暴力搞。

解法1:递归+剪枝

假设当前(i - 1)个点构成了团的集合(Cliques),现在要加入第(i)个点,那么:

  1. 如果(i = n + 1),那么(|Cliques|)可以用来更新答案。
  2. 如果(Cliques)中的(Clique)中的点都和(i)有边相连,那么可以将第(i)个点加入(Clique)
  3. (i)个点可以自己构成一个团。

这样递归的代码其实挺好写的,但是实测会超时。

然后就是加优化了,如果之前已经枚举到的可行解的最小值是(ans),那么如果现在(|Clique| ge ans)则没有必要继续枚举了。

加完剪枝就过了。

原文地址:https://www.cnblogs.com/zengzk/p/14224251.html