a260: The Jet-Black Wings
標籤 : dp tree
通過比率 : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2022-05-09 08:38

內容

pdf:請看pG

https://drive.google.com/file/d/1OPQBuMYzQWblmuyJDCk5TYc9RJqR8WbA/view?usp=sharing

 

「呃啊...可惡!...要發狂了嗎!」

艾迪,一個自稱為「漆黑之翼」的人,正在與名為「Dark Reunion」的邪惡組織作戰。
接著他就驚醒了,原來只是一場夢阿...

「我一定要變得更強。」 艾迪在心中激勵自己。

為了成為一名強悍的戰鬥者,艾迪認真的鍛鍊自己。
在他的練習中,他收集了 $N$ 顆魔法石頭,第 $i$ 顆魔法石頭有著 $A_i$ 單位的黑暗力量。
艾迪會進行 $Q$ 次操作,每次操作有以下兩種:

$1\ X$: 使用 $X$ 單位的黑暗力量於每顆魔法石頭. 因此,第 $i$ 顆魔法石頭的暗黑力量會變成$A_i \oplus X$ 單位。

$2\ K$: 將所有的魔法石頭按照他們的黑暗力量由小到大排序,並加總前 $K$ 顆魔法石頭的黑暗力量。

你能夠幫助艾迪確認他是否正確嗎?

$x \oplus y$ 表示將 $x$ 與 $y$ 進行互斥或操作。這個操作存在於所有常用的程式語言中,例如:C++ 與 Java 即是使用「^」,而 Pascal 則使用「xor」。

 

輸入說明

第一行有一個數字 $T$,表示有 $T$ 組測試資料。

每組測試資料的第一行有兩個數字 $N$, $Q$,表示艾迪蒐集的魔法石頭個數與訓練的操作次數。

每組測試資料的第二行有 $N$ 個數字 $A_1, A_2, \ldots, A_N$,
其中 $A_i$ 表示第 $i$ 顆魔法石頭的黑暗力量。

接著有 $Q$ 行,每行為一個操作「$1\ X$」或「$2\ K$」。

可假設:
• $T ≤ 1000$

• $1 ≤ N, Q ≤ 100000$

• $0 ≤ A_i , X<2^{31} $

• $1 ≤ K ≤ N $

• ⾄多只有 5 組測試資料的 $N + Q > 200$

輸出說明

對於每個操作「$2\ K$」輸出一個數字於一行,表示排序後前 $K$ 顆魔法石頭的黑暗力量總和。

 

範例輸入 #1
1
3 6
4 8 3
1 3
1 1
2 3
1 2
2 2
2 1
範例輸出 #1
17
7
3
測資資訊:
記憶體限制: 256 MB
公開 測資點#0 (100%): 3.0s , <10M
提示 :
標籤:
dp tree
出處:
2017 TOPC pG [管理者:
haha (大學長)
]


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