用户工具

站点工具


2020-2021:teams:legal_string:组队训练比赛记录:contest21

这是本文档旧的修订版!


比赛链接

补题情况

题目 蒋贤蒙 王赵安 王智彪
B 0 0 0
E 0 0 0
F 0 0 0
G 2 0 0
H 0 0 0
K 0 0 0

题解

G. transform

二分答案 $+$ 滑动窗口,赛后一分钟过样例 $\to$ 过题,乐。

J. farm

题意

给定 $n\times m$ 的矩阵,每个位置一个植物,种类为 $a(i,j)$。接下来 $q$ 个操作,每次选定一个矩形区域施加种类为 $k$ 的药水。

当植物的种类与被施加的药水种类不同时植物死亡。问最后死亡的植物数。

题解 1

二维线段树维护区间赋值,最后查询时将所有操作下放到子节点暴力修改,时间复杂度 $O(nm\log n\log m)$。

题解 2

二维树状数组维护矩形区间加,先将所有操作加入矩阵,最后枚举种类,枚举种类 $k$ 的植物时先消除 $k$ 类药水的影响查询完成后再加回去。

时间复杂度同为 $O(nm\log n\log m)$,但常数小。

题解 3

随机给每个种类 $k$ 赋一个值 $f(k)$,然后哈希处理矩阵加,当种类 $k$ 的植物的所在位置的权值恰好为 $f(k)$ 的倍数时该植物存活。

如果不放心可以二重哈希,时间复杂度 $O(nm)$。

2020-2021/teams/legal_string/组队训练比赛记录/contest21.1633174707.txt.gz · 最后更改: 2021/10/02 19:38 由 jxm2001