牛客小白月赛 76 题解

感谢大家参与牛客小白月赛 76！

出题人：氧气少年Kevin（CF;牛客）；罚时大师月色（CF;牛客）
题面PDF：点击下载

A. 猜拳游戏

思路

不难发现，答案与输入的手势相同。

B. Kevin 喜欢一

思路

本题解法较多。

例如，枚举 $x$ ，找到最小的 $x$ 满足 $2^x\geq n$ 是一种解法。

C. A加B,A模B

思路

由 $a\mod b=m$ 得 $a=kb+m,b>m,k\geq 0$

由 $a + b = n$ 得 $(k+1)b+m=n,(k+1)\geq 1$

不难得出， $m\geq \frac{n}{2}$ 时无解。

当 $a=m,b=n-m,m<\frac{n}{2}$ 时，可以得出 $n - m > m$ 即 $a\mod b=m$ 。

因此， $a = m, b = n - m$ 是一种可行的构造方式。

D. MoonLight 的运算问题

思路

维护当前手中的数字 $x$ ，扫描序列的过程中分类讨论：

若 $x\leq 1$ 或 $a_i\leq 1$ ，则执行加法操作；
否则，执行乘法操作。

需要注意将数字取模后变为 $0$ 或 $1$ 的问题。

E. 括号序列操作专家

思路

若左括号的数量与右括号的数量不相等，那么无解。

如果有解，以下是其中一种最优策略：

对于每一个左括号：

如果他的左边有未配对的右括号，那么把这个左括号直接移动到最左边的未配对右括号的左边与之配对；
否则，他只能跟右边的右括号配对。

对于每一个右括号：

如果左边有未配对的左括号，那么直接将这个右括号和左边未配对的左括号配对即可；否则，它只能后续跟右边的左括号配对。

记录当前左右括号的数量，和当前未配对右括号的数量即可。

F. Kevin 的矩阵

思路

一个比较好的思考角度是，先调整矩阵的列数，再改变序列中的元素。

一种比较极端的情况是： $m = 1$ ，将矩阵的列数调整为 $\sqrt n$ 后，再修改某一整列的元素，因此答案不超过 $2\sqrt n$ 的规模。

设最初的矩阵宽度为 $m$ ，最优方案中修改后的矩阵宽度为 $m^{'}$ ，那么 $|m-m'|\leq 2\lceil \sqrt n \rceil$ 。

注意：考虑到存在第 $x$ 行第 $y$ 列，第 $x + 1$ 行第 $y + p$ 列， $\dots$ ，第 $x + i$ 行第 $y+i\cdot p$ 列上存在目标数字的情况，因此 $|m-m'|\leq \lceil \sqrt n \rceil$ 并不是最优的。

暴力枚举修改后的矩阵宽度，计算次数，答案取这些次数的最小值即可。

G. Kevin 逛超市

关于题目背景的解释

本题的设定是氧气少年去逛超市，在结账时收银员漏处理了一件已结账的物品，导致报警器报警。不是因为氧气少年偷了东西。

思路

考虑期望的定义式，这里我们考虑计算 $E=\frac{n 件商品的通过报警器的次数总和}{n}$ 。

考虑计算 $n$ 件商品的通过报警器的次数总和。

不难发现，每次通过报警器的商品编号是连续的。

假设当前的商品编号为 $[l, r]$ ，那么接下来问题可以划分为 $[l,\lfloor \frac{l+r}{2} \rfloor]$ 上的和 $[\lfloor \frac{l+r}{2} \rfloor+1,r]$ 上的子问题。

方向 1

我们注意到，当前状态只跟区间长度有关，并且长度的种数不多，可以使用 $\tt std::map$ 记录某个长度的区间对总和的贡献，进行记忆化搜索。

方向 2

我们可以将其抽象成线段树。

同一层上的所有区间长度，最长的区间长度和最短的区间长度的差值不超过 $1$ 。

实现方法 1

维护每一层所存在的区间长度，和每种区间长度在这一层中存在的数量，不难发现每一层的区间长度种类数不超过 $2$ 。

一直维护到最底层，此时统计加和即可。

实现方法 2

不难发现，若已知当前的层数和区间长度的奇偶，当前的区间长度便是唯一的。

记忆化搜索即可。

PS：出题人最初想卡掉方向 1 的做法，但是由于复杂度相差不够明显，于是开大了时限，放过了方向 1 的做法。

题解 | 牛客小白月赛 76 题解