A.

卡牌

这次比赛，一道签到题都没有。

本来以为是线段树上二分。就类似于花神的数论题那道，刚开始暴力修改（修改到线段树的每一个叶子节点），然后由于boss的attack在不断增加，到了 \(Att_i >= hp_j\) 的时候， \(j\) 这个牌顶多打一次，如果一个区间的 \(max\) 都小于boss的攻击力了，那么就不用修改的。是运用了boss不断变强，两个属性都单调不降的性质。然后发现，跑小样例过了，大样例T成傻逼。然后就交了。本以为会是30~60pts的，结果T+WA成傻逼，0pts。

讲讲正解：

题目很良心（）的给了一个没有用的 \(V\) ，它的值域是\(3e5\) ，这就启发我们对值域使用树状数组（或别的数据结构）。（当然，离散化以后也是可以的，但它具有提示性）

发现当国王塔的攻击力在某个范围的时候，该卡牌对boss造成的伤害是一定的,

因为该卡牌对boss的攻击次数是： $\left \lceil \frac{hp_i}{Att_q} \right \rceil $

只有 \(O(\sqrt V)\) 个区间，则区间内变为了区间加。

在值域上开个树状数组，下标作为boss的 \(Att_i\) ，区间加上 \(\left \lceil \frac{hp_i}{Att_q} \right \rceil * att_i\)

\(i\) 枚举每一个boss， \(j\) 枚举每一个卡牌，答案是具有单调性的，所以需要的卡牌数量不断增加的。类似于双指针的思想。

\(\{\)

枚举boss，卡牌号 \(j\) 增加，知道前 \(j\) 的卡牌产生的攻击力足以杀死第 \(i\) 个boss

那么 \(i++\)

每次用到下一个卡牌的时候，\(O(\sqrt V)\) 次执行 \(O(log_2V)\) 区间加的操作就行了 （树状数组很快）

\(\}\)

时间复杂度 \(O(N\sqrt V log_2 V)\) 。

启示：

1.这么奇怪的复杂度，不仅要敢想，而且要敢写

2.值域小的时候，考虑对值域上用数据结构维护区间操作

3.看到除法、整除、取整的时候，要考虑分块的思想

B.C.D.

先鸽