UVa 12195
題目
http://domen111.github.io/UVa-Easy-Viewer/?12195
小李在學作曲，他想要做出每一小節長度都是 1 拍的曲子
可以用的音符有這些:
我們會拿到一串以 / 切割的字串，每個 / 之間代表一個小節的內容
請你判斷出其中有多少小節的長度剛好是 1 拍
想法1
每個小節我們都拿一個變數紀錄音符的總長度
我們可以跟著題目的想法做，遇到相對應的音符代號，就將長度記錄下來
在每個小節結束後，如果長度剛好為 1 拍，就記錄下來
輸入的部分我們可以這樣處理:
每次遇到 / 就看看我們紀錄音符長度的值是不是剛好為 1 拍，如果是就紀錄下來
無論有沒有剛好為 1 拍，都必須要將記錄長度的變數歸零
想法2
如果不想要處理麻煩的小數問題，可以這樣想
觀察可以用的音符，可以發現到所有音符長度的最小公倍數是 64
將全部的音符長度都乘上 64 後，都會變成整數，這樣就完美的忽略小數的問題了!
那麼一個小節的長度也就變成 64 囉!
Code 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include<iomanip>
using namespace std;
int main(){
string s;
while(cin>>s){
double cnt=0;
int ans=0;
if(s=="*") break;
for(int i=0 ; i<s.size() ; i++){
if(s[i] == '/'){
if(cnt == 1) ans++;
cnt=0;
}
else{
if(s[i] == 'W'){
cnt+=1.0;
}
else if(s[i] == 'H'){
cnt+=0.5;
}
else if(s[i] == 'Q'){
cnt+=0.25;
}
else if(s[i] == 'E'){
cnt+=0.125;
}
else if(s[i] == 'S'){
cnt+=0.0625;
}
else if(s[i] == 'T'){
cnt+=0.03125;
}
else if(s[i] == 'X'){
cnt+=0.015625;
}
}
}
cout<<ans<<'\n';
}
return 0;
}
|
Code 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<iostream>
#include<iomanip>
using namespace std;
int main(){
string s;
while(cin>>s){
int cnt=0;
int ans=0;
if(s=="*") break;
for(int i=0 ; i<s.size() ; i++){
if(s[i] == '/'){
if(cnt == 64) ans++;
cnt=0;
}
else{
if(s[i] == 'W'){
cnt+=64;
}
else if(s[i] == 'H'){
cnt+=32;
}
else if(s[i] == 'Q'){
cnt+=16;
}
else if(s[i] == 'E'){
cnt+=8;
}
else if(s[i] == 'S'){
cnt+=4;
}
else if(s[i] == 'T'){
cnt+=2;
}
else if(s[i] == 'X'){
cnt+=1;
}
}
}
cout<<ans<<'\n';
}
return 0;
}
|
時間複雜度分析
每次輸入會針對字串的每個字原作相對應的計算
而每個計算的時間複雜度為 $O(1)$
每筆測資的時間複雜度為 $O(len(s))$