CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
======2020-2021 BUAA ICPC Team Supplementary Training 01======
[[https://codeforces.com/group/azDPdoF24f/contest/288496|比赛链接]]
=====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却卡死在输出方案上，要加强对乱搞题的训练，避免将时间浪费在无意义的爆搜上。
CVBB ACM Team

用户工具

站点工具

页面工具
