「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日

CF1206D:Shortest Path 题解

主要思路

刚开始以为是搞\(\log n\)个基底点,然后双向边上面做事情,最后发现找图上最小环的复杂度非常的高。所以 GG。

正解考虑把问题的规模进行缩小:也就是把一些答案预先特判掉。比如说,如果某一个位上有超过三个点连接,那么环的大小就可以被确定为是\(3\),也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。

再考虑剩下的情况。此时,\(n\)已经缩小了很多,所以我们暴力建图,用 Floyd 跑最小环即可。

继续阅读CF1206D:Shortest Path 题解

[Fortuna OJ]Aug 10th – Group A 解题报告

A – 数学题

这道题二次函数的暴力分有 60 分,正解来自于论文。

这道题的主要是利用了一个结论,并且运用了辗转相除法的一种思想来对问题进行化简。首先,我们把向量调整至同向,且使\(|\vec{a}| < |\vec{b}|\),然后再来推导一个结论:

结论   对于\(\vec{a}, \vec{b}\),如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\),那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。

这个结论的证明参见《欧几里得算法的应用》。所以,我们就可以大概知道,我们可以将较长的向量分解:\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道,这道题可以笑掉这个\(k \vec{a}\),所以就可以用辗转相除法的套路进行处理。具体见代码:

继续阅读[Fortuna OJ]Aug 10th – Group A 解题报告