AtCoder Beginner Contest 187

本文主要是介绍AtCoder Beginner Contest 187，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这比赛我今年（2021）一月二号打了，那时候还很菜 qwq，只做了四道题，现在还有不到一个小时就到 2022 了，写下题解纪念。

附上全部 AC 代码链接：
https://atcoder.jp/contests/abc187/submissions/me?f.Task=&f.LanguageName=&f.Status=AC&f.User=HinanawiTenshi

前四题很水就不讲了，只讲今天做的 E，F。

E

个人感觉根本没必要出两个操作，纯属吓人（233，可以将两个操作化为一个操作处理。

无非就是每次给你一条边 \((u,v)\)，然后 \(u\) 经过 \(v\) 到达的点不更新，其它点加上 \(x\)。

我们将这棵树的根节点指定为 \(1\)，考虑对每一次操作分类：

• \(u\) 是 \(v\) 的子树，那么我们向 \(u\) 点打一个 \(+x\) 的标记。
• 否则，我们向 \(v\) 点打一个 \(-x\) 的标记，然后记录下偏移量 \(del\)。

在处理完操作之后，跑一遍 \(dfs\)，将标记下传，然后结果加上偏移量 \(del\) 即可，细节见代码。

F

状压 dp。

首先预处理，枚举子集，将所有的完全子图都标记一下。

然后转移方程显然是 \(f(S) = min(f(S), 1 + f(S\oplus s))\)，其中 \(s\) 是 \(S\) 的子集且满足 \(s\) 是对应的点集在原图中是完全子图。

这篇关于AtCoder Beginner Contest 187的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！