b438:
kingsbinary
Content
國王有一排開關，其上共有 N 個開關 S1, S2, S3, ..., SN。這排開關遠距離連接到一個顯示器的 M 個輸入端點 P1, P2, P3, ..., PM。這 M 個輸入端點分成 T 個長度不一的區間，每個區間內的端點，會順序連到某一個相應且相連的開關段。
即 Pi, Pi+1, Pi+2, ..., Pi+k-1 會連到 Sj, Sj+1, Sj+2, ..., Sj+k-1。換言之，一個開關可能連到多個輸入端子，且沒有任何端子是不和任何開關相連的。
顯示器會以輸入端子的 ON/OFF 狀態轉變成一個二進制數字 (P1 為最高位，而 PM 為最低位) 並把它的值顥示出來。這個數值是用為當天向國人獎賞的根據，數值越大，獎賞越多。這個顯示器是由一位大官負責人看管。
開關最初有部份是 ON 有部份是 OFF。國王會根據自己的心情，每天早上或將一個開關由 ON 轉 OFF 或由 OFF 轉 ON。而另一端的大官在中午時就會按顯示的數字發獎賞，數字越大，獎賞亦越大。其他時間內，若開關有變動，就會觸發警鐘。但你發現警鐘有漏洞，就是若你可以同時將一個 NO 的閞關轉 OFF 及另一個OFF 的開關轉 ON，則警鐘就不會被觸發。於是你打算每天中午前偷偷地更改閞關的狀態，使顯示器的輸出最大化，然後在大官發完獎賞後，再把開關復原。我們稱以上同時改變兩個開關的狀態的動作為一個操作，你希望找出每次使顯示器的輸出最大化所需要的最少操作次數。
Input
第一行上有 3 個正整數 N T Q，其中 1 ≤ N, T, Q ≤ 200000
- 隨後的一行上有一個由 0 及 1 組成的字串，字串的長度為 N。它代表開關的最初狀態。0 代表 OFF, １代表 ON.
- 再隨後有 T 行， 每行有 2 個整數 k 和 p。
- 其中第 i 行代表第 i 個端點區間上的端點數目 k，及該區間的第一個端點所連接的開關 Sp，每個區間內的端點都可完整地接到相應的開關段。
- 再隨後有 Q 行，每行上有一個 1 至 N 之間的正整數，代表給國王變換了狀態的開關編號。
另外，輸入端子的總數目，不會超過開關數目的 5 倍。
Output
輸出應有 Q 行，每行上有一個整數，代表在國王改變了一個開關後，要使顯示最大化時，所需要的最少操作次數。
Sample Input
#1
2 2 4 01 2 1 2 1 1 1 2 2
Sample Output
#1
0 1 0 1
測資資訊：
記憶體限制：
64
MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1K
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1K
不公開 測資點#2 (10%): 1.0s , <1K
不公開 測資點#3 (10%): 1.0s , <1K
不公開 測資點#4 (10%): 1.0s , <1K
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1K
Hint ：
其端點接駁情況如下:
0 1 開關
| |
| +-------+
+--+ | |
| +-----+ |
| | | |
| +-+ | |
| | | |
0 1 0 1 端點
第一個端點區間有 2 個端點，接到 S1 開始的開關段，第二個區間亦有 2 個端點，亦是接到以 S1 為開始的開關段。
而國王的選擇如下
- S1: 11 對應顯示為 1111 已是最大，不用操作
- S1: 01 對應顯示為 0101 一次操作 10 => 1010
- S2: 00 對應顯示為 0000 沒法操作
- S2: 01 對應顯示為 0101 一次操作 10 => 1010
Tags:
出處:
MOI-S 2025
[管理者：
]
| ID | User | Problem | Subject | Hit | Post Date |
沒有發現任何「解題報告」 |
|||||