湖南大学2021程序设计训练笔记 – 作业训练2

本文最后更新于 693 天前，其中的信息可能已经有所发展或是发生改变。

所有代码均已上传至 homework/CSP-Training at master · cyp0633/homework (github.com)。不保证代码均正确，正确的也不保证为最优解，可以查看 Commit 详情进一步了解。

1.字符串反转2

个人难度评级：2

问题描述

给定一个句子（只包含字母和空格），将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。比如： “hello xiao mi”-> “mi xiao hello”

输入形式

输入数据有多组，每组占一行，包含一个句子(句子长度小于1000个字符)

输出形式

对于每个测试示例，要求输出句子中单词反转后形成的句子

样例输入

hello xiao mi
I am a student

样例输出

mi xiao hello
student a am I

解题思路

对于每一行，逐个输入单词压入栈，cin.peek到回车或者文件末尾（用EOF表示，可以用^Z触发）就全部输出，因为输入内容最后没有回车，只判断回车是会WA掉大部分点的。

2. 487-3279

来源：UVa 696 测试数据可能不同

个人难度评级：2

问题描述

每个人都喜欢有令人难忘的电话号码。要想让电话号码变得令人难忘的一种方法是拼出一个令人难忘的单词或短语。例如，你可以拨打滑铁卢大学的电话，拨打令人难忘的电话号码TUT-GLOP。

有时只有一部分号码被用来拼写一个单词，例如，你可以拨打310-gino从Gino’s订购披萨。

要使电话号码令人难忘的另一种方法是以一种令人难忘的方式对数字进行分组。你可以从比萨饼小屋中订购比萨饼，方法是拨打他们的“3个10”，即号码3-10-10-10。

电话号码的标准格式是七位的十进制数字，第三和第四位之间包含连字符（例如888-1200）。电话的键盘提供字母到数字的映射，如下所示：

A, B, C映射到2

D, E, F映射到3

G, H, I映射到4

J, K, L映射到5

M, N, O映射到6

P, R, S映射到7

T, U, V映射到8

W, X, Y映射到9

Q和Z没有映射。连接符不拨号，必要时可加上或去除。TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。

当两个电话号码有相同的标准格式时是等价的（拨同样的号码）。

你的公司正在编制本地企业的电话号码目录，作为质量控制的一部分，你需要检查没有两个（或多个）企业具有相同的电话号码。

输入形式

输入包括一个案例。输入的第一行为一个正整数，指定目录中电话号码的数目(最多100，000)。其余的各行列出目录中的电话号码，每个号码单独占一行。每个电话号码都是一个由十进制数字、大写字母(不包括Q和z)和连字符组成的字符串。字符串中的七个字符或是数字或是字母。

输出形式

对于出现超过一次的每个号码，按照标准格式每个输出一行，然后是空格，接着输出出现的次数。只出现1次的电话号码不输出。

样例输入

12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279

样例输出

310-1010 2
487-3279 4
888-4567 3

解题思路

将每个电话号码转换成int之后存储，sort一遍，然后加上横线再输出重复出现的电话号码和次数即可。

3.缺席考试的是谁？

个人难度评级：2

问题描述

程序设计考试结束了，传来个不好的消息：有一个学生没参加考试!需要尽快知道缺席考试的人是谁，以便尽快做出处理。

糟糕的是，尽管有签到表，但由于人数较多，签到情况比较混乱：有的签到表签在一张白纸上，有的虽然签在名册上，但并不是签在自己姓名旁，更有学生签到了别的签到表上……

现在只能根据这2n-1个姓名（名册上有n个学生姓名，签到有n-1个姓名，签到姓名和名册姓名可能混在一起了），来找到缺席考试的人是谁。唯一一个有利的条件是所有参加考试的人都签了名，且只签一次，签名也都正确无误。

现在任务交给你：编写一个程序，找出缺席考试的是谁。

输入形式

有多组测试数据。

每组测试数据开始一行，是一个正整数n，表示总人数，n=0意味着输入结束并且不需要处理。

以下2n-1行，每行一个字符串，长度不超过20，表示一个人的姓名。姓名有大小写的英文字母、常用汉字组成(注意每个汉字占2个字节，中英文姓名都不排除有重名情况)。

40%的测试数据1 ≤ n≤ 10；

30%的测试数据1 ≤ n≤ 100；

20%的测试数据1 ≤ n≤ 10³；

10%的测试数据1 ≤ n≤ 10⁴；

提示：大量输入数据，C/C++输入推荐使用scanf函数

输出形式

对于每组测试数据，输出一行，只包含一个字符串，表示缺席的人的姓名。

样例输入

2
张三
张三
李四
0

样例输出

李四

解题思路

这个题很蛋疼的两个地方是：

不排除有重名的情况，所以不能简单地用bool存储是否签到2次；
签到姓名和名册姓名混在了一起，所以不能采取”先存后删”的策略。

