本篇含cpe必考1星題庫中41~49題。
本篇篇幅較大，可點選左列索引，跳至想查看的題目。
41. uva #10062
- 題目連結
- 題目大意：
- 核心思路：
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//18
using namespace std;
struct ch{
int ascii;
int freq;
};
bool cmp(ch a, ch b){
if(a.freq == b.freq)
return a.ascii>b.ascii;
else
return a.freq<b.freq;
}
int main(){
string s;
while(getline(cin, s)){
//init
ch allch[95]; // ascii 32-126
for(int i=0; i<95; i++)
{
allch[i].ascii = i+32;
allch[i].freq = 0;
}
//cnt
for(int i=0; i<s.length(); i++)
{
allch[s[i]-32].freq += 1;
}
//sort
sort(allch, allch+95, cmp);
//cout
for(int i=0; i<95; i++)
{
if(allch[i].freq>0)
{
cout<<allch[i].ascii<<" "<<allch[i].freq<<endl;
}
}
cout<<endl;
}
}
42. uva #299
- 題目連結
- 題目大意：
- 核心思路：
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//16 bubble sort
using namespace std;
int main(){
int n, l;
while(cin>>n){
for(int k=0; k<n; k++)
{
cin>>l;
int cnt = 0;
int *c = new int[l];
for(int i=0; i<l; i++)
cin>>c[i];
//bubble sort
for(int i=0; i<l-1; i++) //run
{
for(int j=0; j<l-1-i; j++) //index
{
if(c[j]>c[j+1])
{
int tmp = c[j];
c[j] = c[j+1];
c[j+1] = tmp;
cnt++;
}
}
}
cout<<"Optimal train swapping takes "<<cnt<<" swaps."<<endl;
}
}
}43. uva #10226
- 題目連結
- 題目大意：
- 核心思路：
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//.04
using namespace std;
int main(){
int n;
string s;
map<string, int> cnt;
int num=0;
while(cin>>n){
//\n
cin.get();
//空白
getline(cin, s);
for(int i=0; i<n; i++)
{
if(i!=0)
cout<<endl;
num = 0;
while(getline(cin, s)){
if(s=="") break;
//cnt
cnt[s]++;
num++;
}
map<string, int>::iterator it;
for(it=cnt.begin(); it!=cnt.end(); it++){
cout<<it->first<<" "<<fixed<<setprecision(4)<<(double)(it->second)/num*100.0<<endl;
}
cnt.clear();
}
}
}44. uva #10189
- 題目連結
- 題目大意：
- 核心思路：
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
44
45
46
47//18
using namespace std;
int main(){
int dir[8][2] = {{-1, -1}, {0, -1}, {1, -1}, {1, 0}, {1, 1}, {0, 1}, {-1, 1}, {-1, 0}};
int n, m, cnt;
int testnum =0;
while(cin>>n>>m){
if(n==0 && m==0) break;
testnum++;
if(testnum!=1)
cout<<endl;
cout<<"Field #"<<testnum<<":"<<endl;
//cin
char f[n][m];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++)
cin>>f[i][j];
}
//run field
for(int i=0; i<n; i++){
for(int j=0; j<m; j++)
{
cnt = 0;
if(f[i][j]!='*')
{
for(int k=0; k<8; k++)
{
if(j+dir[k][0]>=0 && j+dir[k][0]<m && i+dir[k][1]>=0 && i+dir[k][1]<n)
{
if(f[i+dir[k][1]][j+dir[k][0]]=='*')
cnt++;
}
}
cout<<cnt;
}
else
cout<<"*";
}
cout<<endl;
}
}
}
45. uva #10409
- 題目連結
- 題目大意：
- 核心思路：
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
44
using namespace std;
int main(){
int n, tmp;
string s;
while(cin>>n){
if(n==0) break;
//紀錄die 正、北、西
int die[3] = {1, 2, 3};
for(int i=0; i<n; i++)
{
cin>>s;
if(s=="north")
{
tmp = die[0];
die[0] = 7-die[1]; //top:south
die[1] = tmp; //north:top
}
else if(s=="south")
{
tmp = die[0];
die[0] = die[1];
die[1] = 7-tmp;
}
else if(s=="east")
{
tmp = die[0];
die[0] = die[2];
die[2] = 7-tmp;
}
else if(s=="west")
{
tmp = die[0];
die[0] = 7-die[2];
die[2] = tmp;
}
}
cout<<die[0]<<endl;
}
}
46. uva #10415
- 題目連結
- 題目大意：
- 核心思路：
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74//29
using namespace std;
int main(){
char c[14] = {'c', 'd', 'e', 'f', 'g', 'a', 'b', 'C', 'D', 'E', 'F', 'G', 'A', 'B'};
int finger[14][10] = {
{0, 1, 1, 1, 0, 0, 1, 1, 1, 1},
{0, 1, 1, 1, 0, 0, 1, 1, 1, 0},
{0, 1, 1, 1, 0, 0, 1, 1, 0, 0},
{0, 1, 1, 1, 0, 0, 1, 0, 0, 0},
{0, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 0, 0, 1, 1, 1, 0},
{1, 1, 1, 1, 0, 0, 1, 1, 0, 0},
{1, 1, 1, 1, 0, 0, 1, 0, 0, 0},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 0, 0, 0},
{1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
};
int t;
string s;
int last = -1; //記錄上一個音
while(cin>>t){
//\n
cin.get();
for(int i=0; i<t; i++){
//用getline避免空白notes沒讀到
getline(cin, s);
int cnt[10] = {0};
for(int j=0; j<s.length(); j++)
{
//run c
for(int k=0; k<14; k++)
{
if(s[j] == c[k])
{
//run finger
for(int l=0; l<10; l++)
{
if(j==0)
{
cnt[l]+=finger[k][l];
}
else
{
//上一個音沒按，這個音按：press+1
if(finger[k][l]-finger[last][l] == 1)
cnt[l] += 1;
}
}
//update last
last = k;
break;
}
}
}
//cout
for(int j=0; j<10; j++)
{
cout<<cnt[j];
if(j!=9)
cout<<" ";
}
cout<<endl;
}
}
}
47. uva #118
- 題目連結
- 題目大意：
- 核心思路：
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
using namespace std;
int main(){
int gx, gy;
int rx, ry, rdir;
char ror;
string s;
char dir[4] = {'N', 'E', 'S', 'W'};
char dir_pos[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while(cin>>gx>>gy)
{
//紀錄曾掉落位置
int lost[gx][gy];
for(int i=0; i<gx; i++)
for(int j=0; j<gy; j++)
lost[gx][gy] = 0;
while(cin>>rx>>ry>>ror)
{
cin.get();
getline(cin, s);
//init
for(int i=0; i<4; i++)
{
if(ror == dir[i])
{
rdir = i;
break;
}
}
int i;
for(i=0; i<s.length(); i++){
if(s[i] == 'L')
{
rdir = (rdir+3)%4;
}
else if(s[i] == 'R')
{
rdir = (rdir+1)%4;
}
else if(s[i] == 'F')
{
rx = rx+dir_pos[rdir][0];
ry = ry+dir_pos[rdir][1];
if(rx<0 || rx>gx || ry<0 ||ry>gy)
{
//上一步位置有曾記錄過，則機器人會忽略此指令
if(lost[rx-dir_pos[rdir][0]][ry-dir_pos[rdir][1]] == 1)
{
//復原
rx -= dir_pos[rdir][0];
ry -= dir_pos[rdir][1];
}
else //掉落
{
if(rx>gx) rx = gx;
else if(rx<0) rx = 0;
if(ry>gy) ry = gy;
else if(ry<0) ry = 0;
lost[rx][ry] = 1;
break;
}
}
}
}
cout<<rx<<" "<<ry<<" "<<dir[rdir];
if(i<s.length())
cout<<" LOST";
cout<<endl;
}
}
}
48. uva #11150
- 題目連結
- 題目大意：
- 核心思路：
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//最後若剩兩瓶可樂空瓶，可以多借一瓶空瓶，最後還回去1瓶
//總共借超過一瓶都會虧!!
using namespace std;
int main(){
int n;
int cola = 0;
while(cin>>n){
cola = n;
while(n>=3){
//新可樂
cola += n/3;
//新空杯
n=n/3+n%3;
}
//如果最後剩兩瓶
if(n==2)
cola+=1;
cout<<cola<<endl;
}
}
49. uva #11321
- 題目連結
- 題目大意：
- 核心思路：
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
using namespace std;
int n, m;
bool cmp(int a, int b){
if(a%m == b%m){
if(a%2 != 0 && b%2 == 0) return true; //這裡不要寫a%2==1，因為負奇數%2為-1!!!!!!
else if(a%2 == 0 && b%2 != 0) return false;
else if(a%2 != 0 && b%2 != 0) return a>b;
else return a<b;
}
else
return (a%m)<(b%m);
}
int main(){
while(cin>>n>>m){
cout<<n<<" "<<m<<endl;
if(n==0 && m==0) break;
int *num = new int[n];
for(int i=0; i<n; i++)
{
cin>>num[i];
}
//sort
sort(num, num+n, cmp);
//cout
for(int i=0; i<n; i++)
cout<<num[i]<<endl;
}
}