[CSP-J 2021] 分糖果

题目背景

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

题目描述

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

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

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

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

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

7 16 23

样例输出 #1

6

样例 #2

样例输入 #2

10 14 18

样例输出 #2

8

样例 #3

样例输入 #3

见附件中的 candy/candy3.in。

样例输出 #3

见附件中的 candy/candy3.ans。

提示

【样例解释 #1】

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

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

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

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

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

【样例解释 #2】

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

【数据范围】

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

解析

题目描述

给你三个数 $n$、$l$、$r$，让你在区间 ([l, r]) 中找到一个整数 $x$，使得 $n \mod x$ 最大，并输出这个最大的 $n \mod x$ 的值。

解题思路

70分思路：暴力枚举

我们可以通过暴力枚举的方式，遍历区间 ([l, r]) 中的每一个整数 $x$，并计算 $n \mod x$ 的值，找出其中的最大值。虽然这种方法能解决问题，但效率较低，尤其当区间 ([l, r]) 较大时，时间复杂度较高。

100分思路：利用取余运算的性质

为得到最优解，我们需要运用取余运算的两个简单性质：

1. 对于任意正整数 $x$，$n \mod x$ 的结果总是在 ([0, n-1]) 的范围内。
2. 若 $x \mod n = y$，则 $(x + n) \mod n = y$，即加上 $n$ 后，模 $n$ 的结果不变。

基于这两个性质，我们可以更有效地求解此题。

解决方案

情况 1：当 $r - l + 1 \geq n$

如果区间的长度大于或等于 $n$，则区间 ([l, r]) 中的整数可以覆盖 ([0, n-1]) 之间的所有余数。因此，最大的 $n \mod x$ 值即为 $n - 1$。这种情况下，答案为 $n - 1$。

情况 2：当 $r - l + 1 < n$

如果区间的长度小于 $n$，则需要进一步分类讨论：

1. 若 $l \mod n \leq r \mod n$：这种情况下，区间 ([l, r]) 中的整数 $x$ 对 $n$ 取余的结果将包含从 $l \mod n$ 到 $r \mod n$ 的所有余数。此时，最大的取余值为 $r \mod n$。

2. 若 $l \mod n > r \mod n$：在这种情况下，区间 ([l, r]) 中的取余结果跨越了模 $n$ 的边界，余数的范围分为两段。此时，最大的取余值是 $n - 1$，因为这是模 $n$ 取余的最大值。

总结

这道题的关键在于分类讨论。必须确保不重不漏地处理所有可能的情况，否则容易出错。

代码实现

#include <cstdio>
using namespace std;

int n, L, R;

int main() {
    freopen("candy.in", "r", stdin);  // 重定向输入文件
    freopen("candy.out", "w", stdout);  // 重定向输出文件
    
    scanf("%d%d%d", &n, &L, &R);  // 输入 n、L、R
    
    if (R - L + 1 >= n) {
        printf("%d\n", n - 1);  // 若区间长度大于等于 n，输出 n-1
    } else {
        if (L % n <= R % n) {
            printf("%d\n", R % n);  // 若 L mod n <= R mod n，输出 R mod n
        } else {
            printf("%d\n", n - 1);  // 若 L mod n > R mod n，输出 n-1
        }
    }
    
    return 0;
}

代码解析

1. 输入输出重定向：通过 freopen 函数从文件中读取输入并将输出写入文件。
2. 输入 n、L、R：表示取余的基数 $n$ 以及区间的左边界 $L$ 和右边界 $R$。
3. 判断区间长度：
   • 若 $R - L + 1 \geq n$，则区间内可以包含所有 $n$ 的余数，此时答案为 $n - 1$。
   • 若区间长度不足 $n$，根据 $L \mod n$ 和 $R \mod n$ 的关系进行进一步的分类讨论。
4. 输出结果：根据条件输出最大的 $n \mod x$ 的值。

这道题主要考查对模运算性质的理解和分类讨论的能力，通过合理的推理可以大幅降低时间复杂度，避免暴力枚举的低效做法。

