题:

输出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但

时间复杂度