2021牛客暑期多校训练营6

AC代码

C. Delete Edges

构造题，要求在点数为 $n$ 的完全图上选出三角形，使得剩余边数小于 $n$ 。在比赛过程用想出了一种构造方法，但在几种特殊取值的情况下会发生错误。赛后在结合相关的构造论文，找到了最大匹配数的解法。

D. Gambling Monster

FWT与分治结合题。在比赛时求出了题目的通项公式，也看出需要FWT进行求解，但由于赛场上不会FWT，就无法解决。赛后学习FWT模板，然后结合分治思想进行补完。

F. Hamburger Steak

普通时间分配问题，相当于 $n$ 件事务与 $m$ 个工人，问最短完成时间。最短时间即为总时长平均分配给所有工人和最大时长事务的最大值，然后模拟时间分配过程即可。

H. Hopping Rabbit

题目可以转换为在边长为 $d$ 的正方形方格内覆盖矩形，然后求出是否存在未被覆盖到的方格。赛场上使用线段树进行求解，通过模拟区间覆盖的方式得到是否有空格。

I. Intervals on the Ring

题目要求在一个环上进行多段空间的覆盖叠加，询问重叠后的部分是否可以达到题目中的要求。一开始由于题目给出问题无解的输出，所以误认为重叠后的区间最多只有两段。后来发现所有情况都有解，在当前状态下添加一段，相当于制造一段空缺，枚举所有的空缺段即可。

J. Defend Your Country

需要考虑图上的割点，如果割点的所有连通块大小都为偶数可以直接割去，否则选择其他割点。需要使用塔尖寻找割点，然后模拟切割过程。

总结

F题由于第一次提交有多余输出，wa了一发。I题由于一开始被题目误导，导致思路错误，然后想到正解才通过。H题的线段树由于一开始在覆盖范围划分上出现的问题，在修改后才通过。然后通过公式推导看出D需要用FWT实现，由于没有掌握所以去开C的构造，但到比赛结束也未求出正解。J题在比赛过程中有一些思路有想到需要在割点进行操作，但没有想到具体的实现方法。