但是有一点不会变：没来的人，他的名字出现次数是奇数（因为缺且仅缺了一次）。所以我建立一个pair<string,int>数组，first存放姓名，second存放名字出现次数。直接读入2n-1行，统计每个名字出现次数，那么出现了奇数次的名字一定存在缺考情况。

中文应该不需要特殊考虑。但如果你用getline函数读取名字，记得也要用getline吸收cin读取n后的回车！用getchar会WA掉。

4.电话号码

来源：CodeForces 898C

个人难度评级：3

问题描述

Vasya有几本电话簿，记录了他的朋友们的电话号码，每一个朋友都可以有一或几个电话号码。

Vasya决定整理关于朋友电话号码的信息。给定n个字符串，来自于Vasya的电话簿中的条目。每一条都以朋友的姓名开头，然后跟着当前条目中的电话号码个数，然后是本人的电话号码。有可能几个相同的电话被记录在同一个记录中。

Vasya还认为，如果电话号码a是电话号码b的后缀（也就是说，号码b以a结尾），这两个号码被当作同一个电话号码，那么a被认为是无城市代码，它不应该被考虑。

输出整理后Vasya朋友的电话号码信息。有可能两个不同的人有相同的号码。如果一个人有两个电话号码x和y，x是y的后缀（即y以x结尾），则不输出x。

如果Vasya的电话簿中的某些朋友记录了几次，那么只需要记录一次。

输入形式

输入第一行一个整数n(1<=n<=20)，Vasya的电话簿上的条目数。

以下n行后面是描述中的格式记录。朋友的姓名中不包含空字符，长度不超过10位，由小写英文字母组成。电话号码个数在1~10之间。每个电话号码的长度范围在1~10之间，可以包含前导0。

输出形式

输出Vasya的朋友的电话号码的有序信息。首先输出电话簿中的朋友数目m。

接下来的m行，包含以格式“姓名电话号码个数电话号码1 … 电话号码k”的条目，号码间以空格分隔。每个记录包含当前朋友的所有电话号码。

每个条目输出按照姓名字母序进行排序，电话号码按照从小到大的顺序排列（注意电话号码比较规则：”1″<“01″、”12″<“012″，依此类推）

样例输入

4
ivan 3 123 123 456
ivan 2 456 456
ivan 8 789 3 23 6 56 9 89 2
dasha 2 23 789

样例输出

2
dasha 2 23 789
ivan 4 2 123 456 789

解题思路

定义一个结构体，内含名字、此人的电话数目和一个电话号码数组（字符串类型）。

注意人名有重复，同样的人名要加到一起去；电话号码有后缀情况，要逐个比对，可以考虑善用substr函数。

然后是两层排序，人名和电话号码的排序。注意电话号码不能简单使用std::string重载运算符，短的电话号码被看作小的。

注意所有（最多20）个人名实际上可以都是一个人，再加上每个人名条目都最多10个号码，要过CodeForces的样例，需要把电话号码的数组开大点，不过CG上的样例非常宽松。

5.点球大战

个人难度评级：1

问题描述

在足球比赛中，有不少赛事，例如世界杯淘汰赛和欧洲冠军联赛淘汰赛中，当比赛双方经过正规比赛和加时赛之后仍然不分胜负时，需要进行点球大战来决定谁能够获得最终的胜利。点球大战的规则非常简单，两方轮流派出球员罚点球，每方各罚5个。当5轮点球结束以后如果仍然不分胜负，则进入一轮定胜负的阶段。两方各派一名球员罚点球，直到有一方罚进而另一方没有进为止。
在北美职业冰球联赛中，也有点球大战。与足球的规则不同的是，它只先罚3轮点球，随后就进入一轮定胜负的阶段，而其他的规则完全一样。
在本题中，输入将给出每次点球是否罚进，而你的任务则是输出一个“比分板”。

输入形式

输入包含多组数据。每组数据的第一行包含一个整数N(1<=N<=18)，表示双方总共罚了多少个点球，N=0表示输入结束。随后有N行，每行是一个如下形式的字符串：
XXXX good：表示这个点球罚进
或者XXXX no good：表示这个点球没有罚进
其中XXXX表示球员名字（全部由字母和空格组成，保证不会出现歧义）
每一行保证不超过100个字符。
XXXX和good以及XXXX和no、no和good之间保证有且只有1个空格。
good、no good都是小写。本题是大小写相关的。
数据不保证点球大战一定结束，也不保证在结束以后立即结束这组数据（即：不用判断点球大战是否结束，只用把罚进的点球往比分上加即可）。

输出形式

对每组数据，输出一个比分板。一个点球如果罚进，则在对应的地方标上’O’，如果没有进则标上’X’。先罚球的队伍的信息在上面，后罚的在下面。最右边标上两队的比分。具体格式参考样例输出。注意如果一轮点球只罚了一个，则后面那个点球对应的地方写上’-’。

样例输入

