#2314. 网格
网格
网格
题目描述
CCF NOI 2024 四川省代表队评测活动 第二试 网格(grid) 网格(grid) 【题目描述】 给定一个节点排为 𝑛 行 𝑚 列的网格图,左上角为节点 (1, 1),右下角为节点 (𝑛, 𝑚)。每 个节点与其上下左右四个节点(如果存在)之间有一条带权边相连,一些边权初始为 1。 有一个机器人会从左上角出发,在网格图中移动。机器人可以从一个节点出发,沿与其相 连的边移动到这条边连接的另一个节点。注意只要两节点之间存在边,机器人就可以自由移 动。机器人不会重复移动到相同的节点,也不会重复经过相同的边。如果机器人无法进行合法 的移动,机器人就会停在目前所在的节点上。 机器人内置了一个计数器 𝑟,最初在左上角时 𝑟= 0。只要机器人通过了一条边权为 𝑣 的 边,计数器 𝑟 的值就会变为 gcd(𝑟, 𝑣)。这里定义 gcd(0, 𝑎) = 𝑎。如果机器人移动到右下角时 𝑟 不等于 1,这个机器人就会原地爆炸。 由于这个机器人十分地珍贵,你不希望机器人爆炸,所以你进行了 𝑞 次修改操作,每次选 择一条边权为 1 的边修改权值。以期对于机器人所有可能的移动情况,机器人都不会爆炸。 但这也不足以能让机器人在任何移动情况下都不爆炸,所以对于未修改的时候和每次修改后, 你想知道最少需要从图中移除多少条边,才能保证对于机器人所有可能的移动情况,机器人都 不会爆炸,也就是不存在从左上角到右下角的机器人移动路径,使得最终 𝑟≠1。 【输入格式】 从文件 grid.in 中读入数据。 输入的第一行包含四个整数 𝑛, 𝑚, 𝑞, 𝑐。 接下来 𝑛 行,每行 𝑚−1 个整数,第 𝑖 行第 𝑗 个数代表边 (𝑖, 𝑗) −(𝑖, 𝑗+ 1) 的权值。特别 地,当 𝑚= 1 时,这部分不会出现空行,直接进入下一部分的输入。 接下来 𝑛−1 行,每行 𝑚 个整数,第 𝑖 行第 𝑗 个数代表边 (𝑖, 𝑗) −(𝑖+ 1, 𝑗) 的权值。特别 地,当 𝑛= 1 时,这部分不会出现空行,直接进入下一部分输入。 接下来 𝑞 行,每行四个整数 𝑡, 𝑖, 𝑗, 𝑤, • 𝑡= 1 代表修改边 (𝑖, 𝑗) −(𝑖, 𝑗+ 1) 的权值为 𝑤; • 𝑡= 2 代表修改边 (𝑖, 𝑗) −(𝑖+ 1, 𝑗) 的权值为 𝑤。 请注意,当 𝑐= 1 时表示要求强制在线。具体来说,当 𝑐= 1 时,记上一次修改后的答案 为 lastans,对于第一次修改,lastans 的值为没有修改操作时的答案。那么: • 𝑡= 1 时,实际修改的 𝑖 为 (𝑖−1 + lastans) mod 𝑛+ 1,𝑗 为 (𝑗−1 + lastans) mod(𝑚−1) + 1; • 𝑡= 2 时,实际修改的 𝑖 为 (𝑖−1 + lastans) mod(𝑛−1) + 1,𝑗 为 (𝑗−1 + lastans) mod 𝑚+ 1。 请注意,这里对修改操作的调整不涉及权值 𝑤。保证只对边权为 1 的边进行修改。 第5 页 共11 页
CCF NOI 2024 四川省代表队评测活动 第二试 网格(grid) 【输出格式】 输出到文件 grid.out 中。 输出 𝑞+ 1 行,第一行表示没有修改时的答案,接下来 𝑞 行代表每次修改后的答案。 【样例1 输入】 1 2 3 2 0 2 2 1 3 3 6 4 1 6 2 5 2 1 1 12 6 1 1 2 10 【样例1 输出】 1 1 2 1 3 2 【样例1 解释】 对于最初,可以删除 (1, 2) 到 (2, 2) 的边。机器人沿可能到达右下角的两条路径到达右下 角时计数器均为 1。 对于第一次修改后,可以删除 (2, 2) 到 (2, 3) 的边。机器人沿可能到达右下角的两条路径 到达右下角时计数器均为 1。 对于第二次修改后,可以删除 (1, 1) 到 (1, 2) 和 (2, 2) 到 (2, 3) 的边。机器人沿可能到达 右下角的一条路径到达右下角时计数器为 1。 请注意,这组样例不符合任何测试点的条件限制。即使它满足数据范围限制,也不会出现 在测试点中。可以使用这组样例进行简单调试。 【样例2 输入】 1 2 2 0 0 2 3 3 12 4 2 6 第6 页 共11 页
CCF NOI 2024 四川省代表队评测活动 第二试 网格(grid) 【样例2 输出】 1 2 【样例2 解释】 对于最初,可以删除 (1, 1) 到 (1, 2) 和 (2, 1) 到 (2, 2) 的边。机器人无法到达右下角,也 就不会爆炸了。 【样例3】 见选手目录下的 grid/grid3.in 与 grid/grid3.ans。 这个样例满足测试点 6 ∼11 的条件限制。 【样例4】 见选手目录下的 grid/grid4.in 与 grid/grid4.ans。 这个样例满足测试点 16 ∼20 的条件限制。 【数据范围】 对于所有测试数据保证:1 ≤𝑛, 𝑚≤3 × 105,2 ≤𝑛× 𝑚≤3 × 105,0 ≤𝑞≤3 × 105。对 于初始和修改的所有边权 𝑤,满足 1 ≤𝑤≤109。 测试点编号 𝑛× 𝑚 𝑞 𝑐 1 ∼2 ≤20 ≤5 = 1 3 ∼5 ≤3 × 105 = 0 = 0 6 ∼11 ≤5 × 104 ≤5 × 104 12 ∼15 = 1 16 ∼20 ≤3 × 105 ≤3 × 105 第7 页 共11 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
2 3 2 0
2 1
3 6
1 6 2
2 1 1 12
1 1 2 10
1
1
2
样例 2
2 2 0 0
3
12
2 6
2