牛客挑战赛 83 官方题解

A Solution

简单模拟。

我们可利用一个标记数组记录栈中是否有该数。此处可以使用 map 来存。我们可以首先将输入的数入栈，如果发现输入的数被标记过，那么就可以一直出栈直到该数处于栈顶，并且把标记清零。最后直接输出栈的容量就是答案。

B Solution

结论是前 $\lfloor \frac{n}{k}\rfloor$ 大的数的和。

可以把这些大的数标记下来，如果当前的出栈序列是计入贡献的位置，那么直接弹出，否则就等凑满足够多的小的数再弹出。

C Solution

考虑一个 (()..()..(((())))..()..()) 的结构，其中最外层括号为控制嵌套层数不超过 $k$ ，然后中间为 $k$ 层的括号嵌套，然后左右分别有 $t$ 个 ()，那就产生 $t^2$ 的贡献，所以原问题转化为分解成若干个平方数，显然可以构造，而且可以做到 $8\times 10^5$ 内。

D Solution

求解：

\displaystyle{\sum_{i=1}^n\prod_{j=1}^i\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{j}\rfloor}

\displaystyle{\sum_{i=1}^n{\lfloor\frac{n}{i}\rfloor}^i\prod_{j=1}^i\lfloor\frac{m}{j}\rfloor}

考虑整除分块，令上一个块（此处的块是 $\lfloor\frac{n}{i}\rfloor$ 和 $\lfloor\frac{m}{i}\rfloor$ 均相同记作一块）的最后一个位置为 $k$ ，则有：

\displaystyle{\sum_{i=1}^n{\lfloor\frac{n}{i}\rfloor}^i\prod_{j=k+1}^{i} \lfloor\frac{m}{j}\rfloor\prod_{j=1}^k\lfloor\frac{m}{j}\rfloor}

由于此时左边 $\lfloor\frac{m}{j}\rfloor$ 等价于 $\lfloor\frac{m}{i}\rfloor$ ，所以可以转化为：

\displaystyle{\sum_{i=1}^n{\lfloor\frac{n}{i}\rfloor}^i {\lfloor\frac{m}{i}\rfloor}^{i-k}\prod_{j=1}^k\lfloor\frac{m}{j}\rfloor}

\displaystyle{\sum_{i=1}^n{(\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor)}^{i-k} \times {\lfloor\frac{n}{i}\rfloor}^k\prod_{j=1}^k\lfloor\frac{m}{j}\rfloor}

此时右边是个定值，左边是个等比数列求和，显然整除分块可做，由于 $n,m$ 同阶，时间复杂度 $O(\sqrt n)$ 。

E Solution

打牌题，首先可以发现两个人决斗时，先手若手中拥有双方最大牌必胜，因为你先出一张你的最小牌，无论对面压什么你都可以压回来。

假设最大牌在对方手中，那先手必须有两张牌大于对方的次大牌才能获胜，否则先手必败。因此我们将所有人按自己手中最大牌的大小从小到大排序，显然对于一个人来说，左边的人他一定打的过，右边的人要看自己是否有至少两张牌大于对方的次大牌，令这个人第二大的牌值为 $k$ ，那么就是区间查询 $< k$ 的数的个数，扫描线线段树维护即可，当然主席树也行但是麻烦。

F Solution

首先考虑一个形如 ${1/2/3},0,0,...,0,0,{1/2/3}$ 的区间的答案如何计算，发现可以 $dp$ 预处理， $dp_{i,1/2/3}$ 分别表示第 $i$ 位为 $1/2/3$ 的方案数，转移方程是

$dp_{i,1}=dp_{i-1,1}+dp_{i-1,2}+dp_{i-1,3}$

$dp_{i,2}=dp_{i-1,1}+dp_{i-1,2}$

$dp_{i,3}=dp_{i-1,2}+dp_{i-1,3}$

对于起点是 $1/2/3$ 终点是 $1/2/3$ $9$ 种情况分别预处理即可。

考虑对于一个询问区间一定形如很多个上文的小区间拼起来，答案其实就是将每个小区间的方案数相乘，当然有一些非法情况需要判断一下比如 $1,3$ $3,2$ 等等，还有如果一个区间的左/右端点是 $0$ 的话将它视为在左/右边有个 $3$ 就好了。维护答案只需要一颗线段树，维护一下左端连续 $0$ 的个数，右端连续 $0$ 的个数，左端连续 $0$ 区间的右端点的值，右端连续 $0$ 区间的左端点的值，中间部分的答案就好了。

时间复杂度 $O(9n+q \log n)$ 略优于矩阵做法。

G Solution

题目要求选取的区间长度大于 $1$ ，我们有个显然的结论，就是所选取的区间长度不超过 $3$ 。考虑证明，任何一个长度 $\ge 4$ 的区间都可以分成两个长度 $\ge 2$ 的区间，这两个区间的平均值不可能同时小于原区间的平均值，就这样一直划分下去，即可得到这个结论。

之后二分答案，考虑对于一个区间最少加价多少次可以使得其平均值大于等于二分的答案，直接贪心，每次加价时找能涨价且能涨价最多的去涨价就行，这个是好算的。考虑如何判定二分的答案，因为是第三大，暴力做的话就是去枚举三个区间，计算三个区间分别最少的涨价次数，加起来小于等于 $k$ 就行。考虑如何优化这个过程，我们处理每个前后缀中涨价次数最少的区间的次数，有了这个东西，我们去枚举中间的一个区间，剩下两个区间是前面一个后面一个，计算答案即可。

时间复杂度： $O(n \log v)$ 。