A 四章 题意:有个和个,把它们分成尽量少的组,使得每组的和不超过。 我们使用一个贪心算法,每次先选择尽可能多的,再选择尽可能多的分成一组。可以证明这样能够得到最优解。因为如果在还没被选的数中,把一个换成两个,答案一定不会变劣;所以如果在新选出的一组里存在两个、且存在至少一个没被选,把两个换成一个必然更优。 由于数据范围为,无法直接模拟。 可以先计算出若和都足够多,每组要选几个、几个。然后再不断使用这种方案直到或之一不够。之后下一组必定会将或选完。之后就只剩一种数了,直接计算即可。 复杂度。 B 一章 以下图片中红点为割点、红边为桥。 当时: 若,构造一个三元环即可。 若,构造两个点之间连一...