貝貝's Blog

記錄、學習、生活

0%

刷題記錄 1： cpe必考1星題庫1~10題

發表於 更新於 分類於 ， ，

本篇含cpe必考1星題庫中1~10題。

本篇篇幅較大，可點選左列索引，跳至想查看的題目。
最近又開始考cpe啦，邊複習邊把過去不夠直覺的程式碼及錯誤的部分作修正!!(修正至第10題)
大家考試加油呀🌞

1. uva #10041

  • 題目連結

  • 題目大意：
    選一個點，其到其他點距離總和最短。

    • 注意：點有可能有重複

  • 核心思路：找中位數。

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
//19
#include<iostream>
#include<vector>
#include <algorithm> //為了使用 sort

using namespace std;

int main(){
    int n, r, s;

    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>r;
        vector<int> vs;
        int mid = r/2;
        for(int j=0; j<r; j++)
        {
            cin>>s;
            vs.push_back(s);
        }
        sort(vs.begin(), vs.end());
        int m = vs[mid];
        int sum = 0;
        for(int j=0; j<r; j++)
        {
            int d = m-vs[j];
            if(d<0)
                d*=-1;
            sum += d;
        }
        cout<<sum<<endl;
    }
}

2. uva #10055

  • 題目連結
  • 題目大意：
    求兩軍人數差(絕對值)。
    • 注意：
      題目提到數字最高可到2^32，而int的整數範圍為-(2^31) ~ 2^31-1，所以不能使用int來讀取。
      long long 範圍：-(2^64) ~ 2^64-1
      unsigned long long 使用abs()會有overload報錯
      且雖說題目提到敵軍數量必大於我軍，但無法得知第一個讀取的數字為敵軍還是我軍人數，所以計算時仍須加上絕對值。:))
  • 核心思路：所求之人數差為 兩數相減加絕對值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    #include <iostream>
    using namespace std;

    int main()
    {

        long long h, o;
        while(cin>>h>>o)
        {
            cout<<abs(o-h)<<endl;
        }
    }

3. uva #10035

  • 題目連結

  • 題目大意：
    給兩數做加法，計算有多少次進位。

    • 注意：此題數目數目在int範圍內。無需使用字串或其他方式方式讀入。

  • 核心思路：

    1. 位數對齊後一一對應，由後往前相加(前一次的進位也要加)
    2. 數字%10 可取得某位數值
    3. 需要一個變數紀錄前一次進位
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
// 11
#include <iostream>
using namespace std;

