Skip to content

CSP-J 2021 题解

题解约 4.3 千字
检测到 KaTeX 加载失败,可能会导致文中的数学公式无法正常渲染。

本文篇幅较长,可以通过页面右下角的目录功能快速跳转。

#分糖果

#题面

#题目背景

红太阳幼儿园的小朋友们开始分糖果啦!

#题目描述

红太阳幼儿园有 nn 个小朋友,你是其中之一。保证 n2n \leq 2

有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们。

由于你只是个平平无奇的幼儿园小朋友,所以你的体力有限,至多只能拿 RR 块糖回去。

但是拿的太少不够分的,所以你至少要拿 LL 块糖回去。保证 nLRn \leq L \leq R

也就是说,如果你拿了 k 块糖,那么你需要保证 LkRL \leq k \leq R

如果你拿了 k 块糖,你将把这 k 块糖放到篮子里,并要求大家按照如下方案分糖果:只要篮子里有不少于 nn 块糖果,幼儿园的所有 nn 个小朋友(包括你自己)都从篮子中拿走恰好一块糖,直到篮子里的糖数量少于 nn 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励

作为幼儿园高质量小朋友,你希望让作为你搬糖果的奖励的糖果数量(而不是你最后获得的总糖果数量!)尽可能多;因此你需要写一个程序,依次输入 n,L,Rn, L, R ,并输出出你最多能获得多少作为你搬糖果的奖励的糖果数量。

#输入格式

输入一行,包含三个正整数 n,L,Rn, L, R,分别表示小朋友的个数、糖果数量的下界和上界。

#输出格式

输出一行一个整数,表示你最多能获得的作为你搬糖果的奖励的糖果数量。

#输入输出样例

样例输入 #1

7 16 23

样例输出 #1

6

样例解释 #1

k=20k = 20 块糖放入篮子里。

篮子里现在糖果数 20n=720 \ge n = 7,因此所有小朋友获得一块糖;

篮子里现在糖果数变成 13n=713 \ge n = 7,因此所有小朋友获得一块糖;

篮子里现在糖果数变成 6<n=76 < n = 7,因此这 66 块糖是作为你搬糖果的奖励

容易发现,你获得的作为你搬糖果的奖励的糖果数量不可能超过 66 块(不然,篮子里的糖果数量最后仍然不少于 nn,需要继续每个小朋友拿一块),因此答案是 66

样例输入 #2

10 14 18

样例输出 #2

8

样例解释 #2

容易发现,当你拿的糖数量 kk 满足 14=LkR=1814 = L \le k \le R = 18 时,所有小朋友获得一块糖后,剩下的 k10k - 10 块糖总是作为你搬糖果的奖励的糖果数量,因此拿 k=18k = 18 块是最优解,答案是 88

#数据范围与约定

测试点 nn \le RR \le RLR - L \le
11 22 55
22 55 1010
33 103{10}^3
44 105{10}^5
55 103{10}^3 109{10}^9 00
66 103{10}^3
77 105{10}^5 105{10}^5
88 109{10}^9 109{10}^9
99
1010

对于所有数据,保证 2nLR1092 \le n \le L \le R \le {10}^9

#思路

此题是一道结论题。

#代码

C++
1
2
3
4
5
6
7
8
9
10
11
#include <bits/stdc++.h>

using namespace std;

int n, l, r, ans;

int main() {
cin >> n >> l >> r;
cout << min((int)(ceil(1.0 * l / n) * n + n - 1), r) % n << endl;
return 0;
}

#网络连接

#题面

#题目描述

TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。

在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机负责加入连接。

需要进行网络连接的计算机共有 nn 台,编号为 1n1 \sim n,这些机器将按编号递增的顺序,依次发起一条建立连接或加入连接的操作。

每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址,客户机提供的地址串表示它尝试加入连接的地址。

一个符合规范的地址串应当具有以下特征:

  1. 必须形如 a.b.c.d:e 的格式,其中 a,b,c,d,ea, b, c, d, e 均为非负整数;
  2. 0a,b,c,d2550 \le a, b, c, d \le 2550e655350 \le e \le 65535
  3. a,b,c,d,ea, b, c, d, e 均不能含有多余的前导 00

相应地,不符合规范的地址串可能具有以下特征:

  1. 不是形如 a.b.c.d:e 格式的字符串,例如含有多于 33 个字符 . 或多于 11 个字符 : 等情况;
  2. 整数 a,b,c,d,ea, b, c, d, e 中某一个或多个超出上述范围;
  3. 整数 a,b,c,d,ea, b, c, d, e 中某一个或多个含有多余的前导 00

例如,地址串 192.168.0.255:80 是符合规范的,但 192.168.0.999:80192.168.00.1:10192.168.0.1:088192:168:0:1.233 均是不符合规范的。

如果服务机或客户机在发起操作时提供的地址串不符合规范,这条操作将被直接忽略。

在本问题中,我们假定凡是符合上述规范的地址串均可参与正常的连接,你无需考虑每个地址串的实际意义。

