APCSCamp 海量題目公開！ 連結
程式解題社網站 程式解題社網站上線了！
265 . 當堅果遇上松果
TopCoder
Tags
Description
在 NUT （National University of Taiwan）中，開了一間松果商店。
在這間松果商店中，總共掛了 $N$ 個「松果串」，第 $i$ 個松果串中的第 $j$ 顆松果的品種為 $a_{i, j}$ 。第 $i$ 個松果串的長度為 $s_i$ 。
在接下來 $Q$ 天，每天都會有一個客人帶著「堅果串」來松果商店。第 $i$ 天的客人會帶著長度為 $t_i$ 的堅果串來店內，這個堅果串的第 $j$ 顆堅果的品種為 $b_{i, j}$ 。
彥仁，身為松果商店的店長，對於「松果串」跟「堅果串」之間的相似度，有著特別的意義。定義一個長度為 $c$ 的松果串 $d_1, d_2, \dots, d_c$ ，以及長度為 $e$ 的堅果串 $f_1, f_2, \dots, f_e$ 的相似度為：
- 如果 $c \ne e$ ，也就是松果串跟堅果串的長度不一樣，那麼彥仁就覺得他們超級不像。因此彥仁定義這種情況的相似度為 $880301$ 。
- 否則，這兩串的東西的相似度，就是他們對齊後，品種不一樣的個數。正式的來說，相似度就是滿足 $d_i \ne f_i$ 的 $i$ 的個數
每個客人進來時，那些客人都會很好奇，他拿進松果商店的堅果串，跟松果商店的 $N$ 個松果串中的多少個松果串，滿足「客人的堅果串」跟「松果商店的松果串」的相似度 $\le 2$ 。
Input Format
輸入的第一行包含一個正整數 $N$ ，代表松果商店中的松果串個數。
接下來的 $N$ 行，每行代表一個松果商店的松果串。第 $i$ 行的第一個數字為 $s_i$ ，代表第 $i$ 個松果串的長度。接下來的 $s_i$ 個數字，分別就是 $a_{i, 1}, a_{i, 2}, \dots, a_{i, s_i}$ 。
接下來的一行，包含一個正整數 $Q$ ，代表接下來的客人個數。
接下來的 $Q$ 行，每行代表一個客人的堅果串。第 $i$ 行的第一個數字為 $t_i$ ，代表第 $i$ 個客人帶的堅果串的長度。接下來的 $t_i$ 個數字，分別就是 $b_{i, 1}, b_{i, 2}, \dots, b_{i, t_i}$ 。
- $1 \le N, Q \le 10^ 5$
- $1 \le s_i, t_i \le 10^ 5$
- $1 \le a_{i, j}, b_{i, j} \le 10^ 9$
- 松果商店的那 $N$ 個松果串皆相異，並且長度總和 $\le 10^ 5$ 。也就是說 $\sum_{i = 1}^ {N} s_i \le 10^ 5, \forall i \ne j, a_i \ne a_j$
- 客人的那 $M$ 個堅果串皆相異，並且長度總和 $\le 10^ 5$ 。也就是說 $\sum_{i = 1}^ {Q} t_i \le 10^ 5, \forall i \ne j, b_i \ne b_j$
Output Format
輸出 $Q$ 行，第 $i$ 行代表第 $i$ 個客人想要知道的資訊：有多少松果串，滿足那個松果串跟自己的堅果串的相似度 $\le 2$ 。
Sample Input 1
3 1 2 3
3 4 3 1
3
3 5 5 5
3 4 8 3
3 1 2 5
Sample Output 1
2
1
Hints
Problem Source
IOICamp 2020 Day5 pB
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~29 | 無額外限制 | 100 |