[CSP-J 2021] 插入排序

题目描述

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生，今天 H 老师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为 $\mathcal O(1)$，则插入排序可以以 $\mathcal O(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1, a_2, \ldots, a_n$ 之中，则如下伪代码给出了插入排序算法的一种最简单的实现方式：

这下面是 C/C++ 的示范代码：

for (int i = 1; i <= n; i++)
	for (int j = i; j >= 2; j--)
		if (a[j] < a[j-1]) {
			int t = a[j-1];
			a[j-1] = a[j];
			a[j] = t;
		}

这下面是 Pascal 的示范代码：

for i:=1 to n do
	for j:=i downto 2 do
		if a[j]<a[j-1] then
			begin
				t:=a[i];
				a[i]:=a[j];
				a[j]:=t;
			end;

为了帮助小 Z 更好的理解插入排序，小 Z 的老师 H 老师留下了这么一道家庭作业：

H 老师给了一个长度为 $n$ 的数组 $a$，数组下标从 $1$ 开始，并且数组中的所有元素均为非负整数。小 Z 需要支持在数组 $a$ 上的 $Q$ 次操作，操作共两种，参数分别如下：

$1~x~v$：这是第一种操作，会将 $a$ 的第 $x$ 个元素，也就是 $a_x$ 的值，修改为 $v$。保证 $1 \le x \le n$，$1 \le v \le 10^9$。注意这种操作会改变数组的元素，修改得到的数组会被保留，也会影响后续的操作。

$2~x$：这是第二种操作，假设 H 老师按照上面的伪代码对 $a$ 数组进行排序，你需要告诉 H 老师原来 $a$ 的第 $x$ 个元素，也就是 $a_x$，在排序后的新数组所处的位置。保证 $1 \le x \le n$。注意这种操作不会改变数组的元素，排序后的数组不会被保留，也不会影响后续的操作。

H 老师不喜欢过多的修改，所以他保证类型 $1$ 的操作次数不超过 $5000$。

小 Z 没有学过计算机竞赛，因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

输入格式

第一行，包含两个正整数 $n, Q$，表示数组长度和操作次数。

第二行，包含 $n$ 个空格分隔的非负整数，其中第 $i$ 个非负整数表示 $a_i$。

接下来 $Q$ 行，每行 $2 \sim 3$ 个正整数，表示一次操作，操作格式见【题目描述】。

输出格式

对于每一次类型为 $2$ 的询问，输出一行一个正整数表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

1
1
2

提示

【样例解释 #1】

在修改操作之前，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 2, 1$。

在修改操作之后，假设 H 老师进行了一次插入排序，则原序列的三个元素在排序结束后所处的位置分别是 $3, 1, 2$。

注意虽然此时 $a_2 = a_3$，但是我们不能将其视为相同的元素。

【样例 #2】

见附件中的 sort/sort2.in 与 sort/sort2.ans。

该测试点数据范围同测试点 $1 \sim 2$。

【样例 #3】

见附件中的 sort/sort3.in 与 sort/sort3.ans。

该测试点数据范围同测试点 $3 \sim 7$。

【样例 #4】

见附件中的 sort/sort4.in 与 sort/sort4.ans。

该测试点数据范围同测试点 $12 \sim 14$。

【数据范围】

对于所有测试数据，满足 $1 \le n \le 8000$，$1 \le Q \le 2 \times {10}^5$，$1 \le x \le n$，$1 \le v,a_i \le 10^9$。

对于所有测试数据，保证在所有 $Q$ 次操作中，至多有 $5000$ 次操作属于类型一。

各测试点的附加限制及分值如下表所示。

解析

题目简述

给定长度为 $n$ 的序列 $a_i$，需要维护两个操作：

1. 单点修改：修改序列中某个位置的元素值；
2. 查询排序后的某个元素的原始下标。

输入的约束为：

• $n \leq 8000$，查询次数 $q \leq 2 \times 10^5$，其中修改操作不超过 5000 次。

解题思路

对于一个已经有序的数列，当我们对其中的一个元素进行单点修改时，可以通过局部的前后冒泡各一次来保持数列的有序性。

具体操作示例

假设原始序列为：

$$1, 1, 4, 5, 6, 7$$

将第 3 个元素修改为 9 后，得到序列：

$$1, 1, 9, 5, 6, 7$$

这时，我们可以通过从前往后进行一次冒泡操作，使序列重新保持有序。这样每次操作的时间复杂度是 $O(n)$。

维护有序序列和下标关系

我们可以维护一个有序序列，同时记录每个元素的原始下标和排序后的下标之间的关系。修改操作后，我们更新有序序列的同时，调整下标关系。

通过这种方式：

• 修改操作的时间复杂度是 $O(n)$；
• 查询操作的时间复杂度是 $O(1)$。

这样可以高效解决问题。

代码实现

下面是实际的考场代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=8005;  // 最大长度
int n, q;  // n 表示序列长度，q 表示查询次数
int t[MAXN];  // t[i] 表示元素 i 在排序后的下标
struct node {
    int pre, id;  // pre 表示元素值，id 表示元素的原始下标
} a[MAXN];  // 存储序列元素
// 比较函数，用于按值和下标对元素排序
bool cmp(node x, node y) {
    if (x.pre != y.pre) return x.pre < y.pre;
    return x.id < y.id;
}

int main() {
    // freopen("sort.in", "r", stdin);  // 输入重定向（可选）
    // freopen("sort.out", "w", stdout);  // 输出重定向（可选）
    scanf("%d%d", &n, &q);  // 读取序列长度 n 和查询次数 q
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i].pre);  // 读取每个元素的值
        a[i].id = i;  // 记录元素的原始下标
    }
    // 初始排序
    sort(a + 1, a + n + 1, cmp);  // 根据值和下标排序
    // 更新每个元素的排序后下标
    for (int i = 1; i <= n; i++) {
        t[a[i].id] = i;
    }
    
    for (int i = 1; i <= q; i++) {
        int opt, x, v;
        scanf("%d", &opt);  // 读取操作类型
        if (opt == 1) {  // 修改操作
            scanf("%d%d", &x, &v);  // 修改第 x 个元素的值为 v
            a[t[x]].pre = v;  // 更新元素值
            // 从后往前进行冒泡操作，保持有序
            for (int j = n; j >= 2; j--)
                if (cmp(a[j], a[j-1])) {
                    node kkksc03 = a[j];
                    a[j] = a[j-1];
                    a[j-1] = kkksc03;
                }
            // 从前往后进行冒泡操作，保持有序
            for (int j = 2; j <= n; j++)
                if (cmp(a[j], a[j-1])) {
                    node kkksc03 = a[j];
                    a[j] = a[j-1];
                    a[j-1] = kkksc03;
                }
            // 更新下标关系
            for (int i = 1; i <= n; i++) {
                t[a[i].id] = i;
            }
        } else {  // 查询操作
            scanf("%d", &x);  // 查询第 x 个元素
            printf("%d\n", t[x]);  // 输出排序后该元素的下标
        }
    }
    return 0;
}

