a128: 珠寶
標籤 : 2019 npsc pA 初賽
通過比率 : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2021-10-27 16:46

內容

bb 是個寶石蒐藏家,某天他家旁邊新開了一間珠寶行,他希望能在這間珠寶行裡蒐集到最多種類的寶石。 這個世界上一共有 m 種寶石,這間珠寶行販售

的 n 個珠寶組合中每個都包含了其中一些 種類的寶石。bb 可以購買不限數量的珠寶組合,每個組合一旦購買了就會得到那個組合裡的 所有寶石,不能只

把一部分的寶石拿走。不過由於一些特殊的魔法,如果 bb 同時蒐集到了所 有種類的寶石就會爆炸,所以他購買的所有組合聯集起來不能含有所有種類的

寶石。 這間珠寶行有時會修改組合裡含有的寶石種類來配合消費者的喜好,每次的修改會把某種 寶石加入某個組合中、或是把某種寶石從某個組合中移

除。 bb 已經事先知道了珠寶行接下來依序 q 次的修改方式,現在他想知道如果在最一開始、 以及每次的修改之後去店裡消費,在不爆炸的前提下,分別

最多可以買到多少種寶石?

輸入說明

輸入的第一行有三個正整數 n, m, q 代表販售的組合個數、寶石種類數、以及珠寶行修改的次數。

接下來 n 行,每行有一個長度為 m 的 01 字串,如果第 i 行的第 j 個字元是 1,代表最一開始第 i 個組合裡含有第 j 種寶石,若是 0 則代表沒有。

接下來 q 行,代表 q 次的修改。

每行有兩個正整數 p,t,代表改變第 p 個組合中第 t 種寶石的存在性。也就是如果該種寶石本來存在,就把他移除,不然就把他加入。

條件:

1 ≤ n,m ≤ 300

1 ≤ q ≤ 50000

1 ≤ p ≤ n

1 ≤ t ≤ m

輸出說明

輸出有 q + 1 行,分別代表最一開始、以及每次修改後的答案。

範例輸入 #1
3 4 6
1010
0000
0101
2 3
3 2
1 1
3 1
3 2
3 3
範例輸出 #1
2
3
3
2
3
3
1
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1M
公開 測資點#1 (10%): 1.0s , <1M
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1M
公開 測資點#9 (10%): 1.0s , <1M
提示 :

dp, greedy (CF 2100)

標籤:
2019 npsc pA 初賽
出處:
[管理者: ]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」