由于网络阻塞等原因,不允许两台服务机使用相同的地址串,如果此类现象发生,后一台尝试建立连接的服务机将会无法成功建立连接;除此之外,凡是提供符合规范的地址串的服务机均可成功建立连接。

如果某台提供符合规范的地址的客户机在尝试加入连接时,与先前某台已经成功建立连接的服务机提供的地址串相同,这台客户机就可以成功加入连接,并称其连接到这台服务机;如果找不到这样的服务机,则认为这台客户机无法成功加入连接。

请注意,尽管不允许两台不同的服务机使用相同的地址串,但多台客户机使用同样的地址串,以及同一台服务机同时被多台客户机连接的情况是被允许的。

你的任务很简单:在给出每台计算机的类型以及地址串之后,判断这台计算机的连接情况。

#输入格式

第一行,一个正整数 nn

接下来 nn 行,每行两个字符串 op,ad\mathit{op}, \mathit{ad},按照编号从小到大给出每台计算机的类型及地址串。

其中 op\mathit{op} 保证为字符串 ServerClient 之一,ad\mathit{ad} 为一个长度不超过 2525 的,仅由数字、字符 . 和字符 : 组成的非空字符串。

每行的两个字符串之间用恰好一个空格分隔开,每行的末尾没有多余的空格。

#输出格式

输出共 nn 行,每行一个正整数或字符串表示第 ii 台计算机的连接状态。其中:

如果第 ii 台计算机为服务机,则:

  1. 如果其提供符合规范的地址串且成功建立连接,输出字符串 OK
  2. 如果其提供符合规范的地址串,但由于先前有相同地址串的服务机而无法成功建立连接,输出字符串 FAIL
  3. 如果其提供的地址串不是符合规范的地址串,输出字符串 ERR

如果第 ii 台计算机为客户机,则:

  1. 如果其提供符合规范的地址串且成功加入连接,输出一个正整数表示这台客户机连接到的服务机的编号。
  2. 如果其提供符合规范的地址串,但无法成功加入连接时,输出字符串 FAIL
  3. 如果其提供的地址串不是符合规范的地址串,输出字符串 ERR

#输入输出样例

样例输入 #1

5
Server 192.168.1.1:8080
Server 192.168.1.1:8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.1:99999

样例输出 #1

OK
FAIL
1
FAIL
ERR

样例解释 #1

计算机 11 为服务机,提供符合规范的地址串 192.168.1.1:8080,成功建立连接;
计算机 22 为服务机,提供与计算机 11 相同的地址串,未能成功建立连接;
计算机 33 为客户机,提供符合规范的地址串 192.168.1.1:8080,成功加入连接,并连接到服务机 11
计算机 44 为客户机,提供符合规范的地址串 192.168.1.1:80,找不到服务机与其连接;
计算机 55 为客户机,提供的地址串 192.168.1.1:99999 不符合规范。

样例输入 #2

10
Server 192.168.1.1:80
Client 192.168.1.1:80
Client 192.168.1.1:8080
Server 192.168.1.1:80
Server 192.168.1.1:8080
Server 192.168.1.999:0
Client 192.168.1.1.8080
Client 192.168.1.1:8080
Client 192.168.1.1:80
Client 192.168.1.999:0

样例输出 #2

OK
1
FAIL
FAIL
OK
ERR
ERR
5
1
ERR

#数据范围与约定

测试点编号 nn \le 特殊性质
11 1010 性质 1 2 3
232 \sim 3 100100
454 \sim 5 10001000
686 \sim 8 性质 1 2
9119 \sim 11 性质 1
121312 \sim 13 性质 2
141514 \sim 15 性质 4
161716 \sim 17 性质 5
182018 \sim 20 无特殊性质

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

对于 100%100 \% 的数据,保证 1n10001 \le n \le 1000

#思路

细节稍多的模拟题。

先按照题意检查读入的地址串是否合法,如果合法则继续操作,使用 map 记录即可。

#代码

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

using namespace std;

int n;
string op, ad;
map<string, int> server;

bool check(string s) {
int cnt1 = 0, cnt2 = 0, flag = 0;
long long now = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '.') {
cnt1++; // 统计到了一个 `.`
if (cnt2) return 0; // `:` 在 `.` 之前出现不合法
if (i == 0 || s[i - 1] == '.') return false; // `.` 在开头出现或者有两个连续的 `.`
if (cnt1 > 3) return false; // 三个以上的 `.` 不合法
if (now < 0 || now > 255) return false; // 不合法的数字
flag = 0; // 清零
now = 0;
continue;
}
if (s[i] == ':') {
cnt2++; // 统计到了一个 `:`
if (i == s.size() - 1) return false; // 在字符串最后不合法
if (cnt2 > 1) return false; // 多个 `:` 不合法
if (i == 0 || s[i - 1] == ':') return false; // `:` 在开头出现或者有两个连续的 `:`
if (now < 0 || now > 255) return false; // 不合法的数字
flag = 0; // 清零
now = 0;
continue;
}
if (s[i] < '0' || s[i] > '9') return false; // 不合法的字符
if (s[i] == '0' && flag == 0) flag = 1; // 查到第一个前导零时返回
if (s[i] != '0' && flag == 1) return false; // 重复的前导零
if (s[i] != '0') flag = 2;
now = now * 10 + s[i] - '0';
}
if (cnt1 != 3 || cnt2 != 1) return false;
if (now < 0 || now > 65535) return false; // 不合法的端口号
return true;
}

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> op >> ad;
if (check(ad)) {
if (op == "Server") {
if (server.count(ad)) {
cout << "FAIL" << endl;
} else {
server[ad] = i;
cout << "OK" << endl;
}
} else {
if (server.count(ad)) {
cout << server[ad] << endl;
} else {
cout << "FAIL" << endl;
}
}
} else {
cout << "ERR" << endl;
}
}
return 0;
}

