切換
舊版
前往
大廳
主題

ZeroJudge - e531: 10415 - Eb Alto Saxophone Player 解題心得

Not In My Back Yard | 2019-11-14 23:04:40 | 巴幣 0 | 人氣 596

題目連結:


題目大意:
給定薩克斯風的音調之指法:
c: finger 2~4, 7~10
d: finger 2~4, 7~9
e: finger 2~4, 7, 8
f: finger 2~4, 7
g: finger 2~4
a: finger 2, 3
b: finger 2
C: finger 3
D: finger 1~4, 7~9
E: finger 1~4, 7, 8
F: finger 1~4, 7
G: finger 1~4
A: finger 1~3
B: finger 1~2

給定一正整數 t (1 ≦ t ≦ 1000),代表有 t 首曲子。每首曲子的指法佔一列的輸入。曲子是由上面的指法表中的英文字母組成。(曲子可能為空)

求彈完每首曲子後,每根手指(1 ~ 10)各自總共按下幾次。

注:當彈完一個音調後換到下一個音調時,若兩音調有相同手指需要按下,則轉換之間該手指不須放開再按下,保持按下的狀態即可。



範例輸入:
3
cdefgab
BAGFEDC
CbCaDCbCbCCbCbabCCbCbabae


範例輸出:
0 1 1 1 0 0 1 1 1 1
1 1 1 1 0 0 1 1 1 0
1 8 10 2 0 0 2 2 1 0


解題思維:
這理所當然的只能模擬。但是要怎麼模擬比較有效率呢?因為手指只會有按下、放開兩種狀態,因此我們可以把 10 根手指看作 10 個二進位位元。

因此音調 c 可寫為 1111001110 (由左到右是第 10 到第 1 根手指的狀態)、音調 d 可寫為 0111001110 ……以此類推。

接著就是將曲子中的每個音調依序掃過一次。一開始每根手指都是放開的狀態(其實並沒有,可以看到手指 5 、 6 從沒用到。因為你需要它們用來「拿」樂器,但是完全不影響答案)。每遇到一個音調,就看先前的手指狀態與此音調的指法之差別(用位元運算判斷)。當有手指按下的時候,該手指的次數就 + 1 。

最後,將所有手指的按下次數依序輸出即可。

此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作