2024年5月4日发(作者：)

2021CCF非专业级软件能力认证

CSP-J/S2021第二轮认证

入门组

时间：2021年10月23日08:30∼12:00

题目名称

题目类型

目录

可执行文件名

输入文件名

输出文件名

每个测试点时限

内存限制

子任务数目

测试点是否等分

分糖果

传统型

candy

candy

1.0秒

512MiB

10

否

插入排序

传统型

sort

sort

1.0秒

512MiB

25

是

网络连接

传统型

network

network

1.0秒

512MiB

20

是

小熊的果篮

传统型

fruit

fruit

1.0秒

512MiB

10

是

提交源程序文件名

对于C++语言

对于C语言

对于Pascal语言

编译选项

对于C++语言

对于C语言

对于Pascal语言

‐O2‐lm

‐O2‐lm

‐O2

candy.c

sort.c

network.c

fruit.c

注

.

意

.

事

.

项（

.

请

.

仔

.

细

.

阅

.

读）

.

1.文件名（程序名和输入输出文件名）必须使用英文小写。

2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须

是0。

3.提交的程序代码文件的放置位置请参考各省的具体要求。

4.因违反以上三点而出现的错误或问题，申述时一律不予受理。

5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。

6.程序可使用的栈空间内存限制与题目的内存限制一致。

7.全国统一评测时采用的机器配置为：Inter(R)Core(TM)i7-8700KCPU@3.70GHz，

内存32GB。上述时限以此配置为准。

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

8.只提供Linux格式附加样例文件。

9.评测在当前最新公布的NOILinux下进行，各语言的编译器版本以此为准。

第2页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

分糖果（candy）

分糖果（candy）

【题目背景】

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

【题目描述】

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

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

园的小朋友们。

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

回去。

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

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

如果你拿了k块糖，你将把这k块糖放到篮子里，并要求大家按照如下方案分糖

果：只要篮子里有不

.

少

.

于

.

n块糖果，幼儿园的所有n个小朋友（包括你自己）都从篮子

中拿走恰

.

好

.

一块糖，直到篮子里的糖数量少

.

于

.

n块。此时篮子里剩余的糖果均归你所有

——这些糖果是作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

。

作为幼儿园高质量小朋友，你希望让作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

的糖果数量（而

.

不

.

是

.

你

.

最

.

后

.

获

.

得

.

的

.

总

.

糖

.

果

.

数

.

量！

.

）尽可能多；因此你需要写一个程序，依次输入n,L,R，并输出

出你最多能获得多少作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

的糖果数量。

【输入格式】

从文件中读入数据。

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

界。

【输出格式】

输出到文件中。

输出一行一个整数，表示你最多能获得的作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

的糖果数量。

【样例1输入】

1

71623

第3页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

分糖果（candy）

【样例1输出】

1

6

【样例1解释】

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

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

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

篮子里现在糖果数变成6

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

。

容易发现，你获得的作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

的糖果数量不可能超过6块（不然，篮子

里的糖果数量最后仍然不少于n，需要继续每个小朋友拿一块），因此答案是6。

【样例2输入】

1

101418

【样例2输出】

1

8

【样例2解释】

容易发现，当你拿的糖数量k满足14=L≤k≤R=18时，所有小朋友获得一块

糖后，剩下的k−10块糖总是作

.

为

.

你

.

搬

.

糖

.

果

.

的

.

奖

.

励

.

的糖果数量，因此拿k=18块是最

优解，答案是8。

【样例3】

见选手目录下的candy/与candy/。

第4页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

分糖果（candy）

【数据范围】

测试点

1

2

3

4

5

6

7

8

9

10

对于所有数据，保证2≤n≤L≤R≤10

9

。

10

9

n≤

2

5

10

3

10

5

10

3

10

5

10

9

R≤

5

10

10

3

10

5

R−L≤

5

10

10

3

10

5

0

10

3

10

5

10

9

第5页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

插入排序（sort）

插入排序（sort）

【题目描述】

插入排序是一种非常常见且简单的排序算法。小Z是一名大一的新生，今天H老

师刚刚在上课的时候讲了插入排序算法。

假设比较两个元素的时间为O(1)，则插入排序可以以O(n

2

)的时间复杂度完成长

度为n的数组的排序。不妨假设这n个数字分别存储在a

1

,a

2

,···,a

n

之中，则如下伪

代码给出了插入排序算法的一种最简单的实现方式：

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

1

2

3

4

5

6

7

for(inti=1;i<=n;i++)

for(intj=i;j>=2;j‐‐)

if(a[j]

intt=a[j‐1];

a[j‐1]=a[j];

a[j]=t;

}

这下面是Pascal的示范代码

1

2

3

4

5

6

7

8

fori:=1tondo

forj:=idownto2do

ifa[j]

begin

t:=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≤x≤n,1≤v≤10

9

。注

.

意

.

这

.

种

.

操

.

作

.

会

.

改

.

变

.

数

.

组

.

的

.

元

.

素，

.

修

.

改

.

得

.

到

.

的

.

数

.

组

.

会

.

被

.

保

.

留，

.

也

.

会

.

影

.

响

.

后

.

续

.

的

.

操

.

作。

.

2x:这是第二种操作，假设H老师按照上

.

面

.

的

.

伪

.

代

.

码

.

对a数组进行排序，你需要

告诉H老师原来a的第x个元素，也就是a

x

，在排序后的新数组所处的位置。保证

1≤x≤n。注

.

意

.

这

.

种

.

操

.

作

.

不

.

会

.

改

.

变

.