#小熊的果篮

#题面

#题目描述

小熊的水果店里摆放着一排 nn 个水果。每个水果只可能是苹果或桔子,从左到右依次用正整数 1,2,,n1, 2, \ldots, n 编号。连续排在一起的同一种水果称为一个“块”。小熊要把这一排水果挑到若干个果篮里,具体方法是:每次都把每一个“块”中最左边的水果同时挑出,组成一个果篮。重复这一操作,直至水果用完。注意,每次挑完一个果篮后,“块”可能会发生变化。比如两个苹果“块”之间的唯一桔子被挑走后,两个苹果“块”就变成了一个“块”。请帮小熊计算每个果篮里包含的水果。

#输入格式

第一行,包含一个正整数 nn,表示水果的数量。

第二行,包含 nn 个空格分隔的整数,其中第 ii 个数表示编号为 ii 的水果的种类,11 代表苹果,00 代表桔子。

#输出格式

输出若干行。

ii 行表示第 ii 次挑出的水果组成的果篮。从小到大排序输出该果篮中所有水果的编号,每两个编号之间用一个空格分隔。

#输入输出样例

样例输入 #1

12
1 1 0 0 1 1 1 0 1 1 0 0

样例输出 #1

1 3 5 8 9 11
2 4 6 12
7
10

样例解释 #1

所有水果一开始的情况是 [1,1,0,0,1,1,1,0,1,1,0,0][1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0],一共有 66 个块。

在第一次挑水果组成果篮的过程中,编号为 1,3,5,8,9,111, 3, 5, 8, 9, 11 的水果被挑了出来。

之后剩下的水果是 [1,0,1,1,1,0][1, 0, 1, 1, 1, 0],一共 44 个块。

在第二次挑水果组成果篮的过程中,编号为 2,4,6,122, 4, 6, 12 的水果被挑了出来。

之后剩下的水果是 [1,1][1, 1],只有 11 个块。

在第三次挑水果组成果篮的过程中,编号为 77 的水果被挑了出来。

最后剩下的水果是 [1][1],只有 11 个块。

在第四次挑水果组成果篮的过程中,编号为 1010 的水果被挑了出来。

样例输入 #2

20
1 1 1 1 0 0 0 1 1 1 0 0 1 0 1 1 0 0 0 0

样例输出 #2

1 5 8 11 13 14 15 17
2 6 9 12 16 18
3 7 10 19
4 20

#数据范围与约定

对于 10%10 \% 的数据,n5n \le 5
对于 30%30 \% 的数据,n1000n \le 1000
对于 70%70 \% 的数据,n50000n \le 50000
对于 100%100 \% 的数据,1n2×1051 \le n \le 2 \times {10}^5

提示:由于数据规模较大,建议 C/C++ 选手使用 scanfprintf 语句输入、输出。

#思路

分块储存,使用队列维护并进行模拟。

在队列中相邻两块可以合并成一块进行处理。

#代码

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

using namespace std;

struct node {
int start, end;
bool value;

node()
: start(-1), end(-1), value(false) {}
node(int _start, int _end, bool _value)
: start(_start), end(_end), value(_value) {}
};

int n, cnt;
bool a[200005], used[200005];
queue<node> q, q2;

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
a[n + 1] = !a[n];
for (int i = 2, t = 1; i <= n + 1; i++) {
if (a[i] != a[i - 1]) {
q.push(node(t, i - 1, a[i - 1]));
t = i;
}
}
cnt = n;
while (cnt) {
while (!q.empty()) {
auto t = q.front();
q.pop();
while (used[t.start] && t.start <= t.end) t.start++;
if (t.start > t.end) continue;
cout << t.start << ' ';
cnt--;
used[t.start] = true;
if (t.start == t.end) continue;
t.start++;
q2.push(t);
}
while (!q2.empty()) {
auto t = q2.front();
q2.pop();
while (!q2.empty()) {
auto x = q2.front();
if (x.value == t.value) {
t.end = x.end;
q2.pop();
} else {
break;
}
}
q.push(t);
}
cout << endl;
}
return 0;
}