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

程序设计实习 MOOC Week 9 ABC

contents

  1. 1. 關於這一周
    1. 1.1. 練習項目
      1. 1.1.1. std::list
      2. 1.1.2. std::set & std::multiset
      3. 1.1.3. std::string
  2. 2. A - List
    1. 2.1. 題目
    2. 2.2. 解法
  3. 3. B - Set
    1. 3.1. 題目
    2. 3.2. 解法
  4. 4. C - 字符串操作
    1. 4.1. 題目
    2. 4.2. 解法

關於這一周

練習 STL 的語法。 題目來源

好久沒有練 C++ 程序，這是一個訓練 STL 的題單。

練習項目

std::list

  • list.merge(other_list)
    將 other_list 內容搬運到 list 後，other_list 清空。
  • list.sort()
    不依賴 std::sort, 自己內部有一個 sort()。
  • list.unique()
    跟另外一套的有點相似，一樣是要在排序後才能運行當作去重複。

std::set & std::multiset

  • insert()
  • find()
    查找，後回傳 set<>::iterator 的型態。
  • set<>::iterator
    begin() 和 end() 的型態。
  • set<>::reverse_iterator
    rbegin() 和 rend() 的型態。
  • erase()
    特別小心這個，傳入如果是 iterator 的話，就只會刪除單一元素，如果對於 multiset 來說，傳入一般的值(不是迭代器指針) 則會將所有相同的都刪除。

std::string

  • find(str [, start_pos])
    正向搜索 str 這個字串從 start_pos 開始算起。
  • rfind()
    逆向搜索 str 這個字串。
  • substr(start_post, sub_length)
    從某個位置開始，截出一段長度。

A - List

題目

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

描述

写一个程序完成以下命令：
new id ——新建一个指定编号为id的序列(id<10000)
add id num——向编号为id的序列加入整数num
merge id1 id2——合并序列id1和id2中的数，并将id2清空
unique id——去掉序列id中重复的元素
out id ——从小到大输出编号为id的序列中的元素，以空格隔开

输入

第一行一个数n，表示有多少个命令( n <= 200000)。以后 n 行每行一个命令。

输出

按题目要求输出。

样例输入

16
new 1
new 2
add 1 1
add 1 2
add 1 3
add 2 1
add 2 2
add 2 3
add 2 4
out 1
out 2
merge 1 2
out 1
out 2
unique 1
out 1

样例输出

1 2 3 
1 2 3 4
1 1 2 2 3 3 4

1 2 3 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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <map>
#include <list>
using namespace std;
int main() {
    for(int n; scanf("%d", &n) == 1; )  {
        char cmd[10];
        int id, num, aid;
        map< int, list<int> > S;
        while(n--) {
            scanf("%s", cmd);
            if(cmd[0] == 'n') { // new
                scanf("%d", &id);
                S[id] = list<int>();
            } else if(cmd[0] == 'a') { // add
                scanf("%d %d", &id, &num);
                S[id].push_back(num);
            } else if(cmd[0] == 'm') { // merge
                scanf("%d %d", &id, &aid);
                S[id].merge(S[aid]);
            } else if(cmd[0] == 'u') { // unique
                scanf("%d", &id);
                S[id].sort();
                S[id].unique();
            } else { // out
                scanf("%d", &id);
                S[id].sort();
                list<int>::iterator it, jt;
                it = S[id].begin(), jt = S[id].end();
                int f = 0;
                for(; it != jt; it++) {
                    if(f)	putchar(' ');
                    f = 1;
                    printf("%d", *it);
                }
                puts("");
            }
        }
    }
    return 0;
}

B - Set

題目

总时间限制: 5000ms 内存限制: 100000kB

描述

现有一整数集（允许有重复元素），初始为空。我们定义如下操作：
add x 把x加入集合
del x 把集合中所有与x相等的元素删除
ask x 对集合中元素x的情况询问
对每种操作，我们要求进行如下输出。
add 输出操作后集合中x的个数
del 输出操作前集合中x的个数
ask 先输出0或1表示x是否曾被加入集合（0表示不曾加入），再输出当前集合中x的个数，中间用空格格开。

输入

第一行是一个整数n，表示命令数。0<=n<=100000。
后面n行命令，如Description中所述。

输出

共n行，每行按要求输出。

样例输入

7
add 1
add 1
ask 1
ask 2
del 2
del 1
ask 1

样例输出

1
2
1 2
0 0
0
2
1 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
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
int main() {
    for(int n, x; scanf("%d", &n) == 1;) {
        char cmd[10];
        multiset<int> S;
        set<int> I;
        while(n--) {
            scanf("%s", cmd);
            if(cmd[0] == 'a' && cmd[1] == 'd') { // add
                scanf("%d", &x);
                I.insert(x);
                S.insert(x);
                printf("%d\n", S.count(x));
            } else if(cmd[0] == 'a' && cmd[1] == 's') { // ask
                scanf("%d", &x);
                printf("%d %d\n", I.find(x) != I.end(), S.count(x));
            } else { // del
                scanf("%d", &x);
                printf("%d\n", S.count(x));
                S.erase(x);
            }
        }
    }
    return 0;
}

