P11308 茫茫的不归路-题解

· · 题解

题目传送门

题目要求

小 ζ 的车队能够进入同一个阵营的可能性情况。

一共有三种可能性：

Together：表示无论已经进入的人如何归属，这个车队一定能进入同一个阵营；

Chance：表示存在一部分已经进入的人的阵营归属情况，使得这个车队的所有人进入同一个阵营；

Divide：表示无论已经进入的人如何归属，这个车队的所有人必然进入不同的阵营。

题目分析

在本题里面因为 p+l \le n \times m 所以不用考虑人数溢出的情况。

首先分析 Together：我们可以换种角度思考问题：怎样让他不能进入同一个阵营：那就是让他空出的最大的地方最小，举个例子：4 个人进入 2 个阵营，然后还要进入 3 人使放得下，有 2 种可能：2,2;1,3 很显然我们要让他平均分开，所以如果让已经进入的每个人尽量平均分布在每个阵营且每个阵营剩下的空位大于将要进去的人数，那么满足 Together。

然后分析 Chance：在不满足 Together 的情况时如果将要进去的人数小于阵营的容量，那么所有人将进入同一个阵营，否则是 Divide。