整体难度分析

整体来说这一场 CSP 的比赛难度并不高，四道题基本都是模拟题，至少有 $310$ 分是纯暴力可以直接获得的

但是对代码量和细节问题的处理要求相对高一些，在 OI 的比赛模式中，很容易因为踩了一个坑导致分数非常低

整体来说难度不高，题目类型更加偏向于 CF 类的简单题

T1 分糖果

【题目背景】
红太阳幼儿园的小朋友们开始分糖果啦！

【题目描述】
红太阳幼儿园有 nn 个小朋友，你是其中之一。保证 n \ge 2n≥2。

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

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

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

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

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

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

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

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

【输入输出样例】
输入 #1
7 16 23
输出 #1
6
输入 #2
10 14 18
输出 #2
8
说明/提示
【样例解释 #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$。

【数据范围】

T1分析

送分题，题意就是在区间 $[L,R]$ 内求一个数 $k$ 使得 $k\%n$ 最大

那么我们只要找到比 $L$ 大的最小的 $n$ 的倍数即可

如果这个数字存在于 $[L,R]$ ，那么最后的答案就是 $n-1$

若这个最小的 $n$ 倍数不存在于 $[L,R]$ 内，那么答案就是区间最大值 $R\%n$

#include <iostream>
using namespace std;int main(){long long n, L, R;scanf("%lld%lld%lld", &n, &L, &R);long long temp = (L + n + 1) / n * n;temp = min(temp - 1, R);printf("%lld\n", temp % n);return 0;
}

T2 插入排序

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

假设比较两个元素的时间为 $\mathcal{O}(1)$，则插入排序可以以 $\mathcal{O}(n^2)$ 的时间复杂度完成长度为 $n$ 的数组的排序。不妨假设这 $n$ 个数字分别存储在 $a_1,a_2,\dots ,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 dofor j:=i downto 2 doif a[j]<a[j-1] thenbegint:=a[i];a[i]:=a[j];a[j]:=t;end;

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

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

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

$2x$：这是第二种操作，假设 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
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$，但是我们不能将其视为相同的元素。

【数据范围】

T2分析

1. 常规解法

乍一看题目会以为是一个数据结构的题目，又是单点更新又是查询数字排第几大，会认为是一个平衡树的题目
但是仔细观察以后会发现题目给出了一个很重要的条件：修改次数不超过5000，这是本题的第一个重点

然后需要注意观察样例和题目给出的伪代码，可以得到当数字一样时，下标小的数字被认为更小，这是本题的第二个重点

两者结合，可以得到暴力的解法就是每次修改操作以后都排序一遍，重新求 $rank$，这样的修改的复杂度是 $O(nlogn)$，查询的复杂度是 $O(1)$ ，代码复杂度为 $O(5000\ast nlogn)$，可以得到 $80$ 分

这里可以发现，每次修改只会修改一个数，那么如果这个数组本身就有序了，当修改过一个数字 $a[x]$ 以后，无非就是只有两种情况

1. $a[x]$ 左移
2. $a[x]$ 右移

所以这里完全没有必要重新 $sort$，只要手动处理一下 $a[x]$ 的移动即可，这样修改的复杂度就会降为 $O(n)$，那么整体复杂就是 $O(5000\ast n)$ 完全没有问题

#include <iostream>
#include <algorithm>
using namespace std;
struct XX{int val, id;
} a[100010];
int _rank[100010];bool cmp(const XX&x, const XX&y){if (x.val == y.val){return x.id < y.id;}return x.val < y.val;
}
int main(){int n, q;scanf("%d%d", &n, &q);for (int i = 1; i <= n; ++i){scanf("%d", &a[i].val);a[i].id = i;}sort(a + 1, a + n + 1, cmp);for (int i = 1; i <= n; ++i){_rank[a[i].id] = i;}while (q--){int op, x, y;scanf("%d", &op);if (op == 1){scanf("%d%d", &x, &y);x = _rank[x];a[x].val = y;while (x > 1 && !cmp(a[x - 1], a[x])){swap(a[x - 1], a[x]);x--;}while (x < n && !cmp(a[x], a[x + 1])){swap(a[x], a[x + 1]);x++;}for (int i = 1; i <= n; ++i){_rank[a[i].id] = i;}} else {scanf("%d", &x);printf("%d\n", _rank[x]);}}return 0;
}

