题解 | #牛客小白月赛 44 题解#

牛客小白月赛 44 题解

Problem A

由题意最优解区间互不重叠，直接模拟找出所有区间即可。如果不方便存储，可以考虑使用 vector 容器。

Problem B

换参考系：对于每一个植物格子，如果周围 $3\times 33\backslash times3$ 格子都没有保护伞，一定会被偷走。（直接暴力染色可能需要两遍 for 循环较麻烦）

Problem C

通过五折出点可以拿回 $50\mathrm{\%}50\backslash \%$ 投资的 RMB，因此每次对 RMB 数除以二下取整并统计获取的经验即可。

Problem D

根据下方的样例解释，不难发现表格中的规律：

$ans=\mathrm{\mid }b\mathrm{\mid }\times \sum a_i+\mathrm{\mid }a\mathrm{\mid }\times \sum b_{i}ans=|b|\backslash times\backslash sum\; a\_i+|a|\backslash times\backslash sum\; b\_i$

Problem E

由于每个黑点下一步都是白点，最优解直径长度只能是 $11$（黑白交替，两头都是黑）

据此直接统计黑点个数 $CntCnt$，根据求和公式计算 ${\displaystyle \frac{Cnt\times (Cnt+1)}{2}}\backslash dfrac\{Cnt\backslash times(Cnt+1)\}\{2\}$，注意开 long long

Problem F

参考《电池的寿命》一题，考虑利用其余 $n-1n-1$ 条链拼到即将成为重心的点上。

最终解两个不等式，加以分类讨论判断即可：

$\{\begin{array}{c}\max \{a_1,a_2,\cdots ,a_{i-1},a_{i+1},\cdots ,a_n\}\le \lfloor {\displaystyle \frac{\sum a_i}{2}}\rfloor \\ \max \{x,y\}\le \lfloor {\displaystyle \frac{\sum a_i}{2}}\rfloor \end{array}\backslash begin\{cases\}\backslash max\backslash \{a\_1,a\_2,\backslash cdots,a\_\{i-1\},a\_\{i+1\},\backslash cdots,a\_n\backslash \}\backslash le\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\; a\_i\}\{2\}\backslash right\backslash rfloor\backslash \backslash \backslash max\backslash \{x,y\backslash \}\backslash le\backslash left\backslash lfloor\backslash dfrac\{\backslash sum\; a\_i\}\{2\}\backslash right\backslash rfloor\backslash end\{cases\}$

第一个式子可以考虑 $O(n)O(n)$ 预处理，第二个式子对于一个 $a_{i}a\_i$ 批量计算考虑奇偶分讨：

$\min (\lfloor {\displaystyle \frac{(a_i\mathrm{\%}2)+\sum _{j\mathrm{\ne }i}{a}_j}{2}}\rfloor \times 2+2-(a_i\mathrm{\%}2),a_i)\backslash min\backslash left(\backslash left\backslash lfloor\backslash dfrac\{(a\_i\backslash \%2)+\backslash sum\backslash limits\_\{j\backslash ne\; i\}a\_j\}\{2\}\backslash right\backslash rfloor\backslash times2+2-(a\_i\backslash \%2),a\_i\backslash right)$