Beyond the Void

很明显，这个题是求连通块的个数。关键在于正确判断两个矩形相交。

我们知道，在一维的数轴上，两个区间[a,b] [c,d] (a<=b)，这两个区间相交的充分必要条件是c<=b。对于题中所述...

求连通块，由于数据范围过大，需要离散化，把10000压缩成2500。然后在指定区域内求出连通块的个数，BFS会有一点超时，需要用并查集优化。

这道题的解决方法隐藏得很深，不经过严密的数学推理分析是很难想到正确方法的。

注意到题上的一个看似无关紧要的条件，“不包括三角形”，这是一个突破口。由这个条件，我们可...

二维费用01背包问题，动态规划，但是要注意边界条件。

状态设定

F[i,j,k] 前i个瓶，氧为j，氮为k的最小重量

状态转移方程

F[i,j,k]=Min
{
F[i-1,j,k],
F[i-1,j-P_O[i]...

这是合并等价类问题，由于每个未知量有多位，每位对应0或1，我们先把字母串按照展开拆开。例如样例可以展开成

1,b1,b2,a1,a2,a3,a4,d1,d2,d3,d4, 1
a1,a2,a3,a4,c1,c2,c3,c4,b1,b2,e1,e2

对于...