代码解析

1. 输入输出：
   • scanf 用于读取序列长度、查询次数以及每次的修改或查询操作。
2. 结构体 node：
   • pre：记录元素的值；
   • id：记录元素的原始下标，方便修改后重新映射排序后的下标。
3. 排序与下标更新：
   • 使用 sort 函数对初始序列按照值和下标排序；
   • 维护一个数组 t，其中 t[i] 代表元素 i 在排序后的位置。
4. 修改操作：
   • 修改某个元素后，通过从前向后、从后向前各进行一次冒泡操作来保持有序性。
5. 查询操作：
   • 查询某个元素在排序后的下标，直接输出。

为什么前后各冒泡一次？

当修改一个元素时，我们不知道该元素是变大了还是变小了。因此：

• 如果该元素变小了，可能需要将它向前移动，保持有序；
• 如果该元素变大了，可能需要将它向后移动，保持有序。

因此，我们需要前后各进行一次冒泡操作，以确保整个序列重新有序。

示例

原始序列为 $4, 5, 6$，如果将 5 改为 1，则需要向前移动，保持有序；如果将 5 改为 9，则需要向后移动，保持有序。

[CSP-J 2021] 网络连接

题目描述

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

在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机负责建立连接，客户机负责加入连接。

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

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

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

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

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

