A

100%

$10^n$ 的十进制表示就是一个 1，后面接 $n$ 个 0。

由于 $n\le 100$，结果可能超过普通整数范围，直接按字符串输出即可。

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

B

100%

按照题意统计所有被射中的格子的分数总和即可。

先读入分数矩阵 $a$，再读入字符矩阵。对于每个位置 $(i,j)$：

• 如果字符为 X，则把 $a_{i,j}$ 加入答案；
• 如果字符为 .，则跳过。

注意 $n\le 100$，且 $a_{i,j}\le 10^9$，总分最大可能达到 $10^{13}$ 级别，需要用 long long。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。

C

40%

设 $val_x$ 表示第 $x$ 盆盆栽在最近一次处理后的水分；

由于操作都是按照时间升序的，故我们考虑 $t \to t'$ 具体要做什么。

在 $t \to t'$ 的过程中，我们需要更新每一盆盆栽的含水量，具体为

$$val_x=\max(0,\ val_x-(t'-t))$$

这样查询的时候只需要输出 $val_x$ 即可。

时间复杂度 $O(nq)$。

100%

观察到每盆盆栽之间互不影响，因此可以对每一盆单独维护它最近一次被处理后的状态。

设：

• $val_x$ 表示第 $x$ 盆盆栽在最近一次处理后的水分；
• $last_x$ 表示第 $x$ 盆盆栽最近一次被处理的时刻。

初始时 $val_x=a_x,\quad last_x=0$。

当时刻 $t$ 发生关于第 $x$ 盆盆栽的事件时，先结算从 $last_x$ 到 $t$ 的自然蒸发：

$$val_x=\max(0,\ val_x-(t-last_x))$$

然后令：

$$last_x=t$$

接下来根据事件类型处理：

• 若为 1 t x v，则浇水后令 $val_x:=val_x+v$；
• 若为 2 t x，则当前答案就是 $val_x$。

虽然所有事件的时间整体递增，但同一盆盆栽不一定每次都会出现，所以不能只维护一个全局时间，必须为每盆盆栽分别记录 $last_x$。

水分经过多次浇水后可能达到 $2\times 10^{14}$ 级别，需要用到 long long。

时间复杂度 $O(n+q)$，空间复杂度 $O(n)$。

D

100%

整条街区的黑暗程度只由相邻点亮路灯之间的间隔决定。

当切换位置 $x$ 时，除了 $x$ 附近的前驱 $L$ 和后继 $R$ 之外，其它点亮路灯之间的相邻关系不会变化，因此它们的贡献也不会变化。

故只需要维护当前所有点亮路灯的位置集合，以及相邻点亮路灯之间的贡献和。

设：

$$f(l,r)=(r-l-1)^2$$

表示点亮位置 $l$ 和 $r$ 相邻时，它们之间这一段对答案的贡献。

用一个 set 维护当前点亮的位置，另用变量 $ans$ 维护当前黑暗程度。

插入一个位置

如果当前要把熄灭的 $x$ 点亮，设 set 中：

• $L$ 为小于 $x$ 的最大点亮位置；
• $R$ 为大于 $x$ 的最小点亮位置。

插入 $x$ 之前，如果 $L$ 和 $R$ 都存在，那么 $L,R$ 原本相邻，需要先减去 $f(L,R)$。

插入 $x$ 之后，新的相邻关系变为 $L,x$ 和 $x,R$，所以：

• 如果 $L$ 存在，则加上 $f(L,x)$；
• 如果 $R$ 存在，则加上 $f(x,R)$。

最后把 $x$ 插入 set。

删除一个位置

如果当前要把点亮的 $x$ 熄灭，同样找到它的前驱 $L$ 和后继 $R$。

删除 $x$ 前，相邻关系中可能包含 $L,x$ 和 $x,R$，所以：

• 如果 $L$ 存在，则减去 $f(L,x)$；
• 如果 $R$ 存在，则减去 $f(x,R)$。

删除 $x$ 后，如果 $L$ 和 $R$ 都存在，它们会变成新的相邻点亮路灯，需要加上 $f(L,R)$

最后把 $x$ 从 set 中删除。

每次操作结束后输出 $ans$ 即可。若当前点亮路灯少于 $2$ 盏，上述维护方式自然会得到 $0$。

答案最大约为 $10^{18}$，需要使用 long long。

其中 $L$ 和 $R$ 可以利用 set 的 lower_bound/upper_bound 来快速找出。

时间复杂度 $O(Q\log Q)$。

E

100%

若 $k=1$，只需要统计单个数字本身是 $4$ 的倍数的位置数量，也就是字符为 0、4、8 的数量。

下面考虑 $k\ge 2$ 的情况。

可以观察到一个十进制整数是否为 $4$ 的倍数，只与最后两位有关。以下是具体证明：

设一个长度至少为 $2$ 的十进制整数为：

$$N=100A+10b+c$$

其中 $b,c$ 分别是倒数第二位和最后一位。由于 $100$ 是 $4$ 的倍数，所以：

$$100A\equiv 0\pmod 4$$

因此：

$$N\bmod 4=(10b+c)\bmod 4$$

也就是说，百位及更高位无论如何选择，都不会影响这个数是否为 $4$ 的倍数。于是对于 $k\ge 2$ 的子序列，只需要判断最后两位组成的两位数是否为 $4$ 的倍数。

---

枚举子序列的倒数第二位位置 $i$。

设 $S_i$ 对应的数字为 $v$。如果最后一位数字为 $d$，那么最后两位组成的数为：

$$10v+d$$

它需要满足：

$$(10v+d)\bmod 4=0$$

为了快速统计这样的最后一位，可以从右往左扫描字符串，并维护 $cnt_0,cnt_1,\dots,cnt_9$，其中 $cnt_d$ 表示当前位置右侧数字 $d$ 出现了多少次。

当扫描到位置 $i$ 时，枚举最后一位数字 $d=0\sim 9$。如果 $10v+d$ 是 $4$ 的倍数，那么右侧任意一个数字为 $d$ 的位置都可以作为最后一位。

此时最后两位位置已经确定为 $i<j$。为了让它们成为整个长度为 $k$ 的子序列的最后两位，前面的 $k-2$ 个位置必须从 $1\sim i-1$ 中选择，方案数为：

$$\binom{i-1}{k-2}$$

所以这一类贡献为：

$$cnt_d\binom{i-1}{k-2}$$

把所有满足条件的 $d$ 的贡献加入答案后，再令：

$$cnt_v:=cnt_v+1$$

表示当前位置也可以作为更左侧位置的最后一位。

所有组合数都对 $10^9+7$ 取模，可以预处理阶乘和逆元，在 $O(1)$ 时间内求出 $\binom{x}{y}$。当 $x<y$ 时组合数视为 $0$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。

F

100%

直接模拟每个人从 $1$ 走到 $n$ 会超时。

可以发现关键是快速找到“当前钱数买得起的、还没被买走的最靠左商品”。

维护一棵线段树。线段树的每个叶子表示一个商铺：

• 若该商品还没有被买走，叶子值为它的价格 $a_i$；
• 若该商品已经被买走，叶子值为 $+\infty$。

每个区间节点维护该区间内剩余商品价格的最小值。

对于第 $j$ 个人，设他当前手里的钱为 $money$。

我们的目标是在线段树上全局查询最小的下标 $p$，满足该位置还未被买走且 $a_p\le money$。

如果不存在这样的 $p$，说明当前已经没有买得起的商品，这个人购物结束。

如果找到了 $p$，那么这个人一定会买下第 $p$ 个商品。

买下后做 $money:=money-a_p$

并在线段树中把位置 $p$ 更新为 $+\infty$，表示该商品已经下架。然后继续查询下一件商品。

线段树查询方式

查询整棵线段树中第一个价格不超过 $money$ 的位置。可以考虑线段树上二分，即从线段树的根出发。

具体查询时：

• 如果根节点的最小值大于 $money$，说明当前没有任何可以买的商品；
• 否则从根节点开始向下走。设当前节点的左右儿子分别为 $ls,rs$；
• 如果 $ls$ 维护的最小值不超过 $money$，说明左半区间中存在可以买的商品，并且答案一定在左半区间，于是往左儿子走；
• 否则左半区间没有可以买的商品，答案只能在右半区间，于是往右儿子走。

不断重复这个过程直到叶子节点，就能得到全局最小的可购买下标。

由于每次成功购买会删除一个商品，因此所有人成功购买的总次数不超过 $n$。每个人还会进行一次失败查询来结束自己的购物过程。所以线段树查询和修改的总次数为 $O(n+m)$，每次复杂度 $O(\log n)$。总时间复杂度 $O((n+m)\log n)$，空间复杂度 $O(n)$。