秋刀鱼的博客
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;
}
谢谢你，秋刀鱼今天有吃的了！！！