int main()
{
	int n1, n2;	//數字1，數字2
	while(cin>>n1>>n2)
	{
		int carry=0;	//記錄進位
		int cnt=0;
		if(n1==0&&n2==0) break;
		while(n2>0 || n1>0)
		{
			if(n2<=0)	//n2前方沒位數了
			{
				if(n1%10+carry>=10)	//有進位
				{
					cnt++;
					carry=1;
				}
				else carry=0;
				n1/=10;
			}
			else if(n1<=0)	//n1前方沒位數了
			{
				if(n2%10+carry>=10)	//有進位
				{
					cnt++;
					carry=1;
				}
				else carry=0;
				n2/=10;
			}
			else	//兩數皆還有位數
			{
				if((n1%10+n2%10+carry)>=10)
				{
					cnt++;
					carry=1;
				}
				else carry=0;
				n1/=10;
				n2/=10;
			}
		}
		if(cnt==0) cout<<"No carry operation."<<endl;
		else if(cnt==1) cout<<"1 carry operation."<<endl;
		else cout<<cnt<<" carry operations."<<endl;
	}
	return 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
    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
    #include <iostream>
    using namespace std;

    int main()
    {
        string n1, n2;
        while(cin>>n1>>n2)
        {
            if(n1=="0" && n2=="0")
                break;
            int l1 = n1.length()-1;
            int l2 = n2.length()-1;

            int c=0;
            int c_cnt = 0;
    		// 數字1和數字2都有的位數
            for(; l1>=0&&l2>=0; l1--,l2--)
            {
                if((n1[l1]-(int)'0'+n2[l2]-(int)'0'+c)>=10)
                {
                    c=1;
                    c_cnt+=1;
                }
                else
                    c=0;
            }
    		//剩餘位數
            if(l1>=0 || l2>=0)
            {
                string longn;
                int start;

                if(l1>=0)
                {
                    longn = n1;
                    start = l1;

                }
                if(l2>=0)
                {
                    longn = n2;
                    start = l2;
                }
                for(int i=start; i>=0; i--)
                {
                    if((longn[i]-(int)'0'+c)>=10)
                    {
                        c=1;
                        c_cnt+=1;
                    }
                    else
                        c=0;
                }
            }

            if(c_cnt==0)
                cout<<"No carry operation."<<endl;
            else if(c_cnt==1)
                cout<<"1 carry operation."<<endl;
            else
                cout<<c_cnt<<" carry operations."<<endl;
        }

    }

4. uva #100

  • 題目連結

  • 題目大意：
    有一演算法如下：

    1. input n
    2. print n
    3. if n = 1 then STOP
    4. if n is odd then n ←− 3n + 1
    5. else n ←− n/2
    6. GOTO 2

    且某數n的”cycle length”定義為，n經此演算法最終收斂為1，需要經幾次改變。
    給兩數i、 j，求i、j閉區間內(包含i、j)所有數的cycle length最大者。

    • 注意：此題提供的i、 j，不一定i<=j！！

  • 核心思路：
    區間的數一一套入演算法，計算各數cycle length。
    求最大cycle length：計算完某數cycle length，與當前最大cycle length比較，若大於當前最大cycle length，將最大cycle length更新為某數cycle length。

    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
    //22
    #include<iostream>

    using namespace std;

    int main(){
        int i, j;
        while(cin>>i>>j)
        {
            int start, end;

            if(i>j)
            {
               start = j;
               end = i;
            }
            else
            {
                start = i;
                end = j;

            }
            int max_cnt = 0;
            for(int k=start; k<=end; k++)
            {
                int cnt = 0;
                int n=k;

                while(true)
                {
                    cnt++;
                    if(n==1)
                        break;

                    if(n%2==1)
                        n = 3*n+1;
                    else
                        n = n/2;

                }
                if(cnt>max_cnt)
                    max_cnt = cnt;

            }
            cout<<i<<" "<<j<<" "<<max_cnt<<endl;
        }

    }

    5. uva #10929

  • 題目連結

  • 題目大意： 判斷一正整數n是否為11的倍數，當輸入測資為0，表示結束

    • 注意：此題目測資數字很大，用long long 也不能完全讀取。
      (意思就是不能用除以11後餘數是否為0來判斷啦QAQ)

  • 核心思路：

    1. 大數讀取：使用字串讀取
    2. 11倍數特性：{奇數位數字和-偶數位數字和}為11的倍數
      若某數{奇數位數字和-偶數位數字和}為11的倍數，其為11的倍數。

  • 特別注意！！！若題目數字前面有0，輸出時0需印出來; 若有空格則不印，
    讀取字串時用cin>>str;，可避免讀取到空白字元

  • 其他數字倍數規則整理：

    1的倍數：任何數皆為1的倍數。
    2的倍數：個位數字為偶數(含0)。
    3的倍數：各個數字和為3的倍數。
    4的倍數：末二位數為4的倍數(含00)。
    5的倍數：個位數字為5或0。
    6的倍數：各個數字和為6的倍數(同時是2和3的倍數)。
    7的倍數：由個數起每三位數字一節，各奇數節和 與 偶數節和 相減，其差是7的倍數。
    8的倍數：末三位數為8的倍數(含000)。
    9的倍數：各個數字和為9的倍數。
    10的倍數：個位數字為0。
    11的倍數：奇數位數字和與偶數位數字和相差為11的倍數。
    12的倍數：同時是3和4的倍數。
    13的倍數：由個數起每三位數字一節，各奇數節和 與 偶數節和相減，其差是13的倍數。

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
//21
#include<iostream>

using namespace std;

int main()
{
	string s;
	long long int sum;
	while(cin>>s)
	{
		if(s=="0") break; //記得要用s字串來判斷，不要用數字值0，避免'000000000'也會中止 
		sum=0;
		// {奇數位數字和-偶數位數字和} or {奇數位數字和-偶數位數字和}
		for(int i=0; i<s.length(); i++)
		{
			if(i%2==0) sum+=(int)(s[i]-'0');
			else  sum-=(int)(s[i]-'0');
		}
		//判斷是否為11倍數
		if(sum%11==0)
		{
			cout<<s<<" is a multiple of 11."<<endl;
		}
		else
		{
			cout<<s<<" is not a multiple of 11."<<endl;
		}
	}
}

6. uva #10101

此題題目格式是真的很麻煩:) 花了我幾個小時debug:)))

  • 題目連結

  • 題目大意：
    左邊的文字對應右邊的數字：

    kuti： 10000000
    lakh： 100000
    hajar： 1000
    shata： 100

    將題目給的數字用上述對應文字的方式表現出來，如：

    • 45897458973958 印出 45 lakh 89 hajar 7 shata 45 kuti 89 lakh 73 hajar 9 shata 58
    • 00000000000000 印出 0
    • 1000000000 印出 1 shata kuti
    • 000100100 印出 1 lakh 1 shata

  • 注意：此題輸出題號的格式要使用setw(4)！！！(佔四字元寬且靠右)

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
#include<iostream>
#include<iomanip>
#include<vector>

