解題區/解題區 - 其他題目

程序设计实习 MOOC Week 9 DEX

contents

  1. 1. 接續上一篇
  2. 2. D - 热血格斗场
    1. 2.1. 題目
    2. 2.2. 解法
  3. 3. E - priority queue练习题
    1. 3.1. 題目
    2. 3.2. 解法
  4. 4. X - 思考题最后一题，不计分，供测试
    1. 4.1. 題目
    2. 4.2. 解法

接續上一篇

D - 热血格斗场

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

为了迎接08年的奥运会，让大家更加了解各种格斗运动，facer新开了一家热血格斗场。格斗场实行会员制，但是新来的会员不需要交入会费，而只要同一名老会员打一场表演赛，证明自己的实力。

我们假设格斗的实力可以用一个正整数表示，成为实力值。另外，每个人都有一个唯一的id，也是一个正整数。为了使得比赛更好看，每一个新队员都会选择与他实力最为接近的人比赛，即比赛双方的实力值之差的绝对值越小越好，如果有两个人的实力值与他差别相同，则他会选择比他弱的那个（显然，虐人必被虐好）。

不幸的是，Facer一不小心把比赛记录弄丢了，但是他还保留着会员的注册记录。现在请你帮facer恢复比赛纪录，按照时间顺序依次输出每场比赛双方的id。

输入

第一行一个数n(0 < n <=100000)，表示格斗场新来的会员数（不包括facer）。以后n行每一行两个数，按照入会的时间给出会员的id和实力值。一开始，facer就算是会员，id为1，实力值1000000000。输入保证两人的实力值不同。

输出

N行，每行两个数，为每场比赛双方的id，新手的id写在前面。

样例输入

3
2 1
3 3
4 2

样例输出

2 1
3 2
4 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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
int main() {
#define oo 0x3f3f3f3f
    for(int n, id, power; scanf("%d", &n) == 1;) {
        set< pair<int, int> > S;
        S.insert(make_pair(1000000000, 1));
        for(int i = 0; i < n; i++)	 {
            scanf("%d %d", &id, &power);
            S.insert(make_pair(power, id));
            set< pair<int, int> >::iterator it;
            it = S.find(make_pair(power, id));
            pair<int, int> f1, f2;
            f1 = make_pair(-oo, 0);
            f2 = make_pair(oo, 0);
            if(it != S.begin()) {
                it--;
                f1 = *it;
                it++;
            }
            if(it != S.end()) {
                it++;
                f2 = *it;
                it--;
            }
            if(abs(f2.first - power) < abs(f1.first - power))
                f1 = f2;
            printf("%d %d\n", id, f1.second);
        }
    }	
    return 0;
}

E - priority queue练习题

題目

总时间限制: 2500ms 内存限制: 131072kB

描述

我们定义一个正整数a比正整数b优先的含义是：
*a的质因数数目（不包括自身）比b的质因数数目多；
*当两者质因数数目相等时，数值较大者优先级高。

现在给定一个容器，初始元素数目为0，之后每次往里面添加10个元素，每次添加之后，要求输出优先级最高与最低的元素，并把该两元素从容器中删除。

输入

第一行: num (添加元素次数，num <= 30)

下面10*num行，每行一个正整数n（n < 10000000).

输出

每次输入10个整数后，输出容器中优先级最高与最低的元素，两者用空格间隔。

样例输入

1
10 7 66 4 5 30 91 100 8 9

样例输出

66 5

解法

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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <set>
using namespace std;
int getPF(int n) {
    int ret = 0;
    for(int i = 2; i*i <= n; i++) {
        if(n%i == 0) {
            while(n /= i, n%i == 0);
            ret++;
        }
    }
    if(n != 1 && ret > 0)	ret++;
    return ret;
}
int main() {
    for(int n; scanf("%d", &n) == 1;) {
        multiset< pair<int, int> > S;
        while(n--) {
            for(int i = 0, x; i < 10; i++) {
                scanf("%d", &x);
                S.insert(make_pair(getPF(x), x));
            }			
            multiset< pair<int, int> >::iterator it;
            multiset< pair<int, int> >::iterator jt;
            it = S.begin();
            jt = S.end();
            jt--;
            printf("%d %d\n", (*jt).second, (*it).second);
            S.erase(it);
            S.erase(jt);
        }
    }
    return 0;
}

X - 思考题最后一题，不计分，供测试

題目

总时间限制: 1000ms 内存限制: 65536kB

描述

请补齐下面程序，使得补齐后的程序，对于下面指定的输入数据，能产生指定的输出。

1
2
3
4
5
6
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{

// 在此处补充你的代码

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
};
int main()  
{ 
     
     int t;
     cin >> t;
     while (t--) {
     	 CMyistream_iterator<int> inputInt(cin);
         int n1,n2,n3;
         n1 = * inputInt;
         int tmp = * inputInt; 
         cout << tmp << endl;
         inputInt ++;   
         n2 = * inputInt; 
         inputInt ++;   
         n3 = * inputInt; 
         cout << n1 << "," << n2<< "," << n3 << ",";
         CMyistream_iterator<string> inputStr(cin);
         string s1,s2;
         s1 = * inputStr; 
         inputStr ++;     
         s2 = * inputStr; 
         cout << s1 << "," << s2 << endl;
    }
    return 0;  
}

输入

第一行是整数t,表示有t组数据。
每组数据由三个整数和两个字符串组成。整数都是小于220的正整数，字符串中间没有空格

输出

对每组输入数据，输出两行。
第一行是输入的第一个整数。
第二行依次输出输入的各项，用逗号","分隔。

样例输入

2
79 90 20 hello me
21 375 45 Jack good

样例输出

79
79,90,20,hello,me
21
21,375,45,Jack,good

解法

這裡要特別小心串流處理，這裡仍是用指針去維護。

Pointer Type(*) 和 Reference Type(&) 使用上也要明白差別。

  • 假使宣告 istream &mcin;
    一定要用 CMyistream_iterator(istream& m): mcin(m) 搭配 mcin >> front

    • 為什麼 mcin = m 不能取代 mcin(m) ?
      雖然我不太明白，但是 Reference Type 一定要在宣告的時候就決定取的位址，也就是說 mcin 再也不能跟動對應的位址，與指標不同的地方就在這裡。

      通常會這個寫來降低複雜度 int& ret = MAP[index]; 其中 ret 再也不能更動位址，當然也許再 C++11 之後的版本會有所不同。

  • 假使宣告 istream *mcin;
    彈性就很大，但使用時都要用 *mcin >> front

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
#include <iostream>
#include <string>
using namespace std;
template <class T>
class CMyistream_iterator
{
    public:
        CMyistream_iterator(istream& m): mcin(&m) {
            *mcin >> front;
        }
        void operator ++(int) {
            *mcin >> front;
        }
        T operator * () {
            return front;
        }
    private:
        istream *mcin;
        T front;
};
int main()  
{ 
     
     int t;
     cin >> t;
     while (t--) {
     	 CMyistream_iterator<int> inputInt(cin);
         int n1,n2,n3;
         n1 = * inputInt;
         int tmp = * inputInt; 
         cout << tmp << endl;
         inputInt ++;   
         n2 = * inputInt; 
         inputInt ++;   
         n3 = * inputInt; 
         cout << n1 << "," << n2<< "," << n3 << ",";
         CMyistream_iterator<string> inputStr(cin);
         string s1,s2;
         s1 = * inputStr; 
         inputStr ++;     
         s2 = * inputStr; 
         cout << s1 << "," << s2 << endl;
    }
    return 0;  
}