6
Riise good
Ballack good
Gerrard no good
Lampard no good
Fernando Torres good
Malouda good
9
Christiano Ronaldo no good
Messi no good
Giggs good
Abidal no good
Carrick good
Ronaldinho good
Rooney good
Henry no good
Tevez good
0

样例输出

1 2 3 Score
O X O 2
O X O 2
1 2 3 4 5 Score
X O O O O 4
X X O X - 1

解题思路

如果你知道了string的find函数，那么这个题非常简单，我觉得不需要说思路。

6.飞行棋

来源：HDU 2240（很可能无法访问）

个人难度评级：2

问题描述

       大家当年一定都下过飞行棋吧。现在Lele和Yueyue要下的棋和这个很相似，只是更简单一点而已。

       棋盘由N个格子组成，分别标记为第0格到第N-1格。格子分为两种，一种是普通格子，即表示在该格可以停留。否则是特殊的格子，一旦走到上面，就要根据上面标记的数飞到相应的格子上。如果飞到一个特殊的格子上，则可以继续飞。

       除了第0格外，其他格子都只能容纳一个玩家。即一旦A玩家已经在某个格子上，B玩家又走到这里，A玩家则会被踢回第0格，而B玩家留在这个格子上面。

       第N-1个格子是终点，一旦一个玩家走到这个格子上，该玩家获胜，游戏结束。

       刚刚开始时，两个玩家都站在第0格上，依次扔骰子，根据骰子显示的点数走相应的格子数。比如，玩家在第0格，扔出了5点，则会走到第5个格子上。如果玩家走得超出了棋盘的范围，则要往回走一定的步数。比如，棋盘一共有7(0~6)个格子,玩家在第4格上，扔出了6点，最终他会走到第2格上(4->5->6->5->4->3->2)。

       根据观察，骰子扔出来的数也是有规律的。
       对于每一盘棋，扔出的第一个点数为 F0=(A*C+B)%6+1,第二个点数为 F1=(A*F0+B)%6+1,第三个点数为 F2=(A*F1+B)%6+1 ….依此类推。

       每一盘棋都是由Lele先走，现在就请你当裁判，看谁能获胜。

输入形式

      本题目包含多组测试，请处理到文件结束。
      每组数据占两行。
      第一行有4个整数N,A,B,C(含义见题目描述，6<N<200,0<=A,B,C<=2^31)。
      第二行有N个字符串，分别表示棋盘上第0个到第N-1个格子的内容。两个字符串之间用一个空格分隔开。

      如果字符串为”N”,则表示这个格子为普通格子。否则字符串为”GX”(X为0到N-1之间的整数)的形式，其中X表示玩家走到这个格子时，要马上飞到第X个格子。
      数据保证第0个和第N-1个格子一定为”N”。

输出形式

对于每组数据，在一行内输出结果。
如果Lele能赢这盘棋，则输出”Lele”,如果Yueyue赢的话，就输出”Yueyue”。

样例输入

7 1 0 6
N G3 N N N N N
7 1 0 6
N G4 N N N N N

样例输出

Lele
Yueyue

样例说明

测试用例保证能有确定结果。

解题思路

模拟就完事了，模拟每一步的走法即可。原题是有是否进行不完的判断的，如果有余力可以思考一下。

7.棋盘

问题描述

棋盘是指一个行和列编号从1~N的NxN的二进制矩阵，当行号和列号之和为偶数时该矩阵对应位置为黑色的(1)，否则为白色的(0)。以下图示为N=1、2、3时的棋盘。

給出一个NxN的二进制矩阵，请找出位于该矩阵内的最大尺寸的完整棋盘，以及最大尺寸棋盘的数量（棋盘可以交叠）。

输入形式

每个测试用例的第一行是一个正整数N(1<=N<=2000)，表示給定矩阵的行数和列数，接下来的N行描述了这个矩阵：每行有N个字符，既可以是“1”（代表黑块），也可以是“0”（代表白块）。矩阵至少包含一个“1”字符。

输出形式

输出最大尺寸棋盘的行列的大小，以及最大棋盘的个数，以空格分隔。

样例输入

样例输出

3 3

解题思路

棋盘用bool二维数组存储即可，反正只有0和1两种值。

枚举棋盘左上角起始点，不是黑的直接跳过。对于黑，先得出一个边长上限，就是起始点距离右边和下边的距离最小值。然后枚举边长，大可以先从2开始，毕竟起始点本身是黑的就一定是个棋盘。由于每次增加边长，相比上一个边长增加的只有最右边和最下边一条，所以在上个边长能够成立的情况下，只需要检查新增加的两条边是否合理即可；相反，不能成立的话，直接break即可，边长小的都不成立那大的更不行了。

验证颜色是否正确的时候，需要注意“当行号和列号之和为偶数时“中求和时，以验证中的棋盘起始点作为原点，而真正使用的坐标是以整个大棋盘的(0,0)作为原点。看不懂的话，建议直接去翻我代码……

8 .Engine

来源：HDU 2532（若无法访问，可以看Vjudge）

