2021-11-12 22:16 中南大学 C++

关注

【题解】牛客练习赛91

前言：

本次比赛题目比较偏向思维，所用到的算法知识点不会太深。

接下来背下锅，很抱歉有人反映C题被卡常。因为std没有任何优化大概500+MS，内测时大家貌似也没有出现被卡常的现象，所以就觉得应该1s足够。没想到比赛期间因为测评机波动，加上可能确实有些算法常数过高，导致了卡常发生，真是抱歉QAQ。

A-神奇天平

考点：数学
对于当前 $n$ 件物品：
①若 $n$ 能整除 $m+1$ ，则我们分成 $m+1$ 堆，每堆有 $\frac{n}{m+1}$ 件物品。我们把前 $m$ 堆东西放到天平上，如果这 $m$ 堆东西一样重，那说明重的那件物品在最后一堆中，否则天平可以告诉我们，重的那件物品在这 $m$ 堆东西的哪堆中。
②若 $n$ 不能整除 $m+1$ ，则我们分成 $x+1$ 堆，前 $x$ 堆每堆有 $\frac{n}{m+1} +1$ （ $\frac{n}{m+1}$ 要向下取整）件物品，最后一堆物品数小于等于 $\frac{n}{m+1} +1$ ，可证 $x$ 一定小于等于 $m$ 。我们把前 $x$ 堆东西放到天平上，如果这 $x$ 堆东西一样重，那说明重的那件物品在最后一堆中，否则天平可以告诉我们，重的那件物品在这 $x$ 堆东西的哪堆中。
重复以上过程，最终便可找到重的那件物品，不难发现这个过程本质上就是求 $log_{m+1}n$ (向上取整)的值。
以上是正常的思考过程，实际上打个表找找规律应该就能通过此题(跑

时间复杂度： $O(T\times log_{m+1}(n))$ 。

B-魔法学院(easy version)

考点：差分、贪心

对于某个字符 $c$ ，我们可以用差分或者贪心的方法处理出他们在 $[1,n]$ 上的覆盖区间。然后接着从 $1$ 枚举到 $n$ ，若下标 $i$ 处的字符可以修改为 $c$ ，则令 $S_{i}=max(S_{i},c)$ 即可。枚举完 $94$ 种字符后，再对字符串 $S$ 统计价值和便可得到最终答案。

时间复杂度： $O(94 \times n)$ 。

C-魔法学院(hard version)

考点：并查集、双向链表

我们不妨从高价值字符枚举到低价值字符，那么对于高价值字符覆盖过的区间，低价值字符就没有必要去遍历了。因此遍历时，我们使用并查集或者双向链表对之前覆盖过的区间进行跳跃即可，具体可见代码。

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

D-监狱逃亡

考点：树状数组、线段树

首先预处理出每行的前缀和数组，接着注意到行数只有三，于是我们用 $i$ 表示从第一行下到第二行的下标，用 $j$ 表示从第二行下到第三行的下标，那么问题可以转化成，求满足 $sum1[i]+sum2[j]-sum2[i-1]+sum3[n]-sum3[j-1]\geq0(i<=j)$ 的 $(i,j)$ 对数。

我们对上式移项，变为 $sum2[j]-sum3[j-1]\geq sum2[i-1]-sum1[i]-sum3[n](i<=j)$ 。显然可以类比逆序对，对其离散化后利用树状数组或者线段树进行求解。

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

E-游戏人生

考点：二分、优先队列

显然玩家的初始生命值越多，通关的可能性就越大，因此我们对答案进行二分，那么题目转化成给定玩家初始生命值，判断玩家是否能通关。这个可以使用反悔贪心的方法来实现，具体如下：

①使用两个变量 $cnt1$ 与 $cnt2$ 记录到当前回合，使用了多少次普通攻击和狂暴攻击。

②使用一个大根堆保存到当前回合，反悔后玩家能回复的生命值。

③每个回合开始时，首先我们默认使用狂暴攻击，对boss造成 $2\times A$ 点伤害，玩家生命值减 $B$ ，并令 $cnt2++$ 。

④若玩家的生命值小于等于 $0$ 了，我们进行反悔操作：

1. 如果 $cnt1$ 和 $cnt2$ 都为 $0$ ，表示已经无法通过反悔来回复生命值了，因此无法通关。

2. 如果 $cnt1$ 为 $0$ ， $cnt2$ 不为 $0$ ，则只能通过将某次狂暴攻击反悔为普通攻击来回复生命值，因此玩家的生命值加 $B$ ，boss的生命值加 $A$ ，并令 $cnt2--$ , $cnt1++$ 。

3. 如果 $cnt1$ 不为 $0$ ， $cnt2$ 为 $0$ ，则只能通过将某次普通攻击反悔为防御来回复生命值，因此玩家的生命值加堆顶元素，boss的生命值加 $A$ ，弹出堆顶，并令 $cnt1--$ 。

4. 如果 $cnt1$ 和 $cnt2$ 都不为 $0$ ，则判断 $B$ 与堆顶元素的大小，选择回血量更大的操作进行反悔。

⑤接着判断boss生命值是否小于等于 $0$ ，如果是表示能够通关。

⑥然后boss攻击，玩家生命值减少 $a_{i}$ ，并将这次反悔后能回复的生命值压入堆。

⑦若玩家的生命值小于等于 $0$ 了，我们进行反悔，具体操作同④。

从内测来看，本题还有线段树的单log做法。

时间复杂度： $O(T\times n \times log(lim) \times log(n))$ 。

F-卡牌大师

考点：思维

设 $m$ 的长度是 $len$ ，考虑每个长度为 $len$ 的后缀 $0$ 到 $10^{len}-1$ ，某个 $x$ 想和某个 $y$ 相加得到 $m$ 或者 $10^{len}+m$ ，那一个 $x$ 只有一个对应的 $y$ ，所以每个关系，只取一边即可。具体的， $[0,\frac{m}{2}]$ 对应 $[\frac{m}{2},m]$ ， $[m+1,\frac{10^{len}+m}{2}]$ 对应 $[\frac{10^{len}+m}{2},10^{len}-1]$ ，中点讨论一下，然后算一下 $1$ 到 $n$ 分布在四个块里面的数量，每个互斥的块取其中之一。

时间复杂度： $O(T\times len(m))$ 。

G-区间加

考点：线段树

不算难的数据结构题，主要难度可能在于编程。

考虑某一个普通的数 $a_{i}$ 生命历程的所有状态：原数→一直加 $lowbit$ 变成只有 $2$ 个 $1$ →再一直加 $lowbit$ 直到和 $highbit$ 合并→只有 $1$ 个 $1$ 。对于第二个过程，一个数只会最多加 $logV$ 次，对于第三个过程，每个数最多只会合并一次，第四个过程之后就相当于每次给这个数乘 $2$ 了。

因此，我们对每个数 $a_{i}$ ，如果 $a_{i} = 2^{k}$ ，那么我们另外开一棵线段树维护，在这棵线段树上 $1$ , $2$ 操作都相当于区间乘 $2$ ；否则我们把 $a_{i}$ 最高位和其它位分开，记为 $b_{i}$ 和 $c_{i}$ 。

对于加 $highbit$ 操作：等价于给区间的 $b_{i}$ 乘 $2$ 。

对于加 $lowbit$ 操作：如果区间 $[1,r]$ 存在 $c_{i} ≠2^{k}$ ，我们暴力找到这个 $c_{i}$ ，给它加上 $lowbit$ ，直到 $c_{i}=2^{k}$ ；否则，操作等价于给区间的 $c_{i}$ 乘 $2$ 。

接下来只剩一个问题，就是要把 $highbit=lowbit$ 的数合并，并插入到 $a_{i} = 2^{k}$ 的线段树中。对于这个问题，我们可以维护区间 $highbit_{i} - lowbit_{i}$ 的差的最小值 $d_{i}$ ，每次加 $highbit$ ，相当于给区间的 $d_{i}$ 加 $1$ ，加 $lowbit$ 相当于给区间的 $d_{i}$ 减 $1$ 。如果区间存在一个 $d_{i} = 0$ ，我们就暴力找到这个位置，把 $highbit$ 和 $lowbit$ 合并，插入到另—棵线段树中，并把 $d_{i}$ 赋值为 $inf$ 。

每次询问就是把区间的 $a_{i}$ , $b_{i}$ , $c_{i}$ 加起来。
考虑时间复杂度，对于加 $lowbit$ 操作，每个数只会加 $logV$ 次，每次需要 $O(logn)$ 访问到这个数，这部分总复杂度是 $O(logn\times logV)$ ；对于合并 $highbit$ 和 $lowbit$ 的操作，每个数只会合并一次，需要 $O(logn)$ 访问到这个数，这部分总复杂度是 $O(n\times logn)$ ；其它部分总时间复杂度均为 $O(n\times logn)$ 。因此这题时间复杂度是 $O(n\times log(n) \times log(V))$ 。