2. 黑科技 pb_ds

就算这道题没有 操作数不超过 5000 这个限制，这道题也可以直接用 ext 拓展库 $pb\_ds$ 中的 $tree$ 直接解决，复杂度为 $O((n+q)logn)$

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef pair<int, int> PII;
tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> tr;
int a[100010];
int main(){int n, q;scanf("%d%d", &n, &q);for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);tr.insert(make_pair(a[i], i));}while (q--){int op, x, y;scanf("%d", &op);if (op == 1){scanf("%d%d", &x, &y);tr.erase(make_pair(a[x], x));a[x] = y;tr.insert(make_pair(a[x], x));} else {scanf("%d", &x);printf("%d\n", tr.order_of_key(make_pair(a[x], x)) + 1);}}return 0;
}

这里主要给出一个 $pb\_ds$ 简单使用方法
需要加载两个头文件 <ext/pb_ds/tree_policy.hpp>，<ext/pb_ds/assoc_container.hpp>
以及一个新的命名空间 using namespace __gnu_pbds;
声明一个 $tree$ 的代码比较长 tree<double, null_type, less<double>, rb_tree_tag, tree_order_statistics_node_update> tr;
下面用数字表示第几个参数
但是一般我们需要修改的只有两处：1.类型 和 3.排序规则，在例子的体现即为 PII 和 less<PII>

1.类型可以使用我们常规的类型，int，double，pair 等
2.映射方式这里一般都填写 null_type，如果是低版本的 $g++$ 编译器可能需要填的是 null_mapped_type
3.排序规则可以使用常规的两种，less<T> 和 greater<T>，当然也可以自定义 cmp 函数传入
4.树类型,树的类型有很多种，但是一般常用的只有 红黑树rb_tree_tag 和 伸展树splay_tree_tag
5.节点更新方式，一般也就只填 tree_order_statistics_node_update

