BZOJ2138:stone – 题解

主要思路

首先可以发现这个东西可以被认为是一个二分图的模型,只不过现在我们需要快速算其最大匹配。那么根据 Hall 定理,如果对于任意一个左部点 \(x \in U, |U| < |V|\),其连接的右端点集合 \(M\) 满足 \(|M| > |U|\),那么就存在完美匹配。

这个题有个性质:区间互不包含。所以满足 Hall 定理其实就需要满足对于每个线段都存在 \(\sum_{i = l}^r b_i \leq \sum_{i = L[l]}^{R[r]} a_i\),其中 \(b_i\) 是对于第 \(i\) 根线段我们取了 \(b_i\) 个石子。

我们可以写成一个前缀和进行移项:

\[ p^b = \sum b_i, p^a = \sum a_i \\ p^b_{r} – p^b_{l – 1} \leq p^a_{R[r]} – p^b_{L[l] – 1} \\ p^b_{r} – p^a_{R[r]} \leq p^b_{l – 1} – p^b_{L[l] – 1} \]

这个东西用线段树维护即可。

继续阅读BZOJ2138:stone – 题解

「Universal OJ」:#308「UNR #2」 UOJ 拯救计划 – 题解

主要思路

看到这个很小的模数就知道肯定是个 Trick 题,一定不会让你去跑一般图的(估计是 NPC)。

首先,我们可以设颜色未标号的、用了 \(i\) 种颜色的方案数为 \(f_i\),那么答案就是:

\[ ans = \sum_{i = 1}^k f_i k^{\underline{i}} \]

发现这个东西在 \(i > 2\) 时就直接被模成了 \(0\)。我们只需要算 \(f_1, f_2\) 即可。其中 \(f_1 = [m = 0]\)。\(f_2\) 的方案数等价于二分图的双部染色的方案数。所以,我们跑一边二分图然后算 \(2^b\) 即可,\(b\) 是连通块次数。

继续阅读「Universal OJ」:#308「UNR #2」 UOJ 拯救计划 – 题解

AtCoder Regular Contest 099:E~F – 题解

E – Independence

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

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

LibreOJ#2548:「JSOI2018」绝地反击 – 题解

主要思路

这道题乍一看不是很能做,因为摆放状态很多。然而,计算机科学这种东西解决不了问题的时候不讲究正解,只讲究近似。所以,我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。

继续阅读LibreOJ#2548:「JSOI2018」绝地反击 – 题解

[Fortuna OJ]Aug 1st – Group A 解题报告

A – 水叮当的舞步

真的是玄妙重重。

我们先思考正常的暴力搜索:枚举每一次按下的颜色,然后检查继续更新。考虑用 IDA* 优化这个过程,首先估值函数就是剩下的颜色个数,因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。

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

网络流

定义

在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。

继续阅读网络流