个人难度评级：3

问题描述

谷歌、百度等搜索引擎已经成为了互连网中不可或缺的一部分。在本题中，你的任务也是设计一个搜索论文的搜索引擎，当然，本题的要求比起实际的需求要少了许多。
本题的输入将首先给出一系列的论文，对于每篇论文首先给出标题，然后给出它被引用的次数。然后会有一系列的搜索询问，询问标题中包含特定关键词的论文有哪些。
每一个询问可能包含多个关键词，你需要找出标题包含所有关键词的论文。
“包含”必须是标题中有一个词正好是给定的关键词，不区分大小写。
对每个询问，都按被引用的次数从多到少输出满足条件的论文的标题。如果有被引用的次数相同的论文，则按照论文在输入中的顺序排列，先给出的论文排在前面。

输入形式

输入包含多组数据。
每组数据首先有一行包含一个整数N(1<=N<=1000)，表示论文的数目，N=0表示输入结束。每组论文的信息第一行是论文的标题，由字母（大小写均可）和空格组成，不超过10个词，每个词不超过20个字符，标题总共不超过250个字符。第二行是一个整数K(0<=K<=108)，表示它被引用的次数。在论文信息结束以后，有一行包含一个整数M(1<=M<=100)，表示询问的数目。接下来有M行，每行是一个询问，由L(1<=L<=10)个空格分开的词构成，每个词不超过20个字符。

输出形式

对每个询问，按照题目给定的顺序输出满足条件的论文的标题；如果没有满足条件的论文，就不输出。在每组询问的输出之后输出一行“***”，在每组数据的输出之后输出一行“—”。

样例输入1

6
Finding the Shortest Path
120
Finding the k Shortest Path
80
Find Augmenting Path in General Graph
80
Matching in Bipartite Graph
200
Finding kth Shortest Path
50
Graph Theory and its Applications
40
6
shortest path
k shortest path
graph
path
find
application
0

样例输出1

Finding the Shortest Path
Finding the k Shortest Path
Finding kth Shortest Path
***
Finding the k Shortest Path
***
Matching in Bipartite Graph
Find Augmenting Path in General Graph
Graph Theory and its Applications
***
Finding the Shortest Path
Finding the k Shortest Path
Find Augmenting Path in General Graph
Finding kth Shortest Path
***
Find Augmenting Path in General Graph
***
***
---

样例输入2

1
Finding the Shortest Path
120
2
Path

Pat
0

样例输出2

Finding the Shortest Path
***
***
---

解题思路

首先要说明的是，样例2原题里是没有的，而个人认为中间的空行是多余的，删掉之后才能得到期望输出。

这题就是个大模拟，思路其实不是很难找，但是要写好还是很费精力和时间的。

我定义了一个paper类，包含名字、关键词数组、关键词个数和引用次数，还包含一个成员函数，负责将名字转换成关键字。所有的这些都是public。分隔符是空格，那么使用字符串流来转换很方便，只需要调用自行实现的全部转小写的函数将名字转换后推入流，再一个个推出即可。

比对关键字的时候，查找的关键字要全部在某一文献的关键字列表里，才能算找到了合适的结果，不能够使用string的find()成员函数查找子串。

将论文全部输入之后直接使用stable_sort和自定义比较函数排序，就不需要找到符合条件的论文之后存储起来再排序了。

此题数据特别多，要格外注意各数据的初始化问题！

9.字符串压缩

来源：Codeforces 1120C

个人难度评级：6

问题描述

给定一个由n个小写字母组成的字符串s，需要使用最少数量的钱币来压缩它。

压缩该字符串，必须将s表示为多个相互连接的非空字符串: s=t₁t₂…t_k，其中第 i 个字符串按照下列两种方法之一编码：

如果|t_i|=1，也就是说 t_i为单个字符组成的字符串，编码时需要支付a个钱币
如果t_i是t₁t₂…t_i-1的子串，编码时需要支付b个钱币

你的任务是计算压缩给定的字符串需要花费的最小钱币数。

输入形式

输入的第一行包含3个用空格分隔的正整数：n、a和b(1≤n、a、b≤5000)，第二行为一个长度为n的小写字符串。

输出形式

输出一个整数，表示你需要为压缩s所需要支付的最小钱币数。

样例输入1

3 3 1
aba

样例输出1

样例输入2

4 1 1
abcd

样例输出2

样例输入3

4 10 1
aaaa

样例输出3

解题思路

不会，DP题谁会做谁做去。

10.拼写检查

来源：POJ 1035

个人难度评级：2

问题描述

       作为一个新的拼写检查程序开发团队的成员，您将编写一个模块，用已知的所有形式正确的词典来检查给定单词的正确性。
       如果字典中没有这个词，那么可以用下列操作中的一个来替换正确的单词（从字典中）：
       1. 从单词中删除一个字母；
       2. 用一个任意字母替换单词中的一个字母；
       3. 在单词中插入一个任意字母。
       你的任务是编写一个程序，为每个给定的单词找到字典中所有可能的替换。