C - 字符串操作

題目

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

描述

给定n个字符串（从1开始编号），每个字符串中的字符位置从0开始编号，长度为1-500，现有如下若干操作：

    copy N X L：取出第N个字符串第X个字符开始的长度为L的字符串。
    add S1 S2：判断S1，S2是否为0-99999之间的整数，若是则将其转化为整数做加法，若不是，则作字符串加法，返回的值为一字符串。
    find S N：在第N个字符串中从左开始找寻S字符串，返回其第一次出现的位置，若没有找到，返回字符串的长度。
    rfind S N：在第N个字符串中从右开始找寻S字符串，返回其第一次出现的位置，若没有找到，返回字符串的长度。
    insert S N X：在第N个字符串的第X个字符位置中插入S字符串。
    reset S N：将第N个字符串变为S。
    print N：打印输出第N个字符串。
    printall：打印输出所有字符串。
    over：结束操作。

其中N，X，L可由find与rfind操作表达式构成，S，S1，S2可由copy与add操作表达式构成。

输入

第一行为一个整数n（n在1-20之间）

接下来n行为n个字符串，字符串不包含空格及操作命令等。

接下来若干行为一系列操作，直到over结束。

输出

根据操作提示输出对应字符串。

样例输入

3
329strjvc
Opadfk48
Ifjoqwoqejr
insert copy 1 find 2 1 2 2 2
print 2
reset add copy 1 find 3 1 3 copy 2 find 2 2 2 3
print 3
insert a 3 2
printall
over

样例输出

Op29adfk48
358
329strjvc
Op29adfk48
35a8

解法

這一題算是裡面最繁瑣的一題，一部分是因為其輸入的規則需要遞歸分析。
而為了實現遞歸分析，需要可以偷看輸入的下一個 token，因此先把每一個 token 切出來放在 queue 裏頭。

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
// http://cxsjsxmooc.openjudge.cn/
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <sstream>
#include <queue>
#include <ctype.h>
using namespace std;
char s[32][512], lineStr[1024];
string str[32];
int strSize;
queue<string> tokenQ;
int str2num(string s) {
    return atoi(s.c_str());
}
string num2str(int n) {
  	string s;
  	stringstream ss(s);
  	ss << n;
    return ss.str();
}
int isValidNum(string s) {
    int ret = 0;
    for(int i = 0; i < s.length(); i++) {
        if(!isdigit(s[i]))
            return -1;
        ret = ret * 10 + s[i] - '0';
        if(ret > 99999)
            return -1;
    }
    return ret;
}
string parsing() {
    string p = tokenQ.front();
    tokenQ.pop();
    if(p == "copy")  {
        string N, X, L;
        int n, x, l;
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            X = parsing();
        } else {
            X = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            L = parsing();
        } else {
            L = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N), x = str2num(X), l = str2num(L);
        
        return str[n].substr(x, l);
    } else if(p == "add") {
        string S1, S2;
        int s1, s2;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S1 = parsing();
        } else {
            S1 = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S2 = parsing();
        } else {
            S2 = tokenQ.front(), tokenQ.pop();
        }
        s1 = isValidNum(S1), s2 = isValidNum(S2);
        if(s1 < 0 || s2 < 0)
            return S1 + S2;
        else
            return num2str(s1 + s2);
    } else if(p == "find") {
        string S, N;
        int s, n;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        int pos = str[n].find(S);
        
        if(pos != string::npos) {
            return num2str(pos);
        } else {
            return num2str(str[n].length());
        }
    } else if(p == "rfind") {
        string S, N;
        int s, n;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        int pos = str[n].rfind(S);
        if(pos != string::npos) {
            return num2str(pos);
        } else {
            return num2str(str[n].length());
        }
    } else if(p == "insert") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            X = parsing();
        } else {
            X = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N), x = str2num(X);
        str[n].insert(x, S);
    } else if(p == "reset") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "copy" || tokenQ.front() == "add") {
            S = parsing();
        } else {
            S = tokenQ.front(), tokenQ.pop();
        }
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        str[n] = S;
    } else if(p == "print") {
        string S, N, X;
        int s, n, x;
        if(tokenQ.front() == "find" || tokenQ.front() == "rfind") {
            N = parsing();
        } else {
            N = tokenQ.front(), tokenQ.pop();
        }
        n = str2num(N);
        printf("%s\n", str[n].c_str());
    } else if(p == "printall") {
        for(int i = 1; i <= strSize; i++)
            printf("%s\n", str[i].c_str());
    } else if(p == "over") {
        
    }
    return "";
}
int main() {
    for(int n; scanf("%d", &n) == 1;) {
        int N, X, L, S1, S2, S;
        for(int i = 1; i <= n; i++) {
            scanf("%s", s[i]);
            str[i] = s[i];
        }
        strSize = n;
        while(getchar() != '\n');
        while(gets(lineStr)) {
            stringstream sin(lineStr);
            string token;
            while(sin >> token)
                tokenQ.push(token);
            parsing();
        }
    }
    return 0;
}