1. 不是形如 a.b.c.d:e 格式的字符串，例如含有多于 $3$ 个字符 . 或多于 $1$ 个字符 : 等情况；
2. 整数 $a, b, c, d, e$ 中某一个或多个超出上述范围；
3. 整数 $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$ 台计算机为服务机，则：

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

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

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

样例 #1

样例输入 #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

样例 #2

样例输入 #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

样例 #3

样例输入 #3

见附件中的 network/network3.in。

样例输出 #3

见附件中的 network/network3.ans。

样例 #4

样例输入 #4

见附件中的 network/network4.in。

样例输出 #4

见附件中的 network/network4.ans。

提示

【样例解释 #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 不符合规范。

【数据范围】

“性质 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$。

解析

题目分析

主要问题是判断一个地址（形如 a.b.c.d:e）是否合法，并进行服务机和客户机的地址注册与查找操作。

解决方案

1. 地址合法性判断

为了判断输入的地址是否合法，可以使用 sscanf 读取形如 a.b.c.d:e 的字符串，并解析成 5 个部分：a, b, c, d 和 e。

判断步骤如下：

1. 检查读取结果的数量：sscanf 会返回读取成功的项数。如果读取的项数不是 5 个，则该地址不合法。
2. 检查各部分的取值范围：
   • a, b, c, d 是 IP 地址的四个部分，必须满足范围：0 ≤ a, b, c, d ≤ 255。
   • e 是端口号，必须满足范围：0 ≤ e ≤ 65535。
3. 检查字符串一致性：再将 a.b.c.d:e 按格式拼接成一个新的字符串，检查它是否与原始输入字符串相同。这一步可以有效判断前导 0 的情况。例如，输入 01.2.3.4:5 时，解析后的 a = 1，拼接后字符串为 1.2.3.4:5，此时与原输入字符串 01.2.3.4:5 不同，因此该地址不合法。

2. 前导 0 的问题

前导 0 的问题通过解析后字符串的重构解决。如果输入 01.2.3.4:5，解析后 a = 1，拼接成的新字符串是 1.2.3.4:5，与原字符串不相同，因此不合法。这种方式自然地处理了前导 0 的问题。

3. 服务机和客户机操作

对于服务机的注册和客户机的连接操作，使用一个 map<string, int> 来记录已经注册的服务机地址。map 中的 string 用来存储地址，int 用来存储注册的编号。

操作流程：

• 服务机（注册）：如果地址合法并且未被注册，则输出 OK 并保存该地址和编号；如果该地址已被注册，输出 FAIL。
• 客户机（查找）：如果地址合法并且存在对应的服务机，输出服务机的编号；如果不存在，输出 FAIL。

特殊情况

• 非法地址：输入的地址不合法时，直接输出 ERR。
• 前导 0：解析后重构的字符串与原始字符串不一致时，认为地址不合法。

代码实现

#include<bits/stdc++.h>
using namespace std;

// 定义一个 map 来记录已注册的服务机地址和其编号
map<string,int> vis;
int n;