输入形式

输入的第一部分包含所有字典中的词，每个单词占用一行，以一个单一字符“#”作为结束。所有单词都不相同，字典中至多1000个单词。

接下来的部分包含所有需要进行检查的单词，同样每个单词占用一行。这部分也以一个单一字符“#”作为结束。至多有50个单词需要检查。

在输入中所有的单词（字典中的和需要检查的）都仅由小写字母组成，每个最多包含15个字符。

输出形式

对于每个在输入中出现的单词，按照它们在输入的第二部分出现的顺序输出一行。如果该单词是正确的（也就是说它包含在字典中）则输出信息：“is correct”；如果该单词不正确，则首先输出该单词，然后输入符号’:’（冒号），之后空一格，写出它所有可能的替代，以空格分隔。这些替代的单词按照它们在字典中（输入的第一部分）出现的顺序写出。如果没有可替代的单词，则在冒号后面直接输出换行。

样例输入

i
is
has
have
be
my
more
contest
me
too
if
award
#
me
aware
m
contest
hav
oo
or
i
fi
mre
#

样例输出

me is correct
aware: award
m: i my me
contest is correct
hav: has have
oo: too
or:
i is correct
fi: i
mre: more me

解题思路

先把字典中的词语存到数组里，然后再逐个询问比对即可。难点在于删除和增加字母的检查。增删字母的判断函数可以共用，只需将函数的两个参数对调即可。修改的要求是长度相同，而增删的长度差只能为1。

11.最小的k个数

个人难度评级：1

问题描述

输入n个整数，找出其中最小的k（k<=n）个不同数。例如输入4,5,1,6,1,7,3,8这8个数字，则最小的4个数字是1,3,4,5。

输入形式

每个测试案例包括2行：

第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。

第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。

输出形式

对应每个测试案例，输出最小的k个数，并按从小到大顺序打印(如果不存在k个不同的数，则按照实际数量进行输出)。

样例输入

8 4
4 5 1 6 2 7 3 8

样例输出

1 2 3 4

训练提示

1、数的范围从0到1000000000，使用数组记录那些数出现过就不是太合适

2、需要去除重复的数，需要从小到大排序—-set就是一个不错的选择

解题思路

没必要专门去重，更没必要用什么set，直接存数组sort一遍过。只需要检查上一个数是否与要输出的数相等，相等即跳过，就顺便完成了去重。

12.绩点计算

个人难度评级：1

问题描述

学校对本科生的成绩施行绩点制（GPA）。将学生的实际考分根据不同学科的不同学分按一定的公式进行计算。规定如下：

实际成绩绩点

90-100 4.0

85-89 3.7

82-84 3.3

78-81 3.0

75-77 2.7

72-74 2.3

68-71 2.0

64-67 1.5

60-63 1.0

60以下 0

1. 一门课程的学分绩点=该课绩点*该课学分

2. 总评绩点=所有学科绩点之和/所有课程学分之和

现要求你编程求出某人的总评绩点(GPA)

输入形式

第一行总的课程数n

第二行相应课程的学分（两个学分间用空格隔开）

第三行对应课程的实际得分

此处输入的所有数字均为整数

输出形式

输出有一行，总评绩点，保留两位小数

样例输入

5
4 3 4 2 3
91 88 72 69 56

样例输出

2.52

解题思路

不讲了，太简单。

要是得绩点也能像这道题这么简单就好了。

13. xxx定律

个人难度评级：1

问题描述

对于一个正整数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成 3*n+ 1后砍掉一半，直到该数变为1为止。
请计算需要经过几步才能将n变到1，具体可见样例。

输入形式

测试包含多个用例，每个用例包含一个整数n,当n为0 时表示输入结束。（1<=n<=10000）

输出形式

对于每组测试用例请输出一个数，表示需要经过的步数,每组输出占一行。

样例输入

3
2
0

样例输出

5
1

解题思路

太水了……这题我连打表都懒得打。

14.数的距离差

个人难度评级：1

问题描述

给定一组正整数，其中最大值和最小值分别为Max和Min, 其中一个数x到Max和Min的距离差定义为：

$ \left| \left| x-Max \right| -(x-Min) \right| $

其中abs()为求一个数的绝对值

输入形式

包括两行，第一行一个数n，表示第二行有n个正整数

输出形式

输出一个数x，该数在所有n个数中的距离差最小；如果有两个数的距离差都是最小，输出较小的哪个

样例输入1

5
3 1 7 5 9

样例输出1

样例输入2

3
1 3 2

样例输出2

解题思路

没啥难的，录进来sort一遍，逐个算距离差再比较即可。

有一个不成熟的猜想：距离差最小的，并不是中位数，而是与绝对值相差最小的数。

15.亲和数

来源：HDU 2040（无法访问请看Vjudge或者Wayback Machine）

个人难度评级：1

