中石大第41次CSP培训模拟1题解

作业链接：https://www.luogu.com.cn/contest/314086

邀请码：微信群通知

难度：普及-

赛时答疑与赛后题解：线下答疑

A. [NOIP 2007 提高组]统计数字

[NOIP 2007 提高组]统计数字

方法一：排序计数

思路

排序与计数。将输入的所有数字进行排序，相同的数字会自然排列在一起。遍历排序后的数组，记录当前数字和出现次数。如果遇到不同的数字，则输出前一个数字及其出现次数，并重置计数器。存在一次排序，时间复杂度O(nlogn)。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n, a[N], pre, cnt;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i];

    sort(a, a + n);

    pre = a[0];
    cnt = 1;
    for(int i = 1; i < n; i ++) {
        if(a[i] == pre) {
            cnt ++;
        } else {
            cout << pre << " " << cnt << endl;
            pre = a[i];
            cnt = 1;
        }
    }
    cout << pre << " " << cnt << endl;
    return 0;
}

方法二：map

思路

计算每个数出现的次数。刚好map可以实现，且它基于红黑树，是有序的。时间复杂度O(nlogn)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>

using namespace std;

int n, a;

map<int, int> mp;

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> a;
        mp[a] ++;
    }
    for(auto item: mp)
        cout << item.first << " " << item.second << endl;
    return 0;
}

B. [NOIP 2010 提高组]机器翻译

[NOIP 2010 提高组]机器翻译

方法一：暴力模拟

思路

使用一个数组模拟内存。每次查找新单词是否在数组中，如果不在且内存已满，则将数组元素整体前移（覆盖最早进入的单词），将新单词放在数组最末尾（或最开头），以此来模拟先进先出的过程。时间复杂度O(n × m)。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int M = 105;

int n, m, ans;
int memory[M];

int main() {
    memset(memory, -1, sizeof(memory));
    cin >> m >> n;
    for(int i = 0; i < n; i ++) {
        int t;
        cin >> t;
        bool flag = false;
        for(int j = 0; j < m; j ++) {
            if(memory[j] == t) {
                flag = true;
                break;
            }
        }
        if(!flag) {
            for(int j = m - 1; j > 0; j --)
                memory[j] = memory[j - 1];
            memory[0] = t;
            ans ++;
        }
    }
    cout << ans << endl;
    return 0;
}

方法二：队列（推荐）

思路