// 判断输入的地址是否合法
bool check(char s[]) {
    int a=-1, b=-1, c=-1, d=-1, e=-1;
    // 尝试解析地址并将结果保存在 a, b, c, d, e 中
    int t = sscanf(s, "%d.%d.%d.%d:%d", &a, &b, &c, &d, &e);
    
    // 判断解析的结果是否有 5 个部分
    if(t != 5) return false;
    
    // 判断 a, b, c, d 是否在 0 到 255 之间，e 是否在 0 到 65535 之间
    if(a < 0 || a > 255) return false;
    if(b < 0 || b > 255) return false;
    if(c < 0 || c > 255) return false;
    if(d < 0 || d > 255) return false;
    if(e < 0 || e > 65535) return false;
    
    // 将 a.b.c.d:e 格式化成字符串 s2
    char s2[35];
    sprintf(s2, "%d.%d.%d.%d:%d", a, b, c, d, e);
    
    // 判断原字符串 s 和格式化后的字符串 s2 是否完全相同
    int lens = strlen(s); // 原字符串长度
    bool ok = true; // 是否相同的标志
    for(int i = 0; i < lens; i++) {
        if(s[i] != s2[i]) {
            ok = false;
            break;
        }
    }
    return ok; // 返回是否相同
}

int main() {
    cin >> n; // 读取操作的总数
    for(int i = 1; i <= n; i++) {
        char op[1005], ad[1005]; // 操作类型和地址
        cin >> op >> ad;
        string t(ad); // 将地址转换为字符串
        
        if(op[0] == 'S') { // 如果是服务机注册操作
            if(!check(ad)) cout << "ERR" << endl; // 地址不合法
            else if(vis.count(t) != 0) { // 地址已被注册
                cout << "FAIL" << endl;
            } else {
                cout << "OK" << endl; // 注册成功
                vis[t] = i; // 保存该地址和编号
            }
        } else { // 客户机连接操作
            if(!check(ad)) { // 地址不合法
                cout << "ERR" << endl;
            } else if(vis.count(t) == 0) { // 地址未注册
                cout << "FAIL" << endl;
            } else {
                cout << vis[ad] << endl; // 输出服务机编号
            }
        }
    }
}

代码解析

1. 输入输出：读取操作次数 n，然后逐条读取操作类型（op）和地址（ad）。
2. 服务机注册：
   • 先通过 check() 函数判断地址是否合法。
   • 若地址合法且未被注册，输出 OK 并保存到 map 中。
   • 若地址已注册，输出 FAIL。
3. 客户机连接：
   • 通过 check() 函数判断地址是否合法。
   • 若合法且对应服务机已注册，输出服务机的编号。
   • 若未注册，输出 FAIL。
4. 地址验证：通过 check() 函数进行格式验证，并解决前导 0 的问题。

[CSP-J 2021] 小熊的果篮

题目描述

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

输入格式

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

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

输出格式

输出若干行。

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

样例 #1

样例输入 #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

样例 #2

样例输入 #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

样例 #3

样例输入 #3

见附件中的 fruit/fruit3.in。

样例输出 #3

见附件中的 fruit/fruit3.ans。

提示

【样例解释 #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$ 的水果被挑了出来。

【数据范围】

对于 $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 语句输入、输出。

解析

题目描述

小熊的水果店里有一排 $n$ 个水果，每个水果要么是苹果，要么是桔子，从左到右依次用正整数 1 到 $n$ 编号。连续排列在一起的同种水果称为一个“块”。小熊将这排水果挑到若干个果篮里，挑选方法如下：

• 每次从每个“块”中最左边的水果挑出，组成一个果篮。
• 每次挑选后，若某些水果块相邻，且种类相同，则这些块会合并成一个新的“块”。
• 重复该过程，直到所有水果都被挑走。

你需要帮助小熊计算每个果篮里包含的水果。

题解思路

为了模拟挑选和合并的过程，我们可以使用双向链表来维护水果块的结构。具体步骤如下：

1. 双向链表的构建：建立两个双向链表，一个用于维护每个水果的前后关系，另一个用于维护每个“块”的块头。块头是指每个块中最左边水果的位置。
2. 吃掉水果的操作：每次从每个“块”中最左边的水果开始挑出，即删除链表中的相应元素。与此同时，检查块是否需要合并，如果相邻块的水果种类相同，则将它们合并。
3. 遍历与删除：遍历块头链表，对于每个块的块头，挑出水果后更新其指向的下一个水果。若该水果与上一个被吃掉的水果种类相同，则合并块，否则继续处理。

