【APIO2021】六边形领域 - 题目

对于一个用六边形无限平铺的平面，Pak Dengklek 站在其中一个格子上，并称该格子为初始格子。如果六边形平铺中的两个格子有公共边，则称它们是相邻的格子。对于一步移动，Pak Dengklek 可以从一个格子向六个可能的方向（从 $1$ 到 $6$ 编号，如下图所示）移动到与其相邻的格子上。

于某个由 $N$ 次行动构成的行动序列，Pak Dengklek 可以用其产生的路径（对应一个按序访问的格子序列）构造一个领域。其中第 $i$ 次行动由移动方向 $D [i]$ 和在该方向上的移动步数 $L [i]$ 组成，并且该路径应有如下性质：

路径是封闭的，这意味着在格子序列中，起点格子与终点格子（即初始格子）相同。
路径是简单的，这意味着在格子序列中，除了初始格子访问过恰好两次（起点和终点分别访问一次），其他格子只能被访问至多一次。
路径是暴露的，这意味着在格子序列中，每个格子与至少一个不在序列中出现过的非内部格子相邻。
- 如果一个格子不在格子序列中出现过，并且从它出发，在不经过格子序列中任何格子的情况下，（通过若干步移动）只能访问到有限个格子，我们就称该格子是内部格子。

下图是一个符合上述条件的路径例子。其中：

$1$ 号格子（粉色）是初始格子。
被编号的格子（淡蓝色）组成格子序列，编号代表它被访问的顺序。
被标上叉号的格子（深蓝色）是内部格子。

构造出的领域只包含所有路径上的格子和内部格子。领域中格子 $c$ 的距离定义为：在只经过领域中包含格子的情况下，从初始格子出发到达 $c$ 所需要的最少移动步数。领域中一个格子的分数定义为 $A + d \times B$ ，其中 $A$ 和 $B$ 是 Pak Dengklek 给定的常数， $d$ 是该格子在领域中的距离。下图给出了用上示路径构成的领域中每个格子的距离。

请帮助 Pak Dengklek 计算，用给出的行动序列构成的领域中，所有格子的分数之和。由于总分数值可能很大，最终结果对 $10^{9} + 7$ 取模。

实现细节

你需要实现下列函数：

int draw_territory(int N, int A, int B, int[] D, int[] L)

$N$ ：行动序列中行动的次数。
$A, B$ ：分数计算中的常数。
$D$ ：大小为 $N$ 的数组，其中 $D [i]$ 表示第 $i$ 次行动的方向。
$L$ ：大小为 $N$ 的数组，其中 $L [i]$ 表示第 $i$ 次行动的移动步数。
函数应该返回用给出的行动序列所构成的领域中，所有格子的分数总和对 $10^{9} + 7$ 取模后的值。
该函数将被调用恰好一次。

例子

考虑下列调用：

draw_territory(17, 2, 3,
               [1, 2, 3, 4, 5, 4, 3, 2, 1, 6, 2, 3, 4, 5, 6, 6, 1],
               [1, 2, 2, 1, 1, 1, 1, 2, 3, 2, 3, 1, 6, 3, 3, 2, 1])

该行动序列和上述题面中给出的例子相同。下表列出了该领域中所有可能的距离值所对应的分数。

距离值	格子数	每个格子分数	总分数
$0$	$1$	$2 + 0 \times 3 = 2$	$1 \times 2 = 2$
$1$	$4$	$2 + 1 \times 3 = 5$	$4 \times 5 = 20$
$2$	$5$	$2 + 2 \times 3 = 8$	$5 \times 8 = 40$
$3$	$6$	$2 + 3 \times 3 = 11$	$6 \times 11 = 66$
$4$	$4$	$2 + 4 \times 3 = 14$	$4 \times 14 = 56$
$5$	$3$	$2 + 5 \times 3 = 17$	$3 \times 17 = 51$
$6$	$4$	$2 + 6 \times 3 = 20$	$4 \times 20 = 80$
$7$	$4$	$2 + 7 \times 3 = 23$	$4 \times 23 = 92$
$8$	$5$	$2 + 8 \times 3 = 26$	$5 \times 26 = 130$
$9$	$3$	$2 + 9 \times 3 = 29$	$3 \times 29 = 87$
$10$	$4$	$2 + 10 \times 3 = 32$	$4 \times 32 = 128$
$11$	$5$	$2 + 11 \times 3 = 35$	$5 \times 35 = 175$
$12$	$2$	$2 + 12 \times 3 = 38$	$2 \times 38 = 76$

总分数值为 $2 + 20 + 40 + 66 + 56 + 51 + 80 + 92 + 130 + 87 + 128 + 175 + 76 = 1003$ 。

因此，draw_territory 应该返回 $1003$ 。

输入格式

示例测试程序将按以下格式读取输入数据：

第 $1$ 行： $N, A, B$
第 $2 + i (0 \leq i \leq N - 1)$ 行： $D [i], L [i]$

输出格式

示例测试程序将按以下格式输出你的答案： - 第 $1$ 行，draw_territory 的返回值。

限制与约定

$3 \leq N \leq 200 000$
$0 \leq A, B \leq 10^{9}$
$1 \leq D [i] \leq 6 (0 \leq i \leq N - 1)$
$1 \leq L [i] (0 \leq i \leq N - 1)$
$L$ 中的元素之和不超过 $10^{9}$ 。
给出的行动序列所对应的路径一定是 封闭、简单 和暴露的。

子任务：

实际测试中，前 12 个 subtask 为数据包，后 8 个 subtask 为 8 个子任务。

( $3$ 分) $N = 3, B = 0$
( $6$ 分) $N = 3$
( $11$ 分) $L$ 中的元素之和不超过 $2000$
( $12$ 分) $B = 0, L$ 中的元素之和不超过 $200 000$
( $15$ 分) $B = 0$
( $19$ 分) $L$ 中的元素之和不超过 $200 000$
( $18$ 分) $L [i] = L [i + 1] (0 \leq i \leq N - 2)$
( $16$ 分) 无附加限制

时间限制： $2 s$

空间限制： $1 GB$

下载

样例数据下载

Universal Online Judge

UOJ

#651. 【APIO2021】六边形领域

实现细节

例子

输入格式

输出格式

限制与约定

下载