题解 |

题：

输出n+1。

题：

把班级按人数排序，把个人优先分配给人数少的班级，全部分配完后输出班级人数最多的人数。

题：

设第个班级的人数为。

对于第个班级拖堂的情况，先判断，即是否满足。

然后考虑二分答案，求出当人数最多的班级人数不超过时，最小的离校人数，并与进行比较即可。

当人数最多的班级不超过mid时，最小的离校人数就是。

只需要求出大于mid的所有班级人数之和、大于mid的班级数量即可求出上面这个式子，维护两个前缀和即可。

时间复杂度。

题：

（一开始想偏了写了贪心，WA的一瞬间才发现可以网络流）

二分图最大匹配。

Alice手牌对应的点编号到，Bob手牌对应的点编号n+1到2n。

若则与连边。

若最大匹配为，则Bob胜利，否则Alice胜利。

正确性：如果存在一种完美匹配，则可以根据完美匹配构造出Bob的策略，即Bob始终出Alice本轮手牌的匹配手牌；如果Bob存在一种必胜策略，则也可以据此构造出一种完美匹配，故充要性得证。

时间复杂度。

（据说网络流跑二分图复杂度是?不是很懂，反正很快）

题：

把Bob的手牌全部异或k，问题变成了Bob出和Alice一样的手牌则Bob胜利。

Alice的基本策略是，不能出Bob目前拥有的卡牌。

Bob的基本策略是，Bob不能主动减少和Alice公共卡牌的集合，否则Alice下一轮可以直接出上一轮Bob出的卡牌。

定义表示Alice独有的卡牌数量，定义表示Bob在遵循上述策略的前提下能打出的最多卡牌数量。

设表示Alice第种卡牌的数量，表示Bob第种卡牌的数量，则对于第种卡牌有：

若,则x+=。

若,则y+=。

若,则y+=。

最后比较和的大小即可。

由于特殊条件"若某一方打完了所有手牌，则Alice直接获胜"，故还需要讨论以下情况的影响（可能有重复或冗余，反正我都写上去了）：

n = 1；

m = 1；

Alice独有的牌数量不少于；

x=y但。

时间复杂度。