本篇含cpe必考1星題庫中21~30題。
本篇篇幅較大，可點選左列索引，跳至想查看的題目。
21. uva #11349
- 題目連結
- 題目大意：
- 核心思路：
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//32 .17
//non-negative and symmetric
//symmetric: 以中心點對稱
using namespace std;
int main(){
string s1, s2;
int t, n;
long long **m;
bool flag=true;
while(cin>>t)
{
for(int i=0; i<t; i++)
{
cin>>s1>>s2;
cin>>n;
//也可直接long long m[n][n];
m = new long long*[n];
for(int j=0; j<n; j++)
m[j] = new long long[n];
flag=true;
for(int j=0; j<n; j++)
{
for(int k=0; k<n; k++)
{
cin>>m[j][k];
if(m[j][k]<0)
flag = false;
}
}
if(flag == true)
{
for(int j=0; j<n; j++)
{
for(int k=0; k<n; k++)
{
if(n%2==1)
{
//n為奇數時，中心為n/2
if(m[j][k]!=m[(int)(n/2-(j-n/2))][(int)(n/2-(k-n/2))])
flag = false;
}
else
{
//n為偶數時，中心為n/2-0.5
if(m[j][k]!=m[(int)(n/2-0.5-(j-(n/2-0.5)))][(int)(n/2-0.5-(k-(n/2-0.5)))])
flag = false;
}
}
}
}
if(flag == true)
cout<<"Test #"<<i+1<<": Symmetric."<<endl;
else
cout<<"Test #"<<i+1<<": Non-symmetric."<<endl;
delete [] m;
}
}
return 0;
}
22. uva #11461
- 題目連結
- 題目大意：求閉區間內，有幾個完全平方數。
- 核心思路：
用sqrt()求某數平方根值(為double)並強制轉換成整數(int)，若該整數的平方等於某數，則某數為完全平方數。 - 解法一
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//18
using namespace std;
int main(){
//檢查到根號b
int a, b, cnt = 0;
while(cin>>a>>b)
{
cnt = 0;
if(a==0 && b==0)
break;
if(a>b || b<0)
cout<<0<<endl;
else
{
if(a<0)
a = 0;
//b以下的最大完全平方數開根號 - a以上的最小完全平方數開根號 + 1 = [a,b]間完全平方數數量
cnt = (int)floor(sqrt(b)) - (int)ceil(sqrt(a))+1;
cout<<cnt<<endl;
}
}
} - 解法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main()
{
int a, b;
int tmp;
int cnt;
while(cin>>a>>b)
{
if(a==0) break; //輸入為"0 0"程式結束，因題目有說 (0 < a ≤ b ≤ 100000)，檢查a是否為0即可判定是否結束
cnt=0;
for(int i=a; i<=b; i++)
{
tmp=(int)sqrt(i); //平方根值(double)強制轉換成整數(int)
if(tmp*tmp==i) cnt++; //為完全平方數，cnt++
}
cout<<cnt<<endl;
}
}
23. uva #11063
- 題目連結
- 題目大意：
- 核心思路：
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//31
using namespace std;
int main(){
int t = 0;
int n, sum;
int* b;
map<int, int> m;
string s;
bool flag;
while(cin>>n)
{
flag = true;
t++;
b = new int[n];
for(int i=0; i<n; i++)
{
cin>>b[i];
//檢查升序
if(b[i]<1 || (i>0 && b[i]<=b[i-1]))
flag = false;
}
//檢查sum
if(flag)
{
int i;
for(i=0; i<n; i++)
{
for(int j=i; j<n; j++){
sum = b[i]+b[j];
m[sum]++;
if(m[sum]>=2)
{
flag = false;
break;
}
}
if(!flag)
break;
}
}
if(flag)
cout<<"Case #"<<t<<": It is a B2-Sequence."<<endl;
else
cout<<"Case #"<<t<<": It is not a B2-Sequence."<<endl;
//記得要空行
cout<<endl;
delete b;
m.clear();
//讀空白行
getline(cin, s);
}
}24. uva #10071
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//9
//displacement: 位移=平均速度*時間
//因為是等加速度，0~2t的平均速度=t時刻的順時速度
using namespace std;
int main(){
int v, t;
while(cin>>v>>t){
cout<<v*(2*t)<<endl;
}
return 0;
}25. uva #10093
- 題目連結
- 題目大意：
- 核心思路：
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
using namespace std;
int main(){
string snum;
int inum;
//base至少要大於input所有位元的最小值
int min_base = 1;
while(cin>>snum)
{
min_base = 1;
inum = 0;
//inum
for(int i=0; i<snum.length(); i++)
{
int tmp;
if(snum[i]>='0' && snum[i]<='9')
tmp = snum[i]-'0';
else if(snum[i]>='A' && snum[i]<='Z')
tmp = 10+snum[i]-'A';
else if(snum[i]>='a' && snum[i]<='z')
tmp = 36+snum[i]-'a';
else
continue;
inum += tmp;
if(tmp+1>min_base)
min_base = tmp+1;
}
int i;
for(i=min_base; i<=62; i++)
{
if(i>1 && inum%(i-1)==0)
{
cout<<i<<endl;
break;
}
}
if(i>62)
cout<<"such number is impossible!"<<endl;
}
return 0;
}26. uva #948
- 題目連結
- 題目大意：
- 核心思路：
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//先用建表法存好費氏數列，因為測資的範圍，可以開 40 格就夠 (因為 [40] = 102334155 超過範圍)
//input是postive
using namespace std;
int f[40]={0,1};
//產生f
void generate_f(){
for(int i=2; i<40; i++)
{
f[i] = f[i-1]+f[i-2];
}
}
int main(){
int n, number, flag;
//產生費氏數列
generate_f();
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>number;
flag = false;
cout<<number<<" = ";
for(int i=39; i>=2; i--)
{
if(number>=f[i])
{
number -= f[i];
//已有開頭1'
flag = true;
cout<<"1";
}
else if(flag)
cout<<"0";
}
cout<<" (fib)"<<endl;
}
}
}27. uva #10019
- 題目連結
- 題目大意：
- 核心思路：
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//23 此題沒有負數輸入，不用考慮補數!!!
using namespace std;
int main(){
int n;
int m;
while(cin>>n){
for(int i=0; i<n; i++)
{
cin>>m;
//decimal
int tm=m, b1=0;
while(tm!=0)
{
if(tm%2==1) b1++;
tm/=2;
}
//hex:十六進制每位對應四位二進制
tm = m;
int hm=0, b2=0;
while(tm!=0)
{
//每次取十六進制一位 ，轉二進制
hm = (tm%10);
while(hm!=0)
{
if(hm%2==1) b2++;
hm/=2;
}
tm/=10;
}
cout<<b1<<" "<<b2<<endl;
}
}
}28. uva #10931
- 題目連結
- 題目大意：
- 核心思路：
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//7
using namespace std;
int main(){
long long i, p=0;
string b="";
while(cin>>i)
{
p = 0;
b = "";
if(i==0) break;
while(i!=0)
{
if(i%2==1)
{
b = "1"+b;
p++;
}
else
b = "0"+b;
i/=2;
}
cout<<"The parity of "<<b<<" is "<<p<<" (mod 2)."<<endl;
}
}29. uva #11005
- 題目連結
- 題目大意：
- 核心思路：
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
using namespace std;
int main(){
int n, t, num, tmp=0;
int cost_char[36] = {0};
while(cin>>n)
{
for(int i=0; i<n; i++)
{
for(int j=0; j<36; j++)
cin>>cost_char[j];
cout<<"Case "<<i+1<<":"<<endl;
cin>>t;
for(int j=0; j<t; j++)
{
cin>>num;
int cheap=-1;
int cheap_cnt = 0; //紀錄cheapest base的數量
int cost_base[37] = {0};
//run 36 base
for(int base=2; base<=36; base++){
tmp = num;
while(tmp!=0)
{
cost_base[base] += cost_char[tmp%base];
tmp/=base;
}
if(cheap == -1 || cost_base[base]<cheap)
{
cheap = cost_base[base];
cheap_cnt = 1;
}
else if(cost_base[base]==cheap)
cheap_cnt++;
}
//output
cout<<"Cheapest base(s) for number "<<num<<": ";
for(int base=2; base<=36; base++)
{
if(cost_base[base] == cheap)
{
cout<<base;
cheap_cnt--;
if(cheap_cnt==0)
cout<<endl;
else
cout<<" ";
}
}
}
//除了最後一筆測資，其他有一行空
if(i!=n-1)
cout<<endl;
}
}
}30. uva #10050
- 題目連結
- 題目大意：
- 核心思路：
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//24
using namespace std;
int main(){
int t, n, p;
while(cin>>t)
{
for(int i=0; i<t; i++)
{
cin>>n;//day
cin>>p;//#p
int cnt =0;
int *pi = new int[p];
for(int j=0; j<p; j++)
cin>>pi[j];
//run days
for(int k=1; k<=n; k++)
{
// not fri sa
if(k%7==0 || k%7==6)
continue;
//run pi
for(int m=0; m<p; m++){
if(k%pi[m]==0)
{
cnt++;
break;
}
}
}
cout<<cnt<<endl;
delete [] pi;
}
}
}