问题描述

古希腊数学家毕达哥拉斯在自然数研究中发现，220 的所有真约数(即不是自身的约数)之和为：

$ 1+2+4+5+10+11+20+22+44+55+110＝284 $

而 284 的所有真约数为 1、2、4、71、 142，加起来恰好为 220。人们对这样的数感到很惊奇，并称之为亲和数。一般地讲，如果两个数中任何一个数都是另一个数的真约数之和，则这两个数就是亲和数。
你的任务就编写一个程序，判断给定的两个数是否是亲和数。

输入形式

输入若干行数据（大于0），每行一个实例,包含两个整数A,B；其中 0 <= A,B <= 600000 ;

输出形式

对于每个测试实例，如果 A 和 B 是亲和数的话输出 YES，否则输出 NO

样例输入

220 284
100 200

样例输出

YES
NO

解题思路

没啥难的，不说了

16.金币

来源：NOIP 2015 普及组第一题（数据已加强）~~（卧槽竟然是NOIP的题……要不是当年我做过我还真想不到）~~

个人难度评级：2

问题描述

国王为他的忠诚的骑士支付金币。在他服役的第一天，骑士收到一枚金币。在接下来2天（第二天和第三天的服务），骑士每天收到2金币。在未来三天（第五，第四，和第六天的服务），骑士每天收到三金币。在未来四天（第七，第八，第九，和第十天的服务），骑士每天收到四金币。这一模式的付款方式将继续下去：在接下来的n天骑士每天将收到n枚金币，而在接接下来的n+1天每天将收到n+1枚金币，这里n是正整数。你的程序将确定在任何给定的天数（从第1天开始）支付给骑士的金币总数。

输入形式

输入包含至少一行，但不超过21行。输入的每一行包含一个测试案例的数据，即一个整数（1~10000），代表天数。

输出形式

每一行输出对应一个测试用例，由天数和支付给骑士的金币总数量组成，中间用空格分隔。

样例输入

样例输出

10 30
6 14
10000 942820
1000 29820
21 91
22 98

解题思路

就是个模拟题，按照题意模拟下去即可，不需要花里胡哨的方法即可解决。

17.小A的计算器

个人难度评级：1

问题描述

以往的操作系统内部的数据表示都是二进制方式，小A新写了一个操作系统，系统内部的数据表示为26进制，其中0-25分别由a-z表示。
现在小A要在这个操作系统上实现一个计算器，这个计算器要能实现26进制数的加法运算。你能帮小A实现这个计算器吗？

输入形式

输入的第一行包括一个整数N(1<=N<=100)。
接下来的N行每行包括两个26进制数x和y，它们之间用空格隔开，每个数的位数最多为10位,我们可以保证相加的结果的位数最多也是10位。每个数会用小A所设计的操作系统中的表示方法来表示，如：bsadfasdf。即每个数的各个位均由26个小写字母a-z中的一个来表示。

输出形式

输出x和y相加后的结果，结果也要用题目中描述的26进制数来表示。

样例输入

4
ba cd
c b
b c
ba c

样例输出

dd
d
d
bc

解题思路

高精度加法+进制转换。

先用string输入，然后将每一位转换为十进制数之后倒序导入vector存储。位数不足的记得补0。设置一个进位的临时数组，然后按照竖式计算方法计算，之后再转换回26进制倒序导入string输出。

18.小丑排序

来源：ACM/ICPC 2004（贝勒大学原题面存档）

个人难度评级：1

问题描述

你在信天翁马戏团（是的，它是由一群小丑组成）从事管理工作，你刚刚写完一个程序的输出是将他们的姓名按长度为非递减的方式排列，名称列表（使每名至少只要它之前的）。然而，你的老板不喜欢这种输出方式，而是希望输出出现更对称，较短的字符串在顶部和底部，而较长的字符串在中间。他的规则是，每一对名称都是在该列表的相对的两端，并且在该组中的第一个名字总是在列表的顶部。比如在下面的第一个例子中，Bo和Pat是第一对，Jean和Kevin是第二对，等等。

输入形式

输入由1到多个字符串集合组成，最后一行为0表示输入结束，每个集合开始于一个整数n，表示该集合字符串的个数，接下来n行由n个字符串按长度非递减的方式排列，每个集合至少包含一个但不超过15个字符串，每个字符串不超过25个字符。

输出形式

对于每个集合，第一行输出”set-n”, n从1开始，接下来的若干行对应输入每个集合重新排列的结果，如样例所示。

样例输入

7
Bo
Pat
Jean
Kevin
Claude
William
Marybeth
6
Jim
Ben
Zoe
Joey
Frederick
Annabelle
5
John
Bill
Fran
Stan
Cece
0

样例输出

set-1
Bo
Jean
Claude
Marybeth
William
Kevin
Pat
set-2
Jim
Zoe
Frederick
Annabelle
Joey
Ben
set-3
John
Fran
Cece
Stan
Bill

解题思路

