2015-2016 ACM-ICPC East Central North America Regional Contest (ECNA 2015)

Problem A

Unsolved.

Problem B

Upsolved by zerol. (-7)

题意：就是屏幕里有一些像素，像素分成两类 A B，问最少的移动次数，使得所有 A 在一个矩形区域内且所有 B 在区域外。

题解：就是枚举可能的矩形，然后计算答案。以 x 轴为例，左边界需要考虑的有 A 的 x 坐标以及 B 的 x 坐标 +1，右边界就是 A 的 x 坐标以及 B 的 x 坐标 -1。还有一些恶心的问题在题目中但不在这个简化后的问题中。

Problem C

Solved by kblack. 04:36 (+9)

ultmaster：其实，大部分罚时，都是我贡献的。

Problem D

Solved by zerol. 00:44 (+)

温暖的模拟题签到 ×2。

Problem E

Solved by zerol. 00:14 (+)

温暖的模拟题签到。

Problem F

Solved by ultmaster. 01:13 (+)

题意：有很多地方，有些地方是原材料产地，有些地方是工厂，有些地方什么都不是。工厂和原材料产地是要建立一对一的关系。有很多物流公司，每个物流公司只能去一些地方，只能对接至多一个原材料产地，至多一个工厂。问最多有多少个原材料产地和工厂能匹配上。

题解：很像那种有限制的二分图匹配。直观上来理解，不难想到，我们就对每个物流公司建一对点（入点和出点），其中的 cap 为 1。对于原材料产地，直接连到入点；对于工厂，直接从出点连出；对于其他的点，从出点连到这个点，然后从这个点连到入点。简单验证会发现这个建图有点逼真。码一码就过了。

Problem G

Solved by ultmaster. 02:02 (+)

Problem H

Unsolved.

Problem I

Solved by kblack. 00:24 (+)