本文篇幅较长,可以通过页面右下角的目录功能快速跳转。
#分糖果
#题面
#题目背景
红太阳幼儿园的小朋友们开始分糖果啦!
#题目描述
红太阳幼儿园有 个小朋友,你是其中之一。保证 。
有一天你在幼儿园的后花园里发现无穷多颗糖果,你打算拿一些糖果回去分给幼儿园的小朋友们。
由于你只是个平平无奇的幼儿园小朋友,所以你的体力有限,至多只能拿 块糖回去。
但是拿的太少不够分的,所以你至少要拿 块糖回去。保证 。
也就是说,如果你拿了 k 块糖,那么你需要保证 。
如果你拿了 k 块糖,你将把这 k 块糖放到篮子里,并要求大家按照如下方案分糖果:只要篮子里有不少于 块糖果,幼儿园的所有 个小朋友(包括你自己)都从篮子中拿走恰好一块糖,直到篮子里的糖数量少于 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励。
作为幼儿园高质量小朋友,你希望让作为你搬糖果的奖励的糖果数量(而不是你最后获得的总糖果数量!)尽可能多;因此你需要写一个程序,依次输入 ,并输出出你最多能获得多少作为你搬糖果的奖励的糖果数量。
#输入格式
输入一行,包含三个正整数 ,分别表示小朋友的个数、糖果数量的下界和上界。
#输出格式
输出一行一个整数,表示你最多能获得的作为你搬糖果的奖励的糖果数量。
#输入输出样例
样例输入 #1
7 16 23
样例输出 #1
6
样例解释 #1
拿 块糖放入篮子里。
篮子里现在糖果数 ,因此所有小朋友获得一块糖;
篮子里现在糖果数变成 ,因此所有小朋友获得一块糖;
篮子里现在糖果数变成 ,因此这 块糖是作为你搬糖果的奖励。
容易发现,你获得的作为你搬糖果的奖励的糖果数量不可能超过 块(不然,篮子里的糖果数量最后仍然不少于 ,需要继续每个小朋友拿一块),因此答案是 。
样例输入 #2
10 14 18
样例输出 #2
8
样例解释 #2
容易发现,当你拿的糖数量 满足 时,所有小朋友获得一块糖后,剩下的 块糖总是作为你搬糖果的奖励的糖果数量,因此拿 块是最优解,答案是 。
#数据范围与约定
测试点 | |||
---|---|---|---|
对于所有数据,保证 。
#思路
此题是一道结论题。
#代码
1 |
|
#网络连接
#题面
#题目描述
TCP/IP 协议是网络通信领域的一项重要协议。今天你的任务,就是尝试利用这个协议,还原一个简化后的网络连接场景。
在本问题中,计算机分为两大类:服务机(Server)和客户机(Client)。服务机负责建立连接,客户机负责加入连接。
需要进行网络连接的计算机共有 台,编号为 ,这些机器将按编号递增的顺序,依次发起一条建立连接或加入连接的操作。
每台机器在尝试建立或加入连接时需要提供一个地址串。服务机提供的地址串表示它尝试建立连接的地址,客户机提供的地址串表示它尝试加入连接的地址。
一个符合规范的地址串应当具有以下特征:
- 必须形如
a.b.c.d:e
的格式,其中 均为非负整数; - , ;
- 均不能含有多余的前导 。
相应地,不符合规范的地址串可能具有以下特征:
- 不是形如
a.b.c.d:e
格式的字符串,例如含有多于 个字符.
或多于 个字符:
等情况; - 整数 中某一个或多个超出上述范围;
- 整数 中某一个或多个含有多余的前导 。
例如,地址串 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
均是不符合规范的。
如果服务机或客户机在发起操作时提供的地址串不符合规范,这条操作将被直接忽略。
在本问题中,我们假定凡是符合上述规范的地址串均可参与正常的连接,你无需考虑每个地址串的实际意义。
由于网络阻塞等原因,不允许两台服务机使用相同的地址串,如果此类现象发生,后一台尝试建立连接的服务机将会无法成功建立连接;除此之外,凡是提供符合规范的地址串的服务机均可成功建立连接。
如果某台提供符合规范的地址的客户机在尝试加入连接时,与先前某台已经成功建立连接的服务机提供的地址串相同,这台客户机就可以成功加入连接,并称其连接到这台服务机;如果找不到这样的服务机,则认为这台客户机无法成功加入连接。
请注意,尽管不允许两台不同的服务机使用相同的地址串,但多台客户机使用同样的地址串,以及同一台服务机同时被多台客户机连接的情况是被允许的。
你的任务很简单:在给出每台计算机的类型以及地址串之后,判断这台计算机的连接情况。
#输入格式
第一行,一个正整数 。
接下来 行,每行两个字符串 ,按照编号从小到大给出每台计算机的类型及地址串。
其中 保证为字符串 Server
或 Client
之一, 为一个长度不超过 的,仅由数字、字符 .
和字符 :
组成的非空字符串。
每行的两个字符串之间用恰好一个空格分隔开,每行的末尾没有多余的空格。
#输出格式
输出共 行,每行一个正整数或字符串表示第 台计算机的连接状态。其中:
如果第 台计算机为服务机,则:
- 如果其提供符合规范的地址串且成功建立连接,输出字符串
OK
。 - 如果其提供符合规范的地址串,但由于先前有相同地址串的服务机而无法成功建立连接,输出字符串
FAIL
。 - 如果其提供的地址串不是符合规范的地址串,输出字符串
ERR
。
如果第 台计算机为客户机,则:
- 如果其提供符合规范的地址串且成功加入连接,输出一个正整数表示这台客户机连接到的服务机的编号。
- 如果其提供符合规范的地址串,但无法成功加入连接时,输出字符串
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
样例解释 #1
计算机 为服务机,提供符合规范的地址串 192.168.1.1:8080
,成功建立连接;
计算机 为服务机,提供与计算机 相同的地址串,未能成功建立连接;
计算机 为客户机,提供符合规范的地址串 192.168.1.1:8080
,成功加入连接,并连接到服务机 ;
计算机 为客户机,提供符合规范的地址串 192.168.1.1:80
,找不到服务机与其连接;
计算机 为客户机,提供的地址串 192.168.1.1:99999
不符合规范。
样例输入 #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 2 3 | ||
性质 1 2 | ||
性质 1 | ||
性质 2 | ||
性质 4 | ||
性质 5 | ||
无特殊性质 |
性质 1:保证所有的地址串均符合规范;
性质 2:保证对于任意两台不同的计算机,如果它们同为服务机或者同为客户机,则它们提供的地址串一定不同;
性质 3:保证任意一台服务机的编号都小于所有的客户机;
性质 4:保证所有的地址串均形如 a.b.c.d:e
的格式,其中 均为不超过 且不含有多余前导 的非负整数;
性质 5:保证所有的地址串均形如 a.b.c.d:e
的格式,其中 均为只含有数字的非空字符串。
对于 的数据,保证 。
#思路
细节稍多的模拟题。
先按照题意检查读入的地址串是否合法,如果合法则继续操作,使用 map 记录即可。
#代码
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
样例解释 #1
所有水果一开始的情况是 ,一共有 个块。
在第一次挑水果组成果篮的过程中,编号为 的水果被挑了出来。
之后剩下的水果是 ,一共 个块。
在第二次挑水果组成果篮的过程中,编号为 的水果被挑了出来。
之后剩下的水果是 ,只有 个块。
在第三次挑水果组成果篮的过程中,编号为 的水果被挑了出来。
最后剩下的水果是 ,只有 个块。
在第四次挑水果组成果篮的过程中,编号为 的水果被挑了出来。
样例输入 #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
#数据范围与约定
对于 的数据,。
对于 的数据,。
对于 的数据,。
对于 的数据,。
提示:由于数据规模较大,建议 C/C++ 选手使用 scanf
和 printf
语句输入、输出。
#思路
分块储存,使用队列维护并进行模拟。
在队列中相邻两块可以合并成一块进行处理。
#代码
1 |
|