Codeforces Round #503 (by SIS, Div. 1) – 解题报告

A – Elections

直接做不太好做,很懵逼。可以考虑枚举 CCP 得到的票数,然后再从各大党派中各抢一张票。如果不够抢就直接抢最小的票。这样取 min 即可。

继续阅读Codeforces Round #503 (by SIS, Div. 1) – 解题报告

「NOIp 2012 疫情控制」题解

主要思路

大概可以想到二分出时间,然后把所有的点往上跳,再把能跨子树分配的点进行分配。思路差不多就是这样,还是很自然的一个思路。

但是有一些细节值得注意:跨子树分配和当前子树覆盖的优先级需要处理好。如果这个不处理好只能拿到洛谷上 80% 的数据。这个地方我改了很久,最后发现需要把跨子树分配作为第一枚举,然后再在枚举之间二次枚举子树覆盖需求(放在堆里,贪心配对即可)。

继续阅读「NOIp 2012 疫情控制」题解

[POI2007]BIU-Offices 题解

主要思路

正好在《组合数学》上看过一个结论:反图形成的连通块的点在原图一定处处连通。证明很简单:考虑点对\((u, v)\),如果点对之间在反图中不连通显然是在原图联通的;如果在反图中连通,有一个不在当前点集的点使得他们连通。所以,我们只需要构建反图,根据「不与本点相连的点都在本连通块内」进行 BFS 即可。

继续阅读[POI2007]BIU-Offices 题解

「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日