#include <cstdio>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>using namespace std;
using namespace __gnu_pbds;tree<double, null_type, greater<double>, rb_tree_tag, tree_order_statistics_node_update> T;int main(){int q, opt, x;scanf("%d", &q);for (int i = 1; i <= q; ++ i){scanf("%d%d", &opt, &x);//插入一个数if(opt == 1) T.insert(x + i * 1e-6);//删除一个数if(opt == 2) T.erase(T.lower_bound(x));//查询一个数的排名if(opt == 3) printf("%d\n", (int)T.order_of_key(x) + 1);//查询第k小的数 返回的是一个迭代器 这里k是从0开始算的，意思是最小的数是第0小的if(opt == 4) printf("%d\n", (int)*T.find_by_order(x - 1));//查询一个数的前驱if(opt == 5) printf("%d\n", (int)round(*(-- T.lower_bound(x))));//查询一个数的后继if(opt == 6) printf("%d\n", (int)round(*T.lower_bound(x + 1)));}return 0;
}

T3 网络连接

【题目描述】
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$ 行，每行两个字符串 $op,ad$，按照编号从小到大给出每台计算机的类型及地址串。

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

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

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

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

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

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

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

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

【说明/提示】
【样例解释 #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 不符合规范。

【数据范围】

T3分析

模拟题，根据题目给出的题意直接判断即可

1. $IP$ 地址必须包含 $3$ 个 . 和 $1$ 个 :，并且顺序必须是 ...:
2. 前四个数字的范围是 $[0,255]$，最后一个数字的范围是 $[0,65535]$
3. 不能存在前导零

题目里保证了只有数字，. 和 : ，避免了会出现负数的情况，这其实降低了题目的难度

这里给出几种可能会出错的情况

1. IP 地址确实包含了 $3$ 个 . 和 $1$ 个 : ，但是顺序不对，可能出现了 ..:. 这种分布
2. 前导 $0$ 要注意判断是否是 $0$ 本身，只有 “0” 这个情况允许第一位出现 0，否则不允许第一位数字为 0

代码主要分两步，一个是 $check$ 函数判断 $IP$ 是否合法，若 $IP$ 合法则用一个 $map$ 直接记录每个 $IP$ 的编号即可

#include <iostream>
#include <map>
using namespace std;map<string, int> mp;
string op, ip;bool check(string x){x += ".";string now = "";int point = 0;for (int i = 0; i < x.size(); ++i){if (x[i] == '.' || x[i] == ':'){point++;if (point != 4 && x[i] == ':'){return false;}if (now == "" || (now[0] == '0' && now != "0") || point > 5){return false;}int number = 0;for (int i = 0; i < now.size(); ++i){number = number * 10 + now[i] - 48;if (number > 65535){return false;	}	}if ((point < 5 && number > 255) || (point == 5 && number > 65535)){return false;}now = "";} else {now = now + x[i];}}return point == 5;
}int main(){int n;cin >> n;for (int cnt = 1; cnt <= n; ++cnt){cin >> op >> ip;if (check(ip)){if (op == "Server"){if (mp.count(ip)){printf("FAIL\n");} else {mp[ip] = cnt;printf("OK\n");}}else{if (mp.count(ip)){printf("%d\n", mp[ip]);} else {printf("FAIL\n");}}} else {printf("ERR\n");}}return 0;
}

T4 小熊的果篮

【题目描述】
小熊的水果店里摆放着一排 $n$ 个水果。每个水果只可能是苹果或桔子，从左到右依次用正整数 $1,2,\dots ,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
输入 #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

【说明/提示】
【样例解释 #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$

T4分析

个人认为难度反而没有 T3 高

在一条链中，相同的数字被认为是一个块，每轮同事删除所有块最左边的那个数字，而删除数字后可能会存在一些块的合并，这个问题显然用双向链表可以快速解决删除的问题，而我们也很容易发现，总的块数只会随着删除变少或不变，也就是只可能出现合并的情况，不可能出现因为删除使得一个块变成两个块的情况

那么我们用一个数组 $ans$ 记录当前所有块的第一个数字

而当 $x=ans[i]$ 删除时，合并 $l=L[ans[i]]和r=R[ans[i]]$

此时如果 $a[x]!=a[l]$ 且 $a[r]==a[x]$ ，那么我们可以认为，删除 $a[x]$ 时不会发生合并，那么就把 $a[x]$ 的下一个数

字 $a[r]$ 放入下一轮的 $ans$ 中，否则就不放入

这里注意，删除的时候不能简单的认为 $a[r]!=a[l]$ 就可以将 $r$ 放入下一轮，

因为有可能存在连续删除的情况，例如样例的第二轮，删除的是相邻的几个数字 $246$

所以我们可以利用块只有可能合并这个特点，考虑只有当 $a[r]!=a[l]$ 且 $a[r]==a[x]$ 时才放入 $r$ 到下一轮 $ans$

#include <iostream>
using namespace std;int a[200100];
int ans[200100], len;
int L[200100], R[200100];
int main(){int n;scanf("%d", &n);a[0] = a[n + 1] = -1;R[0] = 1; L[n + 1] = n;for (int i = 1; i <= n; ++i){scanf("%d", &a[i]);L[i] = i - 1;R[i] = i + 1;if (a[i] != a[i - 1]){ans[len++] = i;}}while (len){int new_len = 0;for (int i = 0; i < len; ++i){printf("%d ", ans[i]);int l = L[ans[i]];int r = R[ans[i]];L[r] = l;R[l] = r;	if (a[r] != -1 && a[ans[i]] == a[r] && a[r] != a[l]){ans[new_len++] = r;}}len = new_len;printf("\n");}return 0;
}