k734. 4. 開啟寶盒 - 高中生程式解題系統

內容

已知有 $n$ 個寶盒編號 $0$ 到 $n - 1$ 以及 $m$ 種鑰匙編號 $0$ 到 $m - 1$ 。一開始你有 $t$ 種鑰匙分別為 $x_{1}, \dots, x_{t}$ 。

每一個寶盒要打開都需要同時擁有 $k$ 種鑰匙，第 $i$ 個寶盒分別需要 $r_{i 1}, r_{i 2}, \dots, r_{i k}$ 種類的鑰匙。每個寶盒打開後都會得到 $k$ 種鑰匙，第 $i$ 個寶盒打開後分別會得到 $s_{i 1}, s_{i 2}, \dots, s_{i k}$ 種類的鑰匙，當拿到新的鑰匙之後可以繼續開啟新的寶盒。保證寶盒內的鑰匙不會重複，並且每種鑰匙可以開啟的寶盒數量不超過 $60$ 。

請輸出最多可以開啟多少個寶盒。

子問題一 (20%) $k = 1$ , $1 \leq n, m \leq 100$
子問題二 (20%) $k = 1$ , $1 \leq n, m \leq 10^{5}$
子問題三 (60%) $1 \leq k \leq 5$ , $1 \leq n, m \leq 10^{5}$

輸入說明

第一行輸入三個正整數 $n, m, k (1 \leq n, m \leq 10^{5}, 1 \leq k \leq 5)$ 代表有 $n$ 個寶盒， $m$ 種鑰匙以及每個寶盒需要的鑰匙數量 $k$ 。

接下來輸入一行，第一個數字 $t$ 代表一開始有的鑰匙種類數量，後面有 $t$ 個數字代表這些鑰匙分別的種類。

接下來有 $n$ 行，每一行有 $k$ 個數字，代表要開啟第 $i$ 個寶盒的第 $j$ 種鑰匙為 $r_{i j}$ 。

最後有 $n$ 行，每一行有 $k$ 個數字，代表開啟第 $i$ 個寶盒後得到的第 $j$ 種鑰匙為 $s_{i j}$ 。

輸出說明

輸出一個正整數，代表可以開啟的寶盒數量。

範例輸入 #1

範例輸出 #1

範例輸入 #2

範例輸出 #2

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (5%): 1.0s , <1K
公開測資點#1 (5%): 1.0s , <1K
公開測資點#2 (5%): 1.0s , <1K
公開測資點#3 (5%): 1.0s , <1K
公開測資點#4 (5%): 1.0s , <1M
公開測資點#5 (5%): 1.0s , <1M
公開測資點#6 (5%): 1.0s , <10M
公開測資點#7 (5%): 1.0s , <10M
公開測資點#8 (5%): 1.0s , <10M
公開測資點#9 (5%): 1.0s , <10M
公開測資點#10 (5%): 1.0s , <10M
公開測資點#11 (5%): 1.0s , <10M
公開測資點#12 (5%): 1.0s , <10M
公開測資點#13 (5%): 1.0s , <10M
公開測資點#14 (5%): 1.0s , <10M
公開測資點#15 (5%): 1.0s , <10M
公開測資點#16 (5%): 1.0s , <10M
公開測資點#17 (5%): 1.0s , <10M
公開測資點#18 (5%): 1.0s , <10M
公開測資點#19 (5%): 1.0s , <10M

提示：

標籤:

APCS

出處:

2023年6月 APCS [管理者： algo.seacow@gmail.com

algo.seacow@ ... (演算法海牛) ]

編號	身分	題目	主題	人氣	發表日期
41022	glps1004@gma ... (Ian)	k734	APCS 202306全解析	327	2024-06-25 15:55
41021	glps1004@gma ... (Ian)	k734	APCS202306全解析	165	2024-06-25 15:51
38026	aoscar0717@g ... (吳赤赤宥)	k734	C++題解	594	2023-10-22 22:07
37778	edoctopus322 ... (Moon Jam)	k734	解題思路（含一些小技巧）	840	2023-10-07 01:14
37243	frankleeplay ... (LJH-code)	k734	解題想法	591	2023-08-27 16:15