k734. 4. 開啟寶盒
Tags : APCS
Accepted rate : 368人/473人 ( 78% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-06-04 20:14

Content

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

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

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

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

Input

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

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

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

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

Output

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

Sample Input #1
5 5 1
2 0 1
0
2
4
3
1
1
2
4
3
3
Sample Output #1
3
Sample Input #2
10 8 2
3 6 5 2
5 6
2 7
2 0
4 5
5 1
3 0
4 2
2 4
5 3
5 6
5 0
0 6
1 7
3 2
2 1
7 3
4 7
4 5
4 1
7 5
Sample Output #2
5
測資資訊:
記憶體限制: 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
Hint :
Tags:
APCS
出處:
2023年6月APCS [管理者: algo.seacow@ ... (演算法海牛) ]

Status Forum 排行

ID User Problem Subject Hit Post Date
41022 glps1004@gma ... (Ian) k734
APCS 202306全解析
158 2024-06-25 15:55
41021 glps1004@gma ... (Ian) k734
APCS202306全解析
72 2024-06-25 15:51
38026 aoscar0717@g ... (吳赤赤宥) k734
C++題解
477 2023-10-22 22:07
37778 edoctopus322 ... (Moon Jam) k734
669 2023-10-07 01:14
37243 frankleeplay ... (LJH-code) k734
解題想法
474 2023-08-27 16:15