310109: CF1783E. Game of the Year
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Game of the Year
题意翻译
## 题目描述 Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：$ n $ 个编号从 $ 1 $ 到 $ n $ 的BOSS。 他俩将用以下方式与BOSS战斗 - Monocarp 进行 $ k $ 次尝试撒掉boss; - Polycarp 进行 $ k $ 次尝试撒掉boss; - Monocarp 进行 $ k $ 次尝试撒掉boss; - Polycarp 进行 $ k $ 次尝试撒掉boss; - ... Monocarp 在第 $ a_i $ 次尝试中撒掉了第 $ i $ 只BOSS。Polycarp 在第 $ b_i $ 次尝试中撒掉了第 $ i $ 只BOSS。其中一个人撒掉第 $ i $ 只BOSS后，他们就会尝试撒第 $ (i+1) $ 只BOSS。并且他们的尝试计数器都会清空。撒掉第 $ n $ 只BOSS后，游戏结束。 找到从$ 1 $ 到 $ n $所有的 $ k $ 值， 使得 Monocarp 可以杀死所有的BOSS。 ## 输入格式 第一行输入一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 样例数。 每个样例第一行输入一个整数 $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — BOSS的数量。 每个样例第二行输入 $ n $ 个整数： $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — Monocarp 撒死每只BOSS的尝试次数。 每个样例第三行输入 $ n $ 个整数： $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le n $ ) — Polycarp 撒死每只BOSS的尝试次数。 所有测试样例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $ . ## 输出格式 对于每个样例输出两行。第一行应该包含一个正整数 $ \mathit{cnt} $ — 从 $ 1 $ 到 $ n $ 使得 Monocarp 可以撒死所有BOSS的 $ k $ 的总数。第二行应该包含 $ \mathit{cnt} $ 个正整数 — 所有 $ k $ 的值。 ## 提示 考虑最后一组测试样例 使 $ k = 1 $。首先，Monocarp经过1次尝试撒死第一只BOSS。成功，因为 $ a_1 = 1 $。 然后，Monocarp进行一次尝试撒死第二只BOSS。不成功，因为 $ a_2 > 1 $。于是，Polycarp尝试了一下。也不成功，因为 $ b_2 > 1 $。然后Monocarp进行了另一次尝试。仍然不成功，因为 $ a_2 > 2 $。直到Polycarp 在第三次尝试撒掉了BOSS。Monocarp没能撒掉BOSS。因此，$ k = 1 $ 不是答案。 使 $ k = 2 $ . Monocarp仍然在他的第一次尝试中撒死了BOSS。然后，他进行了两次不成功的尝试未能撒死BOSS。然后，Polycarp进行了两次不成功的尝试。然后，Monocarp进行了两次尝试，并且在第四次尝试中撒掉了BOSS。撒掉第三只BOSS的方法也类似。首先，Monocarp进行两次不成功的尝试。然后，Polycarp进行两次不成功的尝试。然后，Monocarp还有两次尝试机会，但在这两次机会中第一次就撒死了BOSS，因为 $ a_3 = 3 $。 第四只BOSS也被Monocarp撒死。因此，$ k = 2 $ 是答案。题目描述
Monocarp and Polycarp are playing a computer game. This game features $ n $ bosses for the playing to kill, numbered from $ 1 $ to $ n $ . They will fight each boss the following way: - Monocarp makes $ k $ attempts to kill the boss; - Polycarp makes $ k $ attempts to kill the boss; - Monocarp makes $ k $ attempts to kill the boss; - Polycarp makes $ k $ attempts to kill the boss; - ... Monocarp kills the $ i $ -th boss on his $ a_i $ -th attempt. Polycarp kills the $ i $ -th boss on his $ b_i $ -th attempt. After one of them kills the $ i $ -th boss, they move on to the $ (i+1) $ -st boss. The attempt counters reset for both of them. Once one of them kills the $ n $ -th boss, the game ends. Find all values of $ k $ from $ 1 $ to $ n $ such that Monocarp kills all bosses.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of bosses. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — the index of attempt Monocarp kills each boss on. The third line contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le n $ ) — the index of attempt Polycarp kills each boss on. The sum of $ n $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
For each testcase, print two lines. The first line should contain a single integer $ \mathit{cnt} $ — the number of values of $ k $ from $ 1 $ to $ n $ such that Monocarp kills all bosses. The second line should contain $ \mathit{cnt} $ distinct integers — the values of $ k $ themselves.
输入输出样例
输入样例 #1
3
3
1 1 1
2 3 1
1
1
1
4
1 4 3 2
3 3 4 1输出样例 #1
3
1 2 3
1
1
2
2 4说明
Consider the last testcase of the example. Let $ k = 1 $ . First, Monocarp makes one attempt to kill the first boss. It's successful, since $ a_1 = 1 $ . Then, Monocarp makes one attempt to kill the second boss. It's unsuccessful, since $ a_2 > 1 $ . So, Polycarp makes an attempt then. It's also unsuccessful, since $ b_2 > 1 $ . Then, Monocarp makes another attempt. It's still unsuccessful, since $ a_2 > 2 $ . This goes on until Polycarp finally kills the boss on his third attempt. Monocarp didn't kill this boss, thus, $ k = 1 $ isn't the answer. Let $ k = 2 $ . Monocarp still kills the first boss on his first attempt. Then, he makes two unsuccessful attempts for the second boss. Then, Polycarp makes two unsuccessful attempts. Then, Monocarp makes two more attempts and kills the boss on his fourth attempt. The third boss is similar. First, two unsuccessful attempts by Monocarp. Then, two unsuccessful attempts by Polycarp. Then, Monocarp has two more attempts, but even his first one is successful, since $ a_3 = 3 $ . The fourth boss is also killed by Monocarp. Thus, $ k = 2 $ is the answer.Input
题意翻译
## 题目描述 Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：$ n $ 个编号从 $ 1 $ 到 $ n $ 的BOSS。 他俩将用以下方式与BOSS战斗 - Monocarp 进行 $ k $ 次尝试撒掉boss; - Polycarp 进行 $ k $ 次尝试撒掉boss; - Monocarp 进行 $ k $ 次尝试撒掉boss; - Polycarp 进行 $ k $ 次尝试撒掉boss; - ... Monocarp 在第 $ a_i $ 次尝试中撒掉了第 $ i $ 只BOSS。Polycarp 在第 $ b_i $ 次尝试中撒掉了第 $ i $ 只BOSS。其中一个人撒掉第 $ i $ 只BOSS后，他们就会尝试撒第 $ (i+1) $ 只BOSS。并且他们的尝试计数器都会清空。撒掉第 $ n $ 只BOSS后，游戏结束。 找到从$ 1 $ 到 $ n $所有的 $ k $ 值， 使得 Monocarp 可以杀死所有的BOSS。 ## 输入格式 第一行输入一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 样例数。 每个样例第一行输入一个整数 $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — BOSS的数量。 每个样例第二行输入 $ n $ 个整数： $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le n $ ) — Monocarp 撒死每只BOSS的尝试次数。 每个样例第三行输入 $ n $ 个整数： $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_i \le n $ ) — Polycarp 撒死每只BOSS的尝试次数。 所有测试样例的 $ n $ 之和不超过 $ 2 \cdot 10^5 $ . ## 输出格式 对于每个样例输出两行。第一行应该包含一个正整数 $ \mathit{cnt} $ — 从 $ 1 $ 到 $ n $ 使得 Monocarp 可以撒死所有BOSS的 $ k $ 的总数。第二行应该包含 $ \mathit{cnt} $ 个正整数 — 所有 $ k $ 的值。 ## 提示 考虑最后一组测试样例 使 $ k = 1 $。首先，Monocarp经过1次尝试撒死第一只BOSS。成功，因为 $ a_1 = 1 $。 然后，Monocarp进行一次尝试撒死第二只BOSS。不成功，因为 $ a_2 > 1 $。于是，Polycarp尝试了一下。也不成功，因为 $ b_2 > 1 $。然后Monocarp进行了另一次尝试。仍然不成功，因为 $ a_2 > 2 $。直到Polycarp 在第三次尝试撒掉了BOSS。Monocarp没能撒掉BOSS。因此，$ k = 1 $ 不是答案。 使 $ k = 2 $ . Monocarp仍然在他的第一次尝试中撒死了BOSS。然后，他进行了两次不成功的尝试未能撒死BOSS。然后，Polycarp进行了两次不成功的尝试。然后，Monocarp进行了两次尝试，并且在第四次尝试中撒掉了BOSS。撒掉第三只BOSS的方法也类似。首先，Monocarp进行两次不成功的尝试。然后，Polycarp进行两次不成功的尝试。然后，Monocarp还有两次尝试机会，但在这两次机会中第一次就撒死了BOSS，因为 $ a_3 = 3 $。 第四只BOSS也被Monocarp撒死。因此，$ k = 2 $ 是答案。Output
**年度游戏**
**题意翻译**
## 题目描述
Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：有 n 个编号从 1 到 n 的BOSS。
他们将按以下方式与BOSS战斗：
- Monocarp 进行 k 次尝试击败boss;
- Polycarp 进行 k 次尝试击败boss;
- Monocarp 进行 k 次尝试击败boss;
- Polycarp 进行 k 次尝试击败boss;
- ...
Monocarp 在第 a_i 次尝试中击败了第 i 只BOSS。Polycarp 在第 b_i 次尝试中击败了第 i 只BOSS。其中一个人击败第 i 只BOSS后，他们就会尝试击败第 (i+1) 只BOSS。并且他们的尝试计数器都会清零。击败第 n 只BOSS后，游戏结束。
找到从1到 n 所有的 k 值， 使得 Monocarp 可以击败所有的BOSS。
## 输入格式
第一行输入一个整数 t ( 1 ≤ t ≤ 10^4 ) — 样例数。
每个样例第一行输入一个整数 n ( 1 ≤ n ≤ 2 × 10^5 ) — BOSS的数量。
每个样例第二行输入 n 个整数： a_1, a_2, …, a_n ( 1 ≤ a_i ≤ n ) — Monocarp 击败每只BOSS的尝试次数。
每个样例第三行输入 n 个整数： b_1, b_2, …, b_n ( 1 ≤ b_i ≤ n ) — Polycarp 击败每只BOSS的尝试次数。
所有测试样例的 n 之和不超过 2 × 10^5 .
## 输出格式
对于每个样例输出两行。第一行应该包含一个正整数 cnt — 从 1 到 n 使得 Monocarp 可以击败所有BOSS的 k 的总数。第二行应该包含 cnt 个正整数 — 所有 k 的值。
**题目描述**
Monocarp and Polycarp are playing a computer game. This game features n bosses for the playing to kill, numbered from 1 to n.
They will fight each boss the following way:
- Monocarp makes k attempts to kill the boss;
- Polycarp makes k attempts to kill the boss;
- Monocarp makes k attempts to kill the boss;
- Polycarp makes k attempts to kill the boss;
- ...
Monocarp kills the i-th boss on his a_i-th attempt. Polycarp kills the i-th boss on his b_i-th attempt. After one of them kills the i-th boss, they move on to the (i+1)-st boss. The attempt counters reset for both of them. Once one of them kills the n-th boss, the game ends.
Find all values of k from 1 to n such that Monocarp kills all bosses.
**输入输出格式**
**输入格式**
The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.
The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 × 10^5) — the number of bosses.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the index of attempt Monocarp kills each boss on.
The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ n) — the index of attempt Polycarp kills each boss on.
The sum of n over all testcases doesn't exceed 2 × 10^5.
**输出格式**
For each testcase, print two lines. The first line should contain a single integer cnt — the number of values of k from 1 to n such that Monocarp kills all bosses. The second line should contain cnt distinct integers — the values of k themselves.**年度游戏** **题意翻译** ## 题目描述 Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：有 n 个编号从 1 到 n 的BOSS。 他们将按以下方式与BOSS战斗： - Monocarp 进行 k 次尝试击败boss; - Polycarp 进行 k 次尝试击败boss; - Monocarp 进行 k 次尝试击败boss; - Polycarp 进行 k 次尝试击败boss; - ... Monocarp 在第 a_i 次尝试中击败了第 i 只BOSS。Polycarp 在第 b_i 次尝试中击败了第 i 只BOSS。其中一个人击败第 i 只BOSS后，他们就会尝试击败第 (i+1) 只BOSS。并且他们的尝试计数器都会清零。击败第 n 只BOSS后，游戏结束。 找到从1到 n 所有的 k 值， 使得 Monocarp 可以击败所有的BOSS。 ## 输入格式 第一行输入一个整数 t ( 1 ≤ t ≤ 10^4 ) — 样例数。 每个样例第一行输入一个整数 n ( 1 ≤ n ≤ 2 × 10^5 ) — BOSS的数量。 每个样例第二行输入 n 个整数： a_1, a_2, …, a_n ( 1 ≤ a_i ≤ n ) — Monocarp 击败每只BOSS的尝试次数。 每个样例第三行输入 n 个整数： b_1, b_2, …, b_n ( 1 ≤ b_i ≤ n ) — Polycarp 击败每只BOSS的尝试次数。 所有测试样例的 n 之和不超过 2 × 10^5 . ## 输出格式 对于每个样例输出两行。第一行应该包含一个正整数 cnt — 从 1 到 n 使得 Monocarp 可以击败所有BOSS的 k 的总数。第二行应该包含 cnt 个正整数 — 所有 k 的值。 **题目描述** Monocarp and Polycarp are playing a computer game. This game features n bosses for the playing to kill, numbered from 1 to n. They will fight each boss the following way: - Monocarp makes k attempts to kill the boss; - Polycarp makes k attempts to kill the boss; - Monocarp makes k attempts to kill the boss; - Polycarp makes k attempts to kill the boss; - ... Monocarp kills the i-th boss on his a_i-th attempt. Polycarp kills the i-th boss on his b_i-th attempt. After one of them kills the i-th boss, they move on to the (i+1)-st boss. The attempt counters reset for both of them. Once one of them kills the n-th boss, the game ends. Find all values of k from 1 to n such that Monocarp kills all bosses. **输入输出格式** **输入格式** The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases. The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 × 10^5) — the number of bosses. The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the index of attempt Monocarp kills each boss on. The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ n) — the index of attempt Polycarp kills each boss on. The sum of n over all testcases doesn't exceed 2 × 10^5. **输出格式** For each testcase, print two lines. The first line should contain a single integer cnt — the number of values of k from 1 to n such that Monocarp kills all bosses. The second line should contain cnt distinct integers — the values of k themselves.
**题意翻译**
## 题目描述
Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：有 n 个编号从 1 到 n 的BOSS。
他们将按以下方式与BOSS战斗：
- Monocarp 进行 k 次尝试击败boss;
- Polycarp 进行 k 次尝试击败boss;
- Monocarp 进行 k 次尝试击败boss;
- Polycarp 进行 k 次尝试击败boss;
- ...
Monocarp 在第 a_i 次尝试中击败了第 i 只BOSS。Polycarp 在第 b_i 次尝试中击败了第 i 只BOSS。其中一个人击败第 i 只BOSS后，他们就会尝试击败第 (i+1) 只BOSS。并且他们的尝试计数器都会清零。击败第 n 只BOSS后，游戏结束。
找到从1到 n 所有的 k 值， 使得 Monocarp 可以击败所有的BOSS。
## 输入格式
第一行输入一个整数 t ( 1 ≤ t ≤ 10^4 ) — 样例数。
每个样例第一行输入一个整数 n ( 1 ≤ n ≤ 2 × 10^5 ) — BOSS的数量。
每个样例第二行输入 n 个整数： a_1, a_2, …, a_n ( 1 ≤ a_i ≤ n ) — Monocarp 击败每只BOSS的尝试次数。
每个样例第三行输入 n 个整数： b_1, b_2, …, b_n ( 1 ≤ b_i ≤ n ) — Polycarp 击败每只BOSS的尝试次数。
所有测试样例的 n 之和不超过 2 × 10^5 .
## 输出格式
对于每个样例输出两行。第一行应该包含一个正整数 cnt — 从 1 到 n 使得 Monocarp 可以击败所有BOSS的 k 的总数。第二行应该包含 cnt 个正整数 — 所有 k 的值。
**题目描述**
Monocarp and Polycarp are playing a computer game. This game features n bosses for the playing to kill, numbered from 1 to n.
They will fight each boss the following way:
- Monocarp makes k attempts to kill the boss;
- Polycarp makes k attempts to kill the boss;
- Monocarp makes k attempts to kill the boss;
- Polycarp makes k attempts to kill the boss;
- ...
Monocarp kills the i-th boss on his a_i-th attempt. Polycarp kills the i-th boss on his b_i-th attempt. After one of them kills the i-th boss, they move on to the (i+1)-st boss. The attempt counters reset for both of them. Once one of them kills the n-th boss, the game ends.
Find all values of k from 1 to n such that Monocarp kills all bosses.
**输入输出格式**
**输入格式**
The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases.
The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 × 10^5) — the number of bosses.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the index of attempt Monocarp kills each boss on.
The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ n) — the index of attempt Polycarp kills each boss on.
The sum of n over all testcases doesn't exceed 2 × 10^5.
**输出格式**
For each testcase, print two lines. The first line should contain a single integer cnt — the number of values of k from 1 to n such that Monocarp kills all bosses. The second line should contain cnt distinct integers — the values of k themselves.**年度游戏** **题意翻译** ## 题目描述 Monocarp 和 Polycarp 正在玩电脑游戏。游戏特点：有 n 个编号从 1 到 n 的BOSS。 他们将按以下方式与BOSS战斗： - Monocarp 进行 k 次尝试击败boss; - Polycarp 进行 k 次尝试击败boss; - Monocarp 进行 k 次尝试击败boss; - Polycarp 进行 k 次尝试击败boss; - ... Monocarp 在第 a_i 次尝试中击败了第 i 只BOSS。Polycarp 在第 b_i 次尝试中击败了第 i 只BOSS。其中一个人击败第 i 只BOSS后，他们就会尝试击败第 (i+1) 只BOSS。并且他们的尝试计数器都会清零。击败第 n 只BOSS后，游戏结束。 找到从1到 n 所有的 k 值， 使得 Monocarp 可以击败所有的BOSS。 ## 输入格式 第一行输入一个整数 t ( 1 ≤ t ≤ 10^4 ) — 样例数。 每个样例第一行输入一个整数 n ( 1 ≤ n ≤ 2 × 10^5 ) — BOSS的数量。 每个样例第二行输入 n 个整数： a_1, a_2, …, a_n ( 1 ≤ a_i ≤ n ) — Monocarp 击败每只BOSS的尝试次数。 每个样例第三行输入 n 个整数： b_1, b_2, …, b_n ( 1 ≤ b_i ≤ n ) — Polycarp 击败每只BOSS的尝试次数。 所有测试样例的 n 之和不超过 2 × 10^5 . ## 输出格式 对于每个样例输出两行。第一行应该包含一个正整数 cnt — 从 1 到 n 使得 Monocarp 可以击败所有BOSS的 k 的总数。第二行应该包含 cnt 个正整数 — 所有 k 的值。 **题目描述** Monocarp and Polycarp are playing a computer game. This game features n bosses for the playing to kill, numbered from 1 to n. They will fight each boss the following way: - Monocarp makes k attempts to kill the boss; - Polycarp makes k attempts to kill the boss; - Monocarp makes k attempts to kill the boss; - Polycarp makes k attempts to kill the boss; - ... Monocarp kills the i-th boss on his a_i-th attempt. Polycarp kills the i-th boss on his b_i-th attempt. After one of them kills the i-th boss, they move on to the (i+1)-st boss. The attempt counters reset for both of them. Once one of them kills the n-th boss, the game ends. Find all values of k from 1 to n such that Monocarp kills all bosses. **输入输出格式** **输入格式** The first line contains a single integer t (1 ≤ t ≤ 10^4) — the number of testcases. The first line of each testcase contains a single integer n (1 ≤ n ≤ 2 × 10^5) — the number of bosses. The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ n) — the index of attempt Monocarp kills each boss on. The third line contains n integers b_1, b_2, …, b_n (1 ≤ b_i ≤ n) — the index of attempt Polycarp kills each boss on. The sum of n over all testcases doesn't exceed 2 × 10^5. **输出格式** For each testcase, print two lines. The first line should contain a single integer cnt — the number of values of k from 1 to n such that Monocarp kills all bosses. The second line should contain cnt distinct integers — the values of k themselves.