题:
输出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但。
时间复杂度。