「USACO 2018.12 Platinum」解题报告

A – The Cow Gathering

首先,如果没有限制的话,其实从叶子结点来抽是一定有解的,可以考虑思考一颗以最后出口为根结点的外向树来理解这个逻辑关系。现在有 \(m\) 个有向边,初步思考可以把每个点都作为最后一个节点,然后来看新的图有没有环,这样是 \(\Theta(n^2)\)。

继续阅读「USACO 2018.12 Platinum」解题报告

AtCoder Regular Contest 099:E~F – 题解

E – Independence

这道题直接去想性质不好想,因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图,那么左右部恰好可以作为题中的两个 state。然而,意识到并不保证是一张连通的二分图,所以我们可以用一些连通块来拼成两个 state。那么,我们可以用个背包搞搞,再最后算算答案即可。(就不需要贪心的构造两个大小相近的团了,全部都算一遍即可)。

继续阅读AtCoder Regular Contest 099:E~F – 题解