using namespace std;

int main(){

    long long int num;
    string arr[4] = {"lakh", "hajar", "shata", "kuti"};
    int cnt = 0;
    while(cin>>num)
    {
		cnt++;
		//數字為0時，0要單獨印出
		if(num == 0)
		{
			cout << setw(4) << setfill(' ') << cnt << "."<<" 0"<<endl;
		}
		else	//數字不為0的情況
		{
			cout << setw(4) << setfill(' ') << cnt << ".";
			vector<int> v;
			int r[4];
			string rst_str;

			long long int tmp = num;

			int tmp_cnt = -1;	//紀錄又多少個kuti
			while(tmp>0)
			{
				tmp_cnt++;
				
				//kuti
				v.push_back(tmp%100);
				tmp /= 100;
				
				//shata
				v.push_back(tmp%10);
				tmp /= 10;
				
				//hajar
				v.push_back(tmp%100);
				tmp /= 100;
				
				//lakh
				v.push_back(tmp%100);
				tmp /= 100;

			}

			for(int i=v.size()-1; i>=0; i--)
			{

				if(v[i]!=0)
				{
					cout<<" "<<v[i];

					if(i%4==0 && i!=0)
						cout<<" kuti";
					else if(i%4==1)
						cout<<" shata";
					else if(i%4==2)
						cout<<" hajar";
					else if(i%4==3)
						cout<<" lakh";

				}
				else if(i%4==0 && i!=0)
					cout<<" kuti";

			}
        	cout<<endl;
		}
    }

}

7. uva #10240

  • 題目連結

  • 題目大意：
    一個測資有多行，每行含一個 國家名 與 該國家的一個人名，要求統計出 此測資中各國家出現的次數。

    • 注意：
      此題國家名必為1個字串，名字可能有多個字串組成(雖然測資好像都是兩個字串組成)。
      此題也沒有重複的人名，可以放心。

  • 核心思路：用map去對應國家名與其出現次數。

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
//8 map
#include <iostream>
#include <map>

using namespace std;

int main(){
    int n;
    map<string, int> m;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        string country;
        string name;

		//讀城市
        cin>>country;
        
		//讀名字
		getline(cin, name);

        m[country]++;
    }
    map<string, int>::iterator it;
    for(it=m.begin(); it!=m.end(); it++)
    {
        cout<<it->first<<" "<<it->second<<endl;
    }
    m.clear();
}

