2021牛客暑期多校训练营5

AC代码

B. Boxes

箱子中有黑或白的球，开箱需要花费，也可以花费一定代价询问剩余箱子中黑白球的数量，求解要知道所有球颜色的代价的期望。首先考虑把所有箱子打开的代价，其次考虑一开始进行询问后代价花费的期望。通过找规律可以得到询问后每个箱子需要打开的几率，然后取两种方式较小值的答案。

C. Cheating and Stealing

题目要求将比赛结果划分为若干局，根据胜场数进行划分。通过计算前缀和，判断局数的大致划分。然后考虑到可能会出现不停胜败交题的情况导致复杂度变高，需要预处理出最先打破平局的状态来优化时间。

D. Double Strings

dp。

G. Greater Integer, Better LCM

对于每个质因子只会分为A独享，B独享，AB共享一部分其他的分给一人独享。所以直接dfs，时间复杂度 $O(3^{18})$ ，加上部分剪枝即可。

H. Holding Two

构造01矩阵使得不会出现三个相同数字竖直水平或斜方向相连。构造方案：横向两两颜色相同分组，纵向两两颜色不同。

J. Jewels

在不同时间获取某一物品的代价不同并且遵循一定的函数，物品数量较小，符合最小费用流的求解要求，更具时间与代价的关系建图，直接求解答案即可。

K. King of Range

给定数组，询问有多少连续子序列满足最大值与最小值之差大于 $k$ 。使用单调队列求解，得到满足要求的区间最值，同时复杂度满足要求。

总结

首先过了H简单构造题。然后做J网络流题，由于服务器原因T了一发，后面提交相同代码就通过了。K题由于数组标记打错wa了一发，发现问题后解决。B题打表找出选择概率的规律后成功通过。D题由于使用long long导致内存超限。G题思路一直都正确，只不过常数较大过不去，后来加上剪枝过了。C的想法思路比较正确，但方法不对，一直过不去。