数

.

组

.

的

.

元

.

素，

.

排

.

序

.

后

.

的

.

数

.

组

.

不

.

会

.

被

.

保

.

留，

.

也

.

不

.

会

.

影

.

响

.

后

.

续

.

的

.

操

.

作。

.

第6页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

插入排序（sort）

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

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

这个问题。

【输入格式】

从文件中读入数据。

输入的第一行包含两个正整数n,Q，表示数组长度和操作次数。保证1≤n≤

8,000,1≤Q≤2×10

5

。

输入的第二行包含n个空格分隔的非负整数，其中第i个非负整数表示a

i

。保证

1≤a

i

≤10

9

。

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

【输出格式】

输出到文件中。

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

【样例1输入】

1

2

3

4

5

6

34

321

23

132

22

23

【样例1输出】

1

2

3

1

1

2

【样例1解释】

在修改操作之前，假设H老师进行了一次插入排序，则原序列的三个元素在排序

结束后所处的位置分别是3,2,1。

第7页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

插入排序（sort）

在修改操作之前，假设H老师进行了一次插入排序，则原序列的三个元素在排序

结束后所处的位置分别是3,1,2。

注意虽然此时a

2

=a

3

，但是我们不

.

能

.

将

.

其

.

视

.

为

.

相

.

同

.

的

.

元

.

素

.

。

【样例2】

见选手目录下的sort/与sort/。

该测试点数据范围同测试点1∼2。

【样例3】

见选手目录下的sort/与sort/。

该测试点数据范围同测试点3∼7。

【样例4】

见选手目录下的sort/与sort/。

该测试点数据范围同测试点12∼14。

【数据范围】

对于所有测试数据，满足1≤n≤8,000,1≤Q≤2×10

5

,1≤x≤n,1≤v,a

i

≤10

9

。

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

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

测试点

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

≤8,000

≤2×10

5

n

≤10

≤300

≤1,500

Q

≤10

≤300

≤1,500

≤8,000

保证所有输入的a

i

,v互不相同

无

保证所有输入的a

i

,v互不相同

无

无

特殊性质

第8页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

网络连接（network）

网络连接（network）

【题目描述】

TCP/IP协议是网络通信领域的一项重要协议。今天你的任务，就是尝试利用这个

协议，还原一个简化后的网络连接场景。

在本问题中，计算机分为两大类：服务机（Server）和客户机（Client）。服务机

负责建立连接，客户机负责加入连接。

需要进行网络连接的计算机共有n台，编号为1∼n，这些机器将按编号递增的顺

序，依次发起一条建立连接或加入连接的操作。

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

它尝试建立连接的地址，客户机提供的地址串表示它尝试加入连接的地址。

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

1、必须形如d:e的格式，其中a,b,c,d,e均为非负整数；

2、0≤a,b,c,d≤255,0≤e≤65535；

3、a,b,c,d,e均不能含有多余的前导0。

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

1、不是形如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均是不符合规范的。

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

略。

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

虑每个地址串的实际意义。

由于网络阻塞等原因，不允许两台服务机使用相同的地址串，如果此类现象发生，

后一台尝试建立连接的服务机将会无法成功建立连接；除此之外，凡是提供符合规范的

地址串的服务机均可成功建立连接。

如果某台提供符合规范的地址的客户机在尝试加入连接时，与先前某台已经成功建

立连接的服务机提供的地址串相同，这台客户机就可以成功加入连接，并称其连接到这

台服务机；如果找不到这样的服务机，则认为这台客户机无法成功加入连接。

请注意，尽管不允许两台不同的服务机使用相同的地址串，但多台客户机使用同样

的地址串，以及同一台服务机同时被多台客户机连接的情况是被允许的。

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

接情况。

第9页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

网络连接（network）

【输入格式】

从文件中读入数据。

第1行，一个正整数n。

接下来n行，每行2个字符串op,ad，按照编号从小到大给出每台计算机的类型

及地址串。

其中op保证为字符串Server或Client之一，ad为一个长度不超过25的，仅

由数字、字符.和字符:组成的非空字符串。

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

【输出格式】

输出到文件中。

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

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

1.如果其提供符合规范的地址串且成功建立连接，输出字符串OK。

2.如果其提供符合规范的地址串，但由于先前有相同地址串的服务机而无法成功

建立连接，输出字符串FAIL。

3.如果其提供的地址串不是符合规范的地址串，输出字符串ERR。

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

1.如果其提供符合规范的地址串且成功加入连接，输出一个正整数表示这台客户

机连接到的服务机的编号。

2.如果其提供符合规范的地址串，但无法成功加入连接时，输出字符串FAIL。

3.如果其提供的地址串不是符合规范的地址串，输出字符串ERR。

【样例1输入】

1

2

3

4

5

6

5

Server192.168.1.1:8080

Server192.168.1.1:8080

Client192.168.1.1:8080

Client192.168.1.1:80

Client192.168.1.1:99999

【样例1输出】

1

2

OK

FAIL

第10页共14页

2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证

网络连接（network）

3

4

5

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

1

2

3

4

5

6

7

8

9

10

11

10

Server192.168.1.1:80

Client192.168.1.1:80

Client192.168.1.1:8080

Server192.168.1.1:80

Server192.168.1.1:8080

Server192.168.1.999:0

Client192.168.1.1.8080

Client192.168.1.1:8080

Client192.168.1.1:80

Client192.168.1.999:0

【样例2输出】

1

2

3

4

5

6

7

OK

1

FAIL

FAIL

OK

ERR

ERR

第11页共14页