时间复杂度分析：每个水果被遍历一次，每个块被删除一次，因此整体时间复杂度为 $\Theta(n)$。

代码实现

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 2e5+10;

struct Node {
  int prev;  // 前一个水果的位置
  int val;   // 当前水果的位置
  int next;  // 下一个水果的位置
};

int n;  // 水果数量
int shuiguo[MAXN];  // 水果种类数组
Node headList[MAXN];  // 维护块头链表
Node shuiguoList[MAXN];  // 维护水果链表
int cc;  // 块的数量

// 删除水果
void EatOne(int pos) {
  int prev = shuiguoList[pos].prev;
  int next = shuiguoList[pos].next;
  shuiguoList[prev].next = next;
  shuiguoList[next].prev = prev;
  printf("%d ", pos);  // 输出当前被吃掉的水果编号
}

// 删除块头
void Del(int pos) {
  int prev = headList[pos].prev;
  int next = headList[pos].next;
  headList[prev].next = next;
  headList[next].prev = prev;
}

// 模拟吃水果的过程
void Chi() {
  int solo = headList[0].next;  // 从第一个块头开始
  int nowcolor = shuiguo[headList[solo].val];  // 当前水果的种类
  while (solo != cc + 1) {  // 遍历所有块
    if (shuiguo[headList[solo].val] != nowcolor) {  // 如果块头水果种类不同
      Del(solo);  // 删除块头
      solo = headList[solo].next;
      continue;
    }
    EatOne(headList[solo].val);  // 吃掉块头的水果
    headList[solo].val = shuiguoList[headList[solo].val].next;  // 更新块头为下一个水果
    if (shuiguo[headList[solo].val] != nowcolor) {  // 若下一个水果种类不同
      Del(solo);  // 删除块头
    }
    solo = headList[solo].next;
    nowcolor ^= 1;  // 切换当前水果种类
  }
  putchar('\n');  // 输出换行符
}

int main() {
  scanf("%d", &n);  // 读取水果数量
  shuiguoList[0].next = 1;  // 初始化第一个水果
  for (int i = 1; i <= n; i++) {
    scanf("%d", &shuiguo[i]);  // 读取水果种类，1表示苹果，0表示桔子
    shuiguoList[i].prev = i - 1;  // 链接前一个水果
    shuiguoList[i].next = i + 1;  // 链接下一个水果
  }
  shuiguo[0] = 2;  // 边界条件，设置左边界水果种类为 2（非苹果非桔子）
  shuiguo[n + 1] = 2;  // 边界条件，设置右边界水果种类为 2
  headList[0].next = 1;  // 初始化块头链表
  for (int i = 1; i <= n; i++) {
    if (shuiguo[i] != shuiguo[i - 1]) {  // 若水果种类与前一个不同，则形成新的块
      cc++;  // 块数量加1
      headList[cc].prev = cc - 1;  // 链接前一个块头
      headList[cc].next = cc + 1;  // 链接下一个块头
      headList[cc].val = i;  // 当前块头的位置
    }
  }
  while (shuiguoList[0].next != n + 1) {  // 循环处理直到所有水果都被吃完
    Chi();  // 每次处理一轮挑水果
  }
  return 0;
}

代码解析

1. 双向链表的构建：

   • shuiguoList 用于维护每个水果的前后关系。
   • headList 用于维护每个块的块头，即最左边的水果位置。

2. 吃掉水果：

   • EatOne 函数用于从链表中删除一个水果。
   • Del 函数用于删除块头，合并相邻的同种水果块。

3. 处理水果块：

   • Chi 函数循环处理块头，吃掉块头水果并更新块头。如果相邻块水果种类相同，则合并块。

4. 主循环：

   • 主循环调用 Chi 函数，直到所有水果都被吃完。