看不懂题面？哦上帝，这该死的翻译，我真想用隔壁约翰叔叔的靴子狠狠踢他的屁股！说真的，这直译还不如看英文原版。

这不是排序题，题目顺序已经排好了！只要隔一个压一个栈，剩下的原样输出即可。

19.数圈

个人难度评级：1

问题描述

以1为中心，用2,3,4, …, n, …, n*n的数字围绕着中心输出数圈，如若n=4，则

7 8 9 10

6 1 2 11

5 4 3 12

16 15 14 13

输入形式

一个整数n(1<=n<=10)

输出形式

数圈矩阵

样例输入

样例输出

21 22 23 24 25
20 7 8 9 10
19 6 1 2 11
18 5 4 3 12
17 16 15 14 13

解题思路

打表专用题，这题打表不光评测的时候输出快，而且写代码也又快又省力，我觉得打表才是这题的正解（逃）。

每个n对应的圈，实际上都可以看作n=10的子圈，所以把n=10的情况打成表如下，然后再记录每个n要把哪一块切下来输出即可。附上完整数表：

int numCircle[10][10] = {
    {73, 74, 75, 76, 77, 78, 79, 80, 81, 82},
    {72, 43, 44, 45, 46, 47, 48, 49, 50, 83},
    {71, 42, 21, 22, 23, 24, 25, 26, 51, 84},
    {70, 41, 20, 7, 8, 9, 10, 27, 52, 85},
    {69, 40, 19, 6, 1, 2, 11, 28, 53, 86},
    {68, 39, 18, 5, 4, 3, 12, 29, 54, 87},
    {67, 38, 17, 16, 15, 14, 13, 30, 55, 88},
    {66, 37, 36, 35, 34, 33, 32, 31, 56, 89},
    {65, 64, 63, 62, 61, 60, 59, 58, 57, 90},
    {100, 99, 98, 97, 96, 95, 94, 93, 92, 91}};

20.锤子剪刀布

个人难度评级：1

问题描述

大家应该都会玩“锤子剪刀布”的游戏。现给出两人的交锋记录，请统计双方的胜、平、负次数，并且给出双方分别出什么手势的胜算最大。

输入形式

输入第1行给出正整数N（<=10⁵），即双方交锋的次数。随后N行，每行给出一次交锋的信息，即甲、乙双方同时给出的的手势。C代表“锤子”、J代表“剪刀”、B代表“布”，第1个字母代表甲方，第2个代表乙方，中间有1个空格。

输出形式

输出第1、2行分别给出甲、乙的胜、平、负次数，数字间以1个空格分隔。第3行给出两个字母，分别代表甲、乙获胜次数最多的手势，中间有1个空格。如果解不唯一，则输出按字母序最小的解。

样例输入

10
C J
J B
C B
B B
B C
C C
C B
J B
B C
J J

样例输出

5 3 2
2 3 5
B B

解题思路

这种水题挺讨厌的，完全没难度，但很占用时间（我写了1.7KiB，有这时间干啥不好？）。

21.新型冠状病毒（COVID19）传播

个人难度评级：4

问题描述

在以习近平同志为核心的党中央的正确领导下，我国新冠疫情得到了有效控制。防控新冠病毒，必须时刻引起大家的足够重视，特别是人员集中活动场所，保持好社交距离。

然而，在大洋彼岸的 M 国，人们对COVID19并未引起足够重视，他们的领导人川建国同志甚至对居家隔离、戴口罩以及保持社交距离等措施非常不屑，该国疫情已经完全失控。

在一个风景秀丽的小镇，一天早上，有 N 名晨跑爱好者（编号 1 ～ N ）沿着优雅的江边景观道朝同一方向进行晨跑，第 i 名跑者从位置 S_i 处起跑，且其速度为 V_i。换句话说，对所有的实数 t ≥ 0，在时刻 t 时第 i 名跑者的位置为 S_i + V_i ·t。

很不幸的是，其中一名跑者在 t = 0 的时刻感染了病毒，且是无症状感染者，这种病毒只会在同一时刻处在同一位置的跑者之间传播，新感染了病毒的跑者也会感染其他人，很显然，等待足够长的时间，那么病毒会感染一些特定的跑者。

事后发现其中有一名跑者感染了新冠病毒，如果此人就是在 t = 0 时刻的那名感染者，那么，在 N 名晨跑爱好者中会有多少人感染新冠病毒？

输入形式

输入包含三行：

第一行包含为两个整数 N 和 K，分别表示运动员的人数以及开始时感染了病毒的跑者编号。
第二行包含 N 个正整数 S₁、S_2、…、S_N，用空格隔开，分别表示跑者的起始位置。
第三行包含 N 个正整数 V_1、V_2、…、V_N，用空格隔开，分别表示跑者的速度。

输出形式

输出为一个整数，表示最终被感染人数。

样例输入

6 3
3 9 8 5 7 5
6 6 5 4 6 3

样例输出

评分标准

