本篇含cpe必考1星題庫中11~20題。
本篇篇幅較大，可點選左列索引，跳至想查看的題目。
11. uva #10252
注意：只要字串x可”排列”成 s1, s2的子字串就行，不用考慮x排成的s1子字串 是否和s2排成的子字串順序相同
x字串中的字母可有重複
1 | //.19 |
12. uva #490
- 題目連結
注意：字串陣列長度要設>=101或讀入100個字串後要停止繼續讀入字串(break while loop)，否則會run time error1
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//19
using namespace std;
int main(){
string s[101];
int cnt=0;
int maxlen = 0;
while(getline(cin, s[cnt]))
{
int len = s[cnt].length();
maxlen = maxlen>=len?maxlen:len;
cnt+=1;
}
for(int i=0; i<maxlen; i++)
{
for(int j=cnt-1; j>=0; j--)
{
if(i<=s[j].length()-1)
cout<<s[j][i];
else //字串長度不足，補空白
cout<<" ";
}
cout<<endl;
}
}13. uva #272
- 題目連結
- 題目大意：
- 核心思路：
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//8
using namespace std;
int main(){
string s;
int cnt=0;
while(getline(cin, s))
{
for(int i=0; i<s.length(); i++)
{
if(s[i] == '"')
{
cnt=(cnt+1)%2;
if(cnt==1)
cout<<"``";
else
cout<<"''";
}
else
cout<<s[i];
}
cout<<endl;
}
}14. uva #12019
- 題目連結
- 題目大意：
- 核心思路：
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//37
using namespace std;
int main(){
string day[7] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
int num_day[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
int n, m, d;
// 依題目敘述，4/4是monday
//算4/4號是該年第幾天
int base_day = 4;
for(int i=0; i<3; i++)
base_day+=num_day[i];
//算1/1號是星期幾
int base = 6-((base_day-1)%7);
while(cin>>n)
{
for(int i=0; i<n; i++)
{
cin>>m>>d;
// 第幾天
int days = 0;
for(int j=0; j<m-1; j++)
days+=num_day[j];
days+=d;
//星期幾
int day_index = (days + base)%7;
cout<<day[day_index]<<endl;
}
}
}15. uva #10038
- 題目連結
- 題目大意：
- 核心思路：
jolly jumper定義:給n個數，此n個數的差值在1~n-1之間，且不重複。
n=1時，視為jolly jumper1
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//24
using namespace std;
int main(){
int n;
while(cin>>n){
int *cnt = new int[n];
int *num = new int[n];
for(int i=0; i<n; i++)
{
cin>>num[i];
cnt[i]=0;
}
if(n==1)
{
cout<<"Jolly"<<endl;
}
else
{
int j=0;
for(j=0; j<n-1; j++)
{
int diff = abs(num[j+1]-num[j]);
if(diff<=0 || diff>n-1)
{
cout<<"Not jolly"<<endl;
break;
}
cnt[diff]+=1;
}
if(j>=n-1)
{
int k=0;
for(k=1; k<n; k++)
{
if(cnt[k]==0)
{
cout<<"Not jolly"<<endl;
break;
}
}
if(k>=n)
cout<<"Jolly"<<endl;
}
}
}
}16. uva #10056
- 題目連結
- 題目大意：
- 核心思路：
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//54
using namespace std;
//第i個人贏的機率prob
//prob = (q^(i-1))*p+(q^(i-1+n))*p+(q^(i-1+2n))*p+...
//無窮等比級數:
//首項:(q^(i-1))*p，公比:p^n，帶入公式
//prob=(q^(i - 1) * p)*(1)/(1-q^n)
int main(){
int in, n, i;
double p, q, prob;
while(cin>>in)
{
for(int k=0; k<in; k++)
{
cin>>n>>p>>i;
q= 1.0-p;
//公式未定義情況
if(q==1)
{
cout<<"0.0000"<<endl;
}
else
{
prob = (pow(q, (i - 1)) * p)/(1-pow(q,n));
cout<<fixed<<setprecision(4)<<prob<<endl;
}
}
}
return 0;
}17. uva #10170
- 題目連結
- 題目大意：
- 核心思路：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22//19 請都設為long long 避免自動擴位會超時
using namespace std;
//s, s+1, s+2 + ...= d
int main(){
long long s, d, days;
while(cin>>s>>d)
{
days = 0;
while(days<d)
{
days+=s;
s++;
}
cout<<s-1<<endl;
}
}18. uva 10268
- 題目連結
- 題目大意：求微分。
- 核心思路：
照題目給的輸入及定義求微分。
本來想用中的pow()函式運算指數，但有bug一直找不到，只好放棄QQ有人知道為甚麼嗎?(0的次方已有做另外的處理了…還是不行) 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//14
using namespace std;
//x!=0 && y==0 ==> 1
//x==0 && y==0 ==> 1
//x = = 0.和y< 0 ==> inf
int main(){
vector<int> a;
string s;
int x, tmpa, n, d, powx;
while(cin>>x)
{
d = 0;
getline(cin, s);
while(cin>>tmpa){
a.push_back(tmpa);
if(cin.get()=='\n')
break;
}
n=a.size()-1;
powx = 1;
for(int i=n-1; i>=0; i--)
{
d+= a[i]*(n-i)*powx;
powx*=x;
}
cout<<d<<endl;
a.clear();
}
return 0;
}19. uva 10783
- 題目連結
- 題目大意：
- 核心思路：
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//7
using namespace std;
int main(){
int t, s, e, sum;
while(cin>>t)
{
for(int i=0; i<t; i++)
{
cin>>s>>e;
if(s%2==0) s+=1;
sum = 0;
for(int j=s; j<=e; j+=2)
sum += j;
cout<<"Case "<<i+1<<": "<<sum<<endl;
}
}
return 0;
}20. uva 10812
- 題目連結
- 題目大意：
- 核心思路：
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//14
//non-negative integer
//big -small = d
//big + small = s
//big = (s+d)/2
//small = s-(s+d)/2
using namespace std;
int main(){
int n, s, d, big, small;
while(cin>>n){
for(int i=0; i<n; i++)
{
cin>>s>>d;
//若s或d為負，則big或small可能為負
//s<d,則big為負
//s+d不為偶數，則big和small不為整數
if(s<0 || d<0 || s<d || (s+d)%2==1)
{
cout<<"impossible"<<endl;
}
else
{
big = (s+d)/2;
small = s-big;
cout<<big<<" "<<small<<endl;
}
}
}
}