8. uva #10008

  • 題目連結

  • 題目大意：
    給一數字n，代表此測資接下來會有n行字串。請統計這n行字串中，每個英文字母分別出現幾次，並依**出現次數降序(若出現次數相同，依字母順序排)**印出。

    • 注意：
    1. 英文字母不區分大小寫(大小寫視為同一字母)
    2. 不須去計算非英文字母的字元出現次數
    3. 印出答案時，只印出出現次數>=1的英文字母

  • 核心思路：

    1. 不區分大小寫(也可用toupper函式判別)
    2. 統計：建立一個struct統計出現次數(大小為26)
    3. 降序排列：用sort()函式，並將排列規則cmp()設為 出現次數降序，若出現次數相同，依字母順序排
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
//49
//#include <cctype>	用toupper()
#include <iostream>
#include <algorithm>   //sort()
#include<vector>

using namespace std;

struct alphebet{
    char alp;   //字母
    int times;  //出現幾次
};

//比較規則
bool cmp(alphebet x, alphebet y)
{
    if(x.times>y.times)
        return true;
    else if(x.times == y.times && (int)(x.alp)<(int)(y.alp))
        return true;

    return false;
}

int main(){
    int n;
    string s;
    while(cin>>n)
    {
        //  讀一行
        getline(cin, s);

        //  初始化
        alphebet a[26];
        for(int i=0; i<26; i++)
        {
            a[i].alp = (char)((int)'A'+i);
            a[i].times = 0;
        }

        //  統計出現次數
        for(int i=0; i<n; i++)
        {
            getline(cin, s);
            for(int j=0; j<s.length(); j++)
            {
                if(s[j]-'A'>=0 && s[j]-'A'<26) //大寫
                    a[s[j] - 'A'].times++;
                else if(s[j]-'a'>=0 && s[j]-'a'<26) //小寫
                    a[s[j] - 'a'].times++;
            }
        }
        //  排序
        sort(a, a+26, cmp);
        //  印
        for(int i=0; i<26; i++)
        {
            if(a[i].times<1)
                break;
            cout<<a[i].alp<<" "<<a[i].times<<endl;
        }

    }
}

9. uva #10222

  • 題目連結
  • 題目大意：
    解碼一段文字(中間可能含空白)。
    解碼原則：密文字母在鍵盤上的按鍵位置左數兩個按鍵，該按鍵上的字母即是明文。
    • 注意: 此題須decode英文字母部分，空白字元維持原本
  • 核心思路：
    1. 使用字串存鍵盤上的文字
    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
//20

#include <iostream>

using namespace std;

int main(){
    string keyboard = " `1234567890-=qwertyuiop[]asdfghjkl;'zxcvbnm,./";
    string line;
    while(getline(cin, line))
    {
        for(int i=0; i<line.length(); i++)
        {
            //轉小寫
            if(line[i]>='A' && line[i]<='Z')
                line[i] = line[i]-'A'+'a';

            if(line[i] == keyboard[0])
            {
                cout<<" ";
            }
            else
            {
                for(int j=0; j<keyboard.length(); j++)
                {
                    if(line[i] == keyboard[j])
                    {
                        cout<<keyboard[j-2];
                    }

                }
            }

        }
        cout<<endl;
    }

}

10. uva #11332

  • 題目連結

  • 題目大意：
    若 n = 1234567892， 則函數f(n)定義為：

    f(n) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 2 = 47
    則
    f(f(n)) = 4 + 7 = 11
    f(f(f(n))) = 1 + 1 = 2

    如上述連續套用f(n)最終會得到一個位數字，此個位數定義為g(n)。
    求g(n)。

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
//8
#include <iostream>

using namespace std;

int main()
{
    int n;
    while(cin>>n)
    {
        if(n==0)
            break;

        //計算直至f(n)為個位數(<=10)
        while(n>=10)
        {
            int tmp = n;
            int sum=0;
            while(tmp>0)
            {
                sum += tmp%10;  //計算f(n)
                tmp/=10;
            }
            //下次的輸入
            n=sum;

        }
        cout<<n<<endl;
    }

}

關於

本系列為個人刷題的紀錄，做為記錄與將來複習用，所以有些題目註解簡略。
若恰好對你有幫助，我也很開心:)

希望看到這篇的你們和我都能在cpe取得好成績^^