CSP-J 2021 题解 - Baoshuo's OI Blog

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

#分糖果

#题面

#题目背景

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

#题目描述

红太阳幼儿园有 $n$ 个小朋友，你是其中之一。保证 $n \leq 2$ 。

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

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

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

也就是说，如果你拿了 k 块糖，那么你需要保证 $L \leq k \leq R$ 。

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

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

#输入格式

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

#输出格式

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

#输入输出样例

样例输入 #1

7 16 23

样例输出 #1

样例解释 #1

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

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

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

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

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

样例输入 #2

10 14 18

样例输出 #2

样例解释 #2

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

#数据范围与约定

测试点	$n \le$	$R \le$	$R - L \le$
$1$	$2$	$5$
$2$	$5$	$10$
$3$	${10}^3$
$4$	${10}^5$
$5$	${10}^3$	${10}^9$	$0$
$6$	${10}^3$		${10}^3$
$7$	${10}^5$		${10}^5$
$8$	${10}^9$		${10}^9$
$9$
$10$

对于所有数据，保证 $2 \le n \le L \le R \le {10}^9$ 。

#思路

此题是一道结论题。

#代码

C++

#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）。服务机负责建立连接，客户机负责加入连接。

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

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

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

必须形如 a.b.c.d:e 的格式，其中 $a, b, c, d, e$ 均为非负整数；
$0 \le a, b, c, d \le 255$ ， $0 \le e \le 65535$ ；
$a, b, c, d, e$ 均不能含有多余的前导 $0$ 。

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

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

例如，地址串 192.168.0.255:80 是符合规范的，但 192.168.0.999:80、192.168.00.1:10、192.168.0.1:088、192:168:0:1.233 均是不符合规范的。

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

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

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

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

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

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

#输入格式

第一行，一个正整数 $n$ 。

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

其中 $\mathit{op}$ 保证为字符串 Server 或 Client 之一， $\mathit{ad}$ 为一个长度不超过 $25$ 的，仅由数字、字符 . 和字符 : 组成的非空字符串。

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

#输出格式

输出共 $n$ 行，每行一个正整数或字符串表示第 $i$ 台计算机的连接状态。其中：

如果第 $i$ 台计算机为服务机，则：

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

如果第 $i$ 台计算机为客户机，则：

如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户机连接到的服务机的编号。
如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串 FAIL。
如果其提供的地址串不是符合规范的地址串，输出字符串 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

计算机 $1$ 为服务机，提供符合规范的地址串 192.168.1.1:8080，成功建立连接；
计算机 $2$ 为服务机，提供与计算机 $1$ 相同的地址串，未能成功建立连接；
计算机 $3$ 为客户机，提供符合规范的地址串 192.168.1.1:8080，成功加入连接，并连接到服务机 $1$ ；
计算机 $4$ 为客户机，提供符合规范的地址串 192.168.1.1:80，找不到服务机与其连接；
计算机 $5$ 为客户机，提供的地址串 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

#数据范围与约定

测试点编号	$n \le$	特殊性质
$1$	$10$	性质 1 2 3
$2 \sim 3$	$100$
$4 \sim 5$	$1000$
$6 \sim 8$		性质 1 2
$9 \sim 11$		性质 1
$12 \sim 13$		性质 2
$14 \sim 15$		性质 4
$16 \sim 17$		性质 5
$18 \sim 20$		无特殊性质

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

对于 $100 \%$ 的数据，保证 $1 \le n \le 1000$ 。

#思路

细节稍多的模拟题。

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

#代码

C++

#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;
}

#小熊的果篮

#题面

#题目描述

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

#输入格式

第一行，包含一个正整数 $n$ ，表示水果的数量。

第二行，包含 $n$ 个空格分隔的整数，其中第 $i$ 个数表示编号为 $i$ 的水果的种类， $1$ 代表苹果， $0$ 代表桔子。

#输出格式

输出若干行。

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

#输入输出样例

样例输入 #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]$ ，一共有 $6$ 个块。

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

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

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

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

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

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

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

样例输入 #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 \%$ 的数据， $n \le 5$ 。
对于 $30 \%$ 的数据， $n \le 1000$ 。
对于 $70 \%$ 的数据， $n \le 50000$ 。
对于 $100 \%$ 的数据， $1 \le n \le 2 \times {10}^5$ 。

提示：由于数据规模较大，建议 C/C++ 选手使用 scanf 和 printf 语句输入、输出。

#思路

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

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

#代码

C++

#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;
}