所有代码均已上传至 homework/CSP-Training at master · cyp0633/homework (github.com)。不保证代码均正确，正确的也不保证为最优解，可以查看 Commit 详情进一步了解。
1. 字符串反转 2
个人难度评级：2
问题描述
给定一个句子（只包含字母和空格）， 将句子中的单词位置反转，单词用空格分割, 单词之间只有一个空格，前后没有空格。 比如： “hello xiao mi”-> “mi xiao hello”
输入形式
输入数据有多组，每组占一行，包含一个句子 (句子长度小于 1000 个字符)
输出形式
对于每个测试示例，要求输出句子中单词反转后形成的句子
样例输入
hello xiao miI 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 次的电话号码不输出。
样例输入
124873279ITS-EASY888-45673-10-10-10888-GLOPTUT-GLOP967-11-11310-GINOF101010888-1200-4-8-7-3-2-7-9-487-3279样例输出
310-1010 2487-3279 4888-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≤ 103；
10% 的测试数据 1 ≤ n≤ 104；
提示：大量输入数据，C/C++ 输入推荐使用 scanf 函数
输出形式
对于每组测试数据，输出一行，只包含一个字符串，表示缺席的人的姓名。
样例输入
2
张三
张三
李四
0样例输出
李四解题思路
这个题很蛋疼的两个地方是：
- 不排除有重名的情况，所以不能简单地用 bool 存储是否签到 2 次；
- 签到姓名和名册姓名混在了一起，所以不能采取” 先存后删” 的策略。
但是有一点不会变：没来的人，他的名字出现次数是奇数（因为缺且仅缺了一次）。所以我建立一个 pair<string,int> 数组，first 存放姓名，second 存放名字出现次数。直接读入 2n-1 行，统计每个名字出现次数，那么出现了奇数次的名字一定存在缺考情况。
中文应该不需要特殊考虑。但如果你用 getline 函数读取名字，记得也要用 getline 吸收 cin 读取 n 后的回车！用 getchar 会 WA 掉。
4. 电话号码
个人难度评级：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”，依此类推）
样例输入
4ivan 3 123 123 456ivan 2 456 456ivan 8 789 3 23 6 56 9 89 2dasha 2 23 789样例输出
2dasha 2 23 789ivan 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’。先罚球的队伍的信息在上面，后罚的在下面。最右边标上两队的比分。具体格式参考样例输出。注意如果一轮点球只罚了一个，则后面那个点球对应的地方写上’-’。
样例输入
6Riise goodBallack goodGerrard no goodLampard no goodFernando Torres goodMalouda good9Christiano Ronaldo no goodMessi no goodGiggs goodAbidal no goodCarrick goodRonaldinho goodRooney goodHenry no goodTevez good0样例输出
1 2 3 ScoreO X O 2O X O 21 2 3 4 5 ScoreX O O O O 4X 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 6N G3 N N N N N7 1 0 6N G4 N N N N N样例输出
LeleYueyue样例说明
测试用例保证能有确定结果。
解题思路
模拟就完事了，模拟每一步的走法即可。原题是有是否进行不完的判断的，如果有余力可以思考一下。
7. 棋盘
问题描述
棋盘是指一个行和列编号从 1~N 的 NxN 的二进制矩阵，当行号和列号之和为偶数时该矩阵对应位置为黑色的 (1)，否则为白色的 (0)。以下图（没了）示为 N=1、2、3 时的棋盘。
給出一个 NxN 的二进制矩阵，请找出位于该矩阵内的最大尺寸的完整棋盘，以及最大尺寸棋盘的数量（棋盘可以交叠）。
输入形式
每个测试用例的第一行是一个正整数 N(1<=N<=2000)，表示給定矩阵的行数和列数，接下来的 N 行描述了这个矩阵：每行有 N 个字符，既可以是 “1”（代表黑块），也可以是“0”（代表白块）。矩阵至少包含一个“1” 字符。
输出形式
输出最大尺寸棋盘的行列的大小，以及最大棋盘的个数，以空格分隔。
样例输入
50010111010001010101011101样例输出
3 3解题思路
棋盘用 bool 二维数组存储即可，反正只有 0 和 1 两种值。
枚举棋盘左上角起始点，不是黑的直接跳过。对于黑，先得出一个边长上限，就是起始点距离右边和下边的距离最小值。然后枚举边长，大可以先从 2 开始，毕竟起始点本身是黑的就一定是个棋盘。由于每次增加边长，相比上一个边长增加的只有最右边和最下边一条，所以在上个边长能够成立的情况下，只需要检查新增加的两条边是否合理即可；相反，不能成立的话，直接 break 即可，边长小的都不成立那大的更不行了。
验证颜色是否正确的时候，需要注意 “当行号和列号之和为偶数时 “中求和时，以 ** 验证中的棋盘起始点 ** 作为原点，而真正使用的坐标是以 ** 整个大棋盘的 (0,0)** 作为原点。看不懂的话，建议直接去翻我代码……
8 .Engine
个人难度评级：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
6Finding the Shortest Path120Finding the k Shortest Path80Find Augmenting Path in General Graph80Matching in Bipartite Graph200Finding kth Shortest Path50Graph Theory and its Applications406shortest pathk shortest pathgraphpathfindapplication0样例输出 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. 字符串压缩
个人难度评级：6
问题描述
给定一个由 n 个小写字母组成的字符串 s，需要使用最少数量的钱币来压缩它。
压缩该字符串，必须将 s 表示为多个相互连接的非空字符串: s=t1t2…tk，其中第 i 个字符串按照下列两种方法之一编码：
- 如果 | ti|=1，也就是说 ti 为单个字符组成的字符串，编码时需要支付 a 个钱币
- 如果 ti 是 t1t2…ti-1 的子串，编码时需要支付 b 个钱币
你的任务是计算压缩给定的字符串需要花费的最小钱币数。
输入形式
输入的第一行包含 3 个用空格分隔的正整数：n、a 和 b(1≤n、a、b≤5000)，第二行为一个长度为 n 的小写字符串。
输出形式
输出一个整数，表示你需要为压缩 s 所需要支付的最小钱币数。
样例输入 1
3 3 1
aba样例输出 1
7样例输入 2
4 1 1
abcd样例输出 2
4样例输入 3
4 10 1
aaaa样例输出 3
12解题思路
不会，DP 题谁会做谁做去。
10. 拼写检查
来源：POJ 1035
个人难度评级：2
问题描述
作为一个新的拼写检查程序开发团队的成员，您将编写一个模块，用已知的所有形式正确的词典来检查给定单词的正确性。
如果字典中没有这个词，那么可以用下列操作中的一个来替换正确的单词（从字典中）：
1. 从单词中删除一个字母；
2. 用一个任意字母替换单词中的一个字母；
3. 在单词中插入一个任意字母。
你的任务是编写一个程序，为每个给定的单词找到字典中所有可能的替换。
输入形式
输入的第一部分包含所有字典中的词，每个单词占用一行，以一个单一字符 “#” 作为结束。所有单词都不相同，字典中至多 1000 个单词。
接下来的部分包含所有需要进行检查的单词，同样每个单词占用一行。这部分也以一个单一字符 “#” 作为结束。至多有 50 个单词需要检查。
在输入中所有的单词（字典中的和需要检查的）都仅由小写字母组成，每个最多包含 15 个字符。
输出形式
对于每个在输入中出现的单词，按照它们在输入的第二部分出现的顺序输出一行。如果该单词是正确的（也就是说它包含在字典中）则输出信息：“is correct”；如果该单词不正确，则首先输出该单词，然后输入符号 ‘:’（冒号），之后空一格，写出它所有可能的替代，以空格分隔。这些替代的单词按照它们在字典中（输入的第一部分）出现的顺序写出。如果没有可替代的单词，则在冒号后面直接输出换行。
样例输入
iishashavebemymorecontestmetooifaward#meawaremcontesthavooorifimre#样例输出
me is correctaware: awardm: i my mecontest is correcthav: has haveoo: tooor:i is correctfi: imre: 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 的距离差定义为：
$ | | x-Max | -(x-Min) | $
其中 abs() 为求一个数的绝对值
输入形式
包括两行，第一行一个数 n，表示第二行有 n 个正整数
输出形式
输出一个数 x，该数在所有 n 个数中的距离差最小；如果有两个数的距离差都是最小，输出较小的哪个
样例输入 1
5
3 1 7 5 9样例输出 1
5样例输入 2
3
1 3 2样例输出 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
6
10000
1000
21
22样例输出
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)
输出形式
数圈矩阵
样例输入
5样例输出
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（<=105），即双方交锋的次数。随后 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 \ge 0$，在时刻 $t$ 时第 $i$ 名跑者的位置为 $S_i+V_i \cdot t$。
很不幸的是，其中一名跑者在 $t=0$ 的时刻感染了病毒，且是无症状感染者，这种病毒只会在同一时刻处在同一位置的跑者之间传播，新感染了病毒的跑者也会感染其他人，很显然，等待足够长的时间，那么病毒会感染 一些特定的跑者。
事后发现其中有一名跑者感染了新冠病毒，如果此人就是在 $t=0$ 时刻的那名感染者，那么，在 $N$ 名晨跑爱好者中会有多少人感染新冠病毒？
输入形式
输入包含三行：
- 第一行包含为两个整数 $N$ 和 $K$，分别表示运动员的人数以及开始时感染了病毒的跑者编号。
- 第二行包含 $N$ 个正整数 $S_1$、$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样例输出
3评分标准
对于 50% 的评测用例，$0 \lt K \le N \le 102$
对于 70% 的评测用例，$0 \lt K \le N \le 104$
对于 90% 的评测用例，$0 \lt K \le N \le 106$
对于 100% 的评测用例，$0 \lt K \le N \le 107$
详细题解
这题似乎有点意思，是道自创题，值得好好说一说。不过由于本人数学过于弱鸡，这里并没有严格的数学证明。
起初的想法是，对于每一个人的行动路线，可以画出一条一次函数_yi=si+vi*t_。只要遍历一遍其他跑者，与被感染者直线在 y 轴右侧会相交（下文”相交 “均指 y 轴右侧）的，就是被感染的人，是一个 O(n) 的算法。因为相遇距离设定可以是无限远，所以不能枚举距离模拟跑的过程。得了 20 分。
核心是用下面的函数判断两条直线是否相交，也就是是否会被感染。Pos 指的是初始位置，也就是 y 轴截距，而 Speed 代表速度，也就是斜率。
|
|
然后重新看题面，发现有一句话：新感染了病毒的跑者也会感染其他人。于是就想到一轮一轮感染，每轮都将每个没感染的人与每个已经感染的人对应的直线作比较，如果相交则将其加入已感染的集合；以此循环，直到某一轮没有人被传染。有 Floyd-Warshall 算法的感觉，是不是？看了眼数据范围，好家伙，107，我这 O(n3) 的算法还是迟早歇着吧。不过粗略来看，应该能过 50% N<=100 的数据。
于是开始研究一层循环就能搞定的方法，将时间复杂度压缩到 O(n)。我们刚刚提到，一个人的直线只要与感染者所在的直线相交，那么他肯定会被感染。那么，一个跑得快的感染者也可以感染遇到的跑得比香港记者还快更快的感染者，一个跑得慢的感染者也可以感染遇到的跑得更慢的感染者。最终，就体现在被感染的人中，有一个跑得最快的，和一个跑得最慢的，他们在_x-t_图上组成了类似于上界和下界的一个区域，如下图。
那两条蓝线代表了不断传染最快和最慢的人的过程，落实到程序上也就是维护两个 speed 和 position 的下标值，分别代表跑得最快和最慢的人，初始值均为 0 号患者（即初始被感染的人），如果有能和最快的人对应直线相交且 speed 更大的人，说明能够传染他，将值更新为这个人对应的下标值，正如图中上方曲线的两次弯折；对跑得最慢的人也是同样的处理办法。
发现什么了吗？这个上界和下界，就是会不会被传染的界限。不过，既然直线可以无限延伸，那么我们可以去掉中间逐渐感染的过程，直接感染最快和最慢的那两个人，就变成了这样：
前后两种方式，虽然过程不同，但感染的结果是等效的。代表最快最慢的直线，一定会与 0 号感染者直线相交，那么只需要一直选取和 0 号感染者直线相交，而且比最快更快 / 比最慢更慢的人来更新最快 / 最慢下标值即可，而不需要每次都比较”和最快直线相交 “且” 比最快更快 “，或者” 和最慢直线相交 “且” 比最慢更慢“，省下一次比较。
判断是否穿过这两条折线共三条直线，分两种情况：
- 第一种是判断是否与 0 号感染者的直线相交；
- 第二种是判断是否与后面 2 条直线相交。
满足一种就会被传染。我们刚刚需要一次循环来找最快最慢的跑者，判断这些直线是否与 0 号直线相交，那么对于相交的直线可以直接打上 infected 标记，顺便进行第一种情况判断，无需进行第二种判断（直接 continue）。第二步的标准又可以转化为”不在上界直线的上方 “且” 不在下界直线的下方“，其中上方和下方指的是在 y 轴右侧，函数值永远更大 / 更小，自然也不会相交。
还记得刚刚那个判断函数吗？我将它改成了下面的样子：
|
|
这样在一个函数里，可以一次判断 target 直线位于 source 直线上方、下方还是相交。关于它的理解，可以画个图。
然后统计被打上标记的人数量（可以合在第二种情况判断的函数一起完成），输出即可。
总共四次循环，都为 1 层，也就是 O(n) 的复杂度，其中两层循环还是输入数据用的。