2020-2021 BUAA ICPC Team Supplementary Training 01

排名	当场过题数	至今过题数	总题数
5/19	6	7	11

A

upsolved by JJLeo

题意

\(n\)个物品，每个物品权值不超过\(30\)，将所有物品分为三组，求权值最大组和权值最小组差值的最小值，输出方案。\((n \le 400)\)

题解

如果只需要求最小差值直接用bitset就可以解决，但是因为不会输出方案爆搜2小时结果无限TLE on 91。

考虑用bitset记录方案，最优方案最大权值不会超过\(4030\)，但是开不满\(400 \times 4030 \times 4030\)个，最多可以开\(100 \times 4030 \times 4030\)个，因此可以每\(4\)个记录一下可行方案，然后从最优方案\(4\)个\(4\)个枚举转移的所有可能判断能否往回跳即可。

B

upsolved by

题意

题解

C

upsolved by

题意

题解

D

upsolved by

题意

题解

E

upsolved by

题意

题解

F

solved by Bazoka13

题意

几艘容量固定的船，每次可以清空一艘，装满一艘或者互相倒水，求恰好一艘船有\(A\)升水的方案。

题解

范围不大，直接用队列把可以到达的情况全部暴力预处理出来同时记录用的哪艘船，如果方案存在倒着跳一遍即可

G

solved by Bazoka13

题意

求\(a~b\)中各位数乘积最大的数。

题解

贪心的想最大方案可能会有一连串的9，那么一位一位扫b，如果可以减一，就把后面几位全部取9，记录每一位的情况取最优的即可

H

solved by JJLeo

题意

\(n\)个二元组\((a_i,b_i)\)，\(m\)个二元组\((c_i,d_i)\)，求对于前面\(n\)个二元组\(a_ic_j+b_id_j\)的最小值。\((n, m \le 5 \times 10^5)\)

题解

考虑两个不同的\((c_i,d_i),(c_j,d_j)\)，式子列一下，就可以推出一个斜率优化式子。最后转化为下凸包上找第一个斜率\(\ge -\dfrac{a}{b}\)的点，直接二分即可。

I

solved by Bazoka13

题意

对于每一个 \(i,a_{i,j}\)代表某一个数从第i+1位开始，在\(a_{i,j}\)位第一次出现，求字典序最小的数列

题解

显然对于某个值x，该位数字与\(i+1\)到\(x-1\)的数字都不相同，由于有正负限制，直接权值线段树求一个区间mex即可

J

solved by Bazoka13

题意

给定几个插线板和限制最大串联插线板数的电器，求最多电器数量

题解

把插线板按照插孔数从大到小排序，用电器按照串联数从大到小排序，二分用电器数量判断是否可行

K

solved by Bazoka13

题意

可以将一棵树上某段的权值（长度不超过\(k\)）变为0，想办法最小化直径

题解

数据范围不大，考虑枚举每个删的端点x，dfs到一个点x的时候，把根到这个点的路径上的边权全部变成0后靠，考虑整个树的最长链 那就是下面几种情况了，x的子树的最长链，x子树外的最长链，x子树的一个单链+x外的一个单链。预处理一波即可

记录

0min：分题开始
15min+：想到了G的写法，CSK冲G，MJX ZYF想J
39min：CSK WA3 后AC，ZYF 冲J
52min：ZYF WA
82min：CSK冲 F，AC，第一次一血诞生了！
109min：MJX ZYF WA3 后换CSK继续冲J，MJX ZYF 冲H
139min：CSK AC J，ZYF冲H
156min：ZYF AC H，CSK冲I，MJX ZYF冲A
288min：A 题疯狂 TLE on 91，CSK AC K
till end：TLE on 91

总结

• csk：训练前不熬夜+当天小憩一波就可以有一个不错的状态，比前几次牛客多校的梦游状态好多了
• MJX：这场疯狂划水
• ZYF：A题想到bitset却卡死在输出方案上，要加强对乱搞题的训练，避免将时间浪费在无意义的爆搜上。