0%

CSP2021-J


题目链接:暂无


T1 分糖果

【题目背景】

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

【题目描述】

红太阳幼儿园有 n 个小朋友,你是其中之一。保证 n ≥ 2。
有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们。
由于你只是个平平无奇的幼儿园小朋友,所以你的体力有限,至多只能拿 R 块糖回去。
但是拿的太少不够分的,所以你至少要拿 L 块糖回去。保证 n ≤ L ≤ R。
也就是说,如果你拿了 k 块糖,那么你需要保证 L ≤ k ≤ R。
如果你拿了 k 块糖,你将把这 k 块糖放到篮子里,并要求大家按照如下方案分糖果:只要篮子里有不少于 n 块糖果,幼儿园的所有 n 个小朋友(包括你自己)都从篮子中拿走恰好一块糖,直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。
作为幼儿园高质量小朋友,你希望让作为你搬糖果的奖励的糖果数量(而不是你最后获得的总糖果数量!)尽可能多;因此你需要写一个程序,依次输入 n, L, R, 并输出出你最多能获得多少作为你搬糖果的奖励的糖果数量。

【输入格式】

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

【输出格式】

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

【输入输出样例】

输入 #1
7 16 23
输出 #1
6
输入 #2
10 14 18
输出 #2
8

说明/提示

【样例解释 #1】
拿 k = 20 块糖放入篮子里。
篮子里现在糖果数 20 ≥ n = 7,因此所有小朋友获得一块糖;
篮子里现在糖果数变成 13 ≥ n = 7,因此所有小朋友获得一块糖;
篮子里现在糖果数变成 6 < n = 7,因此这 6 块糖是作为你搬糖果的奖励。
容易发现,你获得的作为你搬糖果的奖励的糖果数量不可能超过 6 块(不然,篮子里的糖果数量最后仍然不少于 n ,需要继续每个小朋友拿一块),因此答案是 6。

【样例解释 #2】
容易发现,当你拿的糖数量 k 满足 14 = L ≤ k ≤ R = 18 时,所有小朋友获得一块糖后,剩下的 k−10 块糖总是作为你搬糖果的奖励的糖果数量,因此拿 k=18 块是最优解,答案是 8。

【数据范围】

【解题思路】

看看n的整数倍是否在[L,R]的区间内,如果是,则取余数最大的时候,即余数为n-1时;
如果不是,则取R件糖果,使得取余后剩下的糖果最多。

【代码部分】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<bits/stdc++.h>
using namespace std;
int main()
{
long long n,l,r;
cin>>n>>l>>r;
long long x,y;
x=l/n;
y=r/n;
if (y>x) {
long long ans=y*n-1;
cout<<ans%n<<endl;
}
if (x==y) {
cout<<r%n<<endl;
}
return 0;
}

T2 插入排序

【题目描述】

插入排序是一种非常常见且简单的排序算法。小 Z 是一名大一的新生,今天 H 老师刚刚在上课的时候讲了插入排序算法。
假设比较两个元素的时间为 O(1),则插入排序可以以 O(n^2) 的时间复杂度完成长度为 n 的数组的排序。不妨假设这 n 个数字分别存储在a1,a2,…,an之中,则如下伪代码给出了插入排序算法的一种最简单的实现方式:
这下面是 C/C++ 的示范代码

1
2
3
4
5
6
7
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 的示范代码

1
2
3
4
5
6
7
8
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 个元素,也就是 ax 的值,修改为 v 。保证 1 ≤ x ≤ n ,1 ≤ v ≤ 109 。注意这种操作会改变数组的元素,修改得到的数组会被保留,也会影响后续的操作。
2 x:这是第二种操作,假设 H 老师按照上面的伪代码对 a 数组进行排序,你需要告诉 H 老师原来 a 的第 x 个元素,也就是 ax,在排序后的新数组所处的位置。保证 1 ≤ x ≤ n 。注意这种操作不会改变数组的元素,排序后的数组不会被保留,也不会影响后续的操作。
H 老师不喜欢过多的修改,所以他保证类型 1 的操作次数不超过 5000 。
小 Z 没有学过计算机竞赛,因此小 Z 并不会做这道题。他找到了你来帮助他解决这个问题。

【输入格式】

第一行,包含两个正整数 n , Q ,表示数组长度和操作次数。
第二行,包含 n 个空格分隔的非负整数,其中第 i 个非负整数表示 ai
接下来 Q 行,每行 2 ∼ 3 个正整数,表示一次操作,操作格式见【题目描述】。

【输出格式】

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

【输入输出样例】

输入 #1
3 4
3 2 1
2 3
1 3 2
2 2
2 3
输出 #1
1
1
2

【说明/提示&数据范围】

T3 网络连接

【题目描述】

TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。
在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机负责加入连接。
需要进行网络连接的计算机共有 n 台,编号为 1 ∼ n ,这些机器将按编号递增的顺序,依次发起一条建立连接或加入连接的操作。
每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址,客户机提供的地址串表示它尝试加入连接的地址。
一个符合规范的地址串应当具有以下特征:
必须形如 a.b.c.d:e 的格式,其中 a , b , c , d , e 均为非负整数;
0 ≤ a , b , c , d ≤ 255 ,0 ≤ e ≤ 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 行,每行两个字符串 op, ad,按照编号从小到大给出每台计算机的类型及地址串。
其中 op 保证为字符串 Server 或 Client 之一,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

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