对于50%的评测用例，0< K≤ N ≤10²

对于70%的评测用例，0< K ≤ N ≤10⁴

对于90%的评测用例，0< K ≤ N ≤10⁶

对于100%的评测用例，0< K ≤ N ≤10⁷

详细题解

这题似乎有点意思，是道自创题，值得好好说一说。不过由于本人数学过于弱鸡，这里并没有严格的数学证明。

起初的想法是，对于每一个人的行动路线，可以画出一条一次函数y_i=s_i+v_i*t。只要遍历一遍其他跑者，与被感染者直线在y轴右侧会相交（下文”相交“均指y轴右侧）的，就是被感染的人，是一个O(n)的算法。因为相遇距离设定可以是无限远，所以不能枚举距离模拟跑的过程。得了20分。

核心是用下面的函数判断两条直线是否相交，也就是是否会被感染。Pos指的是初始位置，也就是y轴截距，而Speed代表速度，也就是斜率。

bool checkInfection(const int &sourcePos, const int &sourceSpeed, const int &targetPos, const int &targetSpeed)
{
    if ((sourcePos > targetPos && sourceSpeed < targetSpeed) || (sourcePos < targetPos && sourceSpeed > targetSpeed) || (sourcePos == targetPos))
    {
        return true;
    }
    else
    {
        return false;
    }
}

然后重新看题面，发现有一句话：新感染了病毒的跑者也会感染其他人。于是就想到一轮一轮感染，每轮都将每个没感染的人与每个已经感染的人对应的直线作比较，如果相交则将其加入已感染的集合；以此循环，直到某一轮没有人被传染。有Floyd-Warshall算法的感觉，是不是？看了眼数据范围，好家伙，10⁷，我这O(n³)的算法还是迟早歇着吧。不过粗略来看，应该能过50% N<=100的数据。

于是开始研究一层循环就能搞定的方法，将时间复杂度压缩到O(n)。我们刚刚提到，一个人的直线只要与感染者所在的直线相交，那么他肯定会被感染。那么，一个跑得快的感染者也可以感染遇到的跑得~~比香港记者还快~~更快的感染者，一个跑得慢的感染者也可以感染遇到的跑得更慢的感染者。最终，就体现在被感染的人中，有一个跑得最快的，和一个跑得最慢的，他们在x-t图上组成了类似于上界和下界的一个区域，如下图。

那两条蓝线代表了不断传染最快和最慢的人的过程，落实到程序上也就是维护两个speed和position的下标值，分别代表跑得最快和最慢的人，初始值均为0号患者（即初始被感染的人），如果有能和最快的人对应直线相交且speed更大的人，说明能够传染他，将值更新为这个人对应的下标值，正如图中上方曲线的两次弯折；对跑得最慢的人也是同样的处理办法。

发现什么了吗？这个上界和下界，就是会不会被传染的界限。不过，既然直线可以无限延伸，那么我们可以去掉中间逐渐感染的过程，直接感染最快和最慢的那两个人，就变成了这样：

前后两种方式，虽然过程不同，但感染的结果是等效的。代表最快最慢的直线，一定会与0号感染者直线相交，那么只需要一直选取和0号感染者直线相交，而且比最快更快/比最慢更慢的人来更新最快/最慢下标值即可，而不需要每次都比较”和最快直线相交“且”比最快更快“，或者”和最慢直线相交“且”比最慢更慢“，省下一次比较。

判断是否穿过这两条折线共三条直线，分两种情况：

第一种是判断是否与0号感染者的直线相交；
第二种是判断是否与后面2条直线相交。

满足一种就会被传染。我们刚刚需要一次循环来找最快最慢的跑者，判断这些直线是否与0号直线相交，那么对于相交的直线可以直接打上infected标记，顺便进行第一种情况判断，无需进行第二种判断（直接continue）。第二步的标准又可以转化为”不在上界直线的上方“且”不在下界直线的下方“，其中上方和下方指的是在y轴右侧，函数值永远更大/更小，自然也不会相交。

还记得刚刚那个判断函数吗？我将它改成了下面的样子：

int checkInfection(const int &sourcePos, const int &sourceSpeed, const int &targetPos, const int &targetSpeed) //返回值：1 - 在上方 0 - 相交 -1 - 在下方
{
    if ((sourcePos > targetPos && sourceSpeed < targetSpeed) || (sourcePos < targetPos && sourceSpeed > targetSpeed) || (sourcePos == targetPos))
    {
        return 0;
    }
    if ((targetPos > sourcePos) && (targetSpeed >= sourceSpeed))
    {
        return 1;
    }
    return -1;
}

这样在一个函数里，可以一次判断target直线位于source直线上方、下方还是相交。关于它的理解，可以画个图。

然后统计被打上标记的人数量（可以合在第二种情况判断的函数一起完成），输出即可。

总共四次循环，都为1层，也就是O(n)的复杂度，其中两层循环还是输入数据用的。

This content is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.