使用 STL 中的 queue 来完美模拟内存的先进先出（FIFO）特性。同时搭配一个布尔数组 f 来快速判断单词是否在内存中（类似哈希表的思想），大大降低了查找的时间复杂度。当队列长度超过内存容量时，将队首元素出队，并在布尔数组中标记为未存入。时间复杂度O(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
#include <iostream>
#include <queue>

using namespace std;

const int MAXN = 1005;

int n, m, t, ans;
bool f[MAXN];
queue<int> q;

int main() {
	cin >> m >> n;
	for(int i = 0; i < n; i ++) {
		cin >> t;
		if(!f[t]) {
			f[t] = true;
			q.push(t);
			ans ++;
			
			if(q.size() > m) {
				f[q.front()] = false;
				q.pop();
			}
		}
	}
	cout << ans << endl;
	return 0;
}

C. [CSP-J 2021]网络连接

[CSP-J 2021]网络连接

【数据范围】

测试点编号n≤特殊性质
110性质 1 2 3
2 ∼ 3100性质 1 2 3
4 ∼ 51000性质 1 2 3
6 ∼ 81000性质 1 2
9 ∼ 111000性质 1
12 ∼ 131000性质 2
14 ∼ 151000性质 4
16 ∼ 171000性质 5
18 ∼ 201000无特殊性质

“性质 1”为：保证所有的地址串均符合规范；
“性质 2”为：保证对于任意两台不同的计算机，如果它们同为服务机或者同为客户机，则它们提供的地址串一定不同；
“性质 3”为：保证任意一台服务机的编号都小于所有的客户机；
“性质 4”为：保证所有的地址串均形如 a.b.c.d:e 的格式，其中 a, b, c, d, e 均为不超过 109 且不含有多余前导 0 的非负整数；
“性质 5”为：保证所有的地址串均形如 a.b.c.d:e 的格式，其中 a, b, c, d, e 均为只含有数字的非空字符串。

对于 100% 的数据，保证 1 ≤ n ≤ 1000。

方法一：25分做法

思路

利用数据性质 1、2、3 保证地址均合法的特点，无需进行格式校验。直接分离 Server 和 Client 逻辑，并在已记录的 Server 中暴力查找匹配项。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n, ServerCnt;
string op[N], ad[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> op[i] >> ad[i];
        if(op[i] == "Server") {
            cout << "OK" << endl;
            ServerCnt ++;
        }
        else {
            bool flag = false;
            for(int j = 0; j < ServerCnt; j ++) {
                if(ad[i] == ad[j]) {
                    cout << j + 1 << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "FAIL" << endl;
        }
    }
    return 0;
}

方法二：40分做法

思路

在 25 分代码基础上，利用性质 1、2 改进查找逻辑。直接遍历当前机器之前的所有记录，判断其是否为地址匹配的 Server 即可。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n;
string op[N], ad[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> op[i] >> ad[i];
        if(op[i] == "Server") {
            cout << "OK" << endl;
        }
        else {
            bool flag = false;
            for(int j = 0; j < i; j ++) {
                if(op[j] == "Server" && ad[j] == ad[i]) {
                    cout << j + 1 << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "FAIL" << endl;
        }
    }
    return 0;
}

方法三：55分做法

思路

在40分代码基础上，保留性质1，增加了对 Server 地址唯一性的校验逻辑。在建立新 Server 前，先遍历已有记录检查是否存在同地址的 Server 以防止重复。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n;
string op[N], ad[N];

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> op[i] >> ad[i];
        if(op[i] == "Server") {
            bool flag = false;
            for(int j = 0; j < i; j ++) {
                if(op[j] == "Server" && ad[j] == ad[i]) {
                    cout << "FAIL" << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "OK" << endl;
        }
        else {
            bool flag = false;
            for(int j = 0; j < i; j ++) {
                if(op[j] == "Server" && ad[j] == ad[i]) {
                    cout << j + 1 << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "FAIL" << endl;
        }
    }
    return 0;
}

方法四：满分做法

思路

在完整匹配逻辑的基础上，加入严格的字符串校验函数以排查 ERR 状态。通过逐字符解析，全面验证前导零、数字越界及符号数量与位置，从而过滤掉所有非法地址。

check函数两种写法

1. 格式化解析与重构校验
1
2
3
4
5
6
7
8
9
10
bool check(string address) {
    long long a, b, c, d, e;        // a.b.c.d:port
    sscanf(address.c_str(), "%lld.%lld.%lld.%lld:%lld", &a, &b, &c, &d, &e);
    if(a < 0 || a > 255 || b < 0 || b > 255 || c < 0 || c > 255 || d < 0 || d > 255 || e < 0 || e > 65535) 
        return false;               // 数字范围不合法
    stringstream ss;
    // 拼接回原始字符串，确保格式完全匹配（比如没有前导零等问题）
    ss << a << "." << b << "." << c << "." << d << ":" << e;
    return ss.str() == address;
}
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
39
40
bool check(string address) {
    long long cur = 0;          // 当前正在解析的数字
    int dot_cnt = 0;            // 点的个数
    int colon_cnt = 0;          // 冒号的个数
    bool has_digit = false;     // 当前段是否已经有了数字

    for(char c : address) {
        if(c >= '0' && c <= '9') {
            // 出现前导零
            if (has_digit && cur == 0) return false; 
            cur = cur * 10 + (c - '0');
            // 数字不能超过65535（端口号的上限）
            if (cur > 65535) return false; 
            has_digit = true;
        }
        else if(c == '.') {
            // 点：前面必须有数字，数字不能超255，且不能出现在冒号之后
            if (!has_digit || cur > 255 || colon_cnt > 0) return false;
            dot_cnt++;
            cur = 0;            // 清空，准备读下一段
            has_digit = false;
        }
        else if(c == ':') {
            // 冒号：前面必须有数字，数字不能超255，且必须恰好已经有3个点，且不能有多个冒号
            if (!has_digit || cur > 255 || dot_cnt != 3 || colon_cnt > 0) return false;
            colon_cnt ++;
            cur = 0;            // 清空，准备读最后的端口号
            has_digit = false;
        }
        else{
            // 出现其他非法字符（比如字母、负号等）
            return false; 
        }
    }
    
    // 字符串遍历完后，必须保证最后一段有数字，且标点符号数量严格匹配，且端口号不超限
    if (!has_digit || dot_cnt != 3 || colon_cnt != 1 || cur > 65535) return false;
    
    return true;
}

完整代码

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
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

int n;
string op[N], ad[N];

bool check(string address) {
    long long cur = 0;          // 当前正在解析的数字
    int dot_cnt = 0;            // 点的个数
    int colon_cnt = 0;          // 冒号的个数
    bool has_digit = false;     // 当前段是否已经有了数字

    for(char c : address) {
        if(c >= '0' && c <= '9') {
            // 出现前导零
            if (has_digit && cur == 0) return false; 
            cur = cur * 10 + (c - '0');
            // 数字不能超过65535（端口号的上限）
            if (cur > 65535) return false; 
            has_digit = true;
        }
        else if(c == '.') {
            // 点：前面必须有数字，数字不能超255，且不能出现在冒号之后
            if (!has_digit || cur > 255 || colon_cnt > 0) return false;
            dot_cnt++;
            cur = 0;            // 清空，准备读下一段
            has_digit = false;
        }
        else if(c == ':') {
            // 冒号：前面必须有数字，数字不能超255，且必须恰好已经有3个点，且不能有多个冒号
            if (!has_digit || cur > 255 || dot_cnt != 3 || colon_cnt > 0) return false;
            colon_cnt ++;
            cur = 0;            // 清空，准备读最后的端口号
            has_digit = false;
        }
        else{
            // 出现其他非法字符（比如字母、负号等）
            return false; 
        }
    }
    
    // 字符串遍历完后，必须保证最后一段有数字，且标点符号数量严格匹配，且端口号不超限
    if (!has_digit || dot_cnt != 3 || colon_cnt != 1 || cur > 65535) return false;
    
    return true;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i ++) {
        cin >> op[i] >> ad[i];
        if(!check(ad[i])) {
            cout << "ERR" << endl;
            continue;
        }
        if(op[i] == "Server") {
            bool flag = false;
            for(int j = 0; j < i; j ++) {
                if(op[j] == "Server" && ad[j] == ad[i]) {
                    cout << "FAIL" << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "OK" << endl;
        }
        else {
            bool flag = false;
            for(int j = 0; j < i; j ++) {
                if(op[j] == "Server" && ad[j] == ad[i]) {
                    cout << j + 1 << endl;
                    flag = true;
                    break;
                }
            }
            if(!flag) cout << "FAIL" << endl;
        }
    }
    return 0;
}
中石大CSP培训 > 202603
#CSP #题解 #算法 #排序 #队列 #模拟 #字符串
中石大第41次CSP培训模拟1题解
https://blog.yanjz.top/CUP-CSP41-test1/
作者
严嘉哲
发布于
2026年3月17日
许可协议