【数据范围】

【解题思路】

Op保证为Server或者Client之一,那就免去了判错的步骤,我不太会用switch,就直接if分类讨论Op的两种情况。不管是服务机还是客户机,都需要判断两个基本的条件:地址串是否符合规范,先前是否有相同地址串。
地址串是否符合规范的判断,写在主函数中属实有点让人眼花缭乱,所以我把它放在子函数conn(随便取的)中。由于地址串中a,b,c,d,e元素的位数不确定,所以可以视作.和:把五个元素分割开了。把它们强制取出来,同时判断是否有前置0,最后判断每个数字具体大小是否在规定区间内。(程序仍有部分问题,比如输入…:也会显示OK)
先前是否有相同地址串的判断,可以想到STL库中的集合,即set容器。Insert可以在容器内添加元素,count可以用来判断该元素是否在容器内。有了这两个方法,程序就变得容易(无脑)些了。
服务机和客户机的操作略有不同,但大同小异。直接按照题目输出中的逻辑,书写代码即可。有了之前的铺垫,就会好写很多。

【代码部分】

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
69
#include<bits/stdc++.h>
using namespace std;
bool conn(string s)
{
int n=0,a=0,b=0,c=0,d=0,e=0;
if (s[n]=='0'&&s[n+1]!='.') return false;
while (s[n]!='.'&&n<s.length()) {
a=a*10+int(s[n])-48;
n++;
}
n++;
if (s[n]=='0'&&s[n+1]!='.') return false;
while (s[n]!='.'&&n<s.length()) {
b=b*10+int(s[n])-48;
n++;
}
n++;
if (s[n]=='0'&&s[n+1]!='.') return false;
while (s[n]!='.'&&n<s.length()) {
c=c*10+int(s[n])-48;
n++;
}
n++;
if (s[n]=='0'&&s[n+1]!=':') return false;
while (s[n]!=':'&&n<s.length()) {
d=d*10+int(s[n])-48;
n++;
}
n++;
if (s[n]=='0') return false;
for (int i=n;i<s.length();i++) {
e=e*10+int(s[i])-48;
}
if (a>=0&&a<=255&&b>=0&&b<=255&&c>=0&&c<=255&&d>=0&&d<=255&&e>=0&&e<=65535)
return true;
return false;
}
int main()
{
int n;
string op,ad;
set<string> comp;
string ss[1020];
cin>>n;
for (int i=1;i<=n;i++) {
cin>>op>>ad;
bool flag=conn(ad);
if (op=="Server") {
if (flag&&comp.count(ad)==0) {
comp.insert(ad);
ss[i]=ad;
cout<<"OK\n";
}
else if (flag&&comp.count(ad)!=0)
cout<<"FAIL\n";
else if (!flag) cout<<"ERR\n";
}
else if (op=="Client") {
if (flag&&comp.count(ad)!=0) {
for (int j=1;j<=n;j++)
if (ad==ss[j]) cout<<j<<endl;
}
else if (flag&&comp.count(ad)==0)
cout<<"FAIL\n";
else if (!flag) cout<<"ERR\n";
}
}
return 0;
}

T4 小熊的果篮

【题目描述】

小熊的水果店里摆放着一排 n 个水果。每个水果只可能是苹果或桔子,从左到右依次用正整数 1、2、3、……、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 ≤ 5 。
对于 30% 的数据,n ≤ 1000 。
对于 70% 的数据,n ≤ 50000 。
对于 100% 的数据,1 ≤ n ≤ 2 × 105

【解题思路】

首先,因为水果会被挑出,相当于会有数据的删除,所以我们会想到用列表容器来解决这道题目。STL库中有list容器,使用它应该会方便许多。
我定义了a,b两个List。a用来储存水果的种类,b用来储存水果的编号。由于不知道要进行多少次挑水果的操作,所以我用while(1)来开始循环。被挑走的水果具有的特征是与之前相邻一个的水果类型不同。而第一个水果肯定是要被挑走的,所以我们默认第0个水果的种类为-1。将a,b两个链表的迭代器同时遍历,如果元素满足上述条件,就输出,并记录它的位置,等到迭代器到下一个位置时,再将所记录的位置的元素删除。(这是一个坑,如果不等到迭代器到下一个位置,直接删除,会出问题)而我们退出循环的条件就是list容器的元素个数为0。

【代码部分】

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
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x,y;
scanf("%d",&n);
list<int> a;
list<int> b;
list<int>::iterator ita,itb,itaa,itbb;
for (int i=1;i<=n;i++) {
scanf("%d",&x);
a.push_back(x);
b.push_back(i);
}
while (1) {
int fruit=-1;
bool flag=false;
itb=b.begin();
for (ita=a.begin();ita!=a.end();ita++) {
if (flag) {
a.erase(itaa);
b.erase(itbb);
flag=false;
}
if ((*ita)!=fruit) {
fruit=*ita;
printf("%d ",*itb);
itaa=ita; itbb=itb;
flag=true;
}
itb++;
}
if (flag) {
a.erase(itaa);
b.erase(itbb);
flag=false;
}
printf("\n");
if (a.size()<=0) break;
}
return 0;
}
谢谢你,秋刀鱼今天有吃的了!!!