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

1. 在霍格沃茨找零钱

个人难度评级：2

问题描述

如果你是哈利 · 波特迷，你会知道魔法世界有它自己的货币系统 —— 就如海格告诉哈利的：“十七个银西可 (Sickle) 兑一个加隆 (Galleon)，二十九个纳特(Knut) 兑一个西可，很容易。”现在，给定哈利应付的价钱 $P$ 和他实付的钱 $A$，你的任务是写一个程序来计算他应该被找的零钱。

输入形式

输入在 $1$ 行中分别给出 $P$ 和 $A$，格式为 “Galleon.Sickle.Knut”，其间用 $1$ 个空格分隔。这里 Galleon 是 $[0, 10^7]$ 区间内的整数，Sickle 是 $[0, 17)$ 区间内的整数，Knut 是 $[0, 29)$ 区间内的整数。

输出形式

在一行中用与输入同样的格式输出哈利应该被找的零钱。如果他没带够钱，那么输出的应该是负数。

样例输入 1

10.16.27 14.1.28

样例输出 1

3.2.1

样例输入 2

14.1.28 10.16.27

样例输出 2

-3.2.1

解题思路

建议不要全部化为 Knut 再计算，直接对应相减然后借位即可。

本题一个坑，没带够钱的情况下，输出的数只有 Galleon 位有负号，实际上的意思是三个数都有负号，后面两个不需要输出。也就是说，” 样例输出 2“的意义是找回 - 3 Galleon, -2 Sickle 和 - 1 Knut。我建议的处理方式是，如果在借位之前最高位是负值，则将每一位取相反数，并输出一个负号，然后照常借位计算。

2. 最简单的计算机

个人难度评级：1

问题描述

一个名叫是 $PigHeadThree$ 的研究组织设计了一台实验用的计算机，命名为 $PpMm$。$PpMm$ 只能执行简单的六种命令 $A$，$B$，$C$，$D$，$E$，$F$；只有二个内存 $M1$，$M2$；三个寄存器 $R1$，$R2$，$R3$。六种命令的含义如下：
命令 $A$：将内存 $M1$ 的数据装到寄存器 $R1$ 中；
命令 $B$：将内存 $M2$ 的数据装到寄存器 $R2$ 中；
命令 $C$：将寄存器 $R3$ 的数据装到内存 $M1$ 中；
命令 $D$：将寄存器 $R3$ 的数据装到内存 $M2$ 中；
命令 $E$：将寄存器 $R1$ 中的数据和寄存器 $R2$ 中的数据相加，结果放到寄存器 $R3$ 中；
命令 $F$：将寄存器 $R1$ 中的数据和寄存器 $R2$ 中的数据相减，结果放到寄存器 $R3$ 中。
你的任务是：设计一个程序模拟 $PpMm$ 的运行。

输入形式

有若干组，每组有 $2$ 行，第一行是 $2$ 个整数，分别表示 $M1$ 和 $M2$ 中的初始内容；第二行是一串长度不超过 $200$ 的由大写字母 $A$ 到 $F$ 组成的命令串，命令串的含义如上所述。

输出形式

对应每一组的输入，输出只有一行，二个整数，分别表示 $M1$，$M2$ 的内容；其中 $M1$ 和 $M2$ 之间用逗号隔开。

样例输入

100 288
ABECED
876356 321456
ABECAEDBECAF

样例输出

388,388
2717080,1519268

解题思路

果然是最简单的…… 什么，你不会 switch 语句都不会用吧？

3. 相同生日

个人难度评级：2

问题描述

在一个有 $n$ 个人的大班级中，存在两个人生日相同的概率非常大，现给出每个学生的学号，出生月日，试找出所有生日相同的学生。

输入形式

第一行为整数 $n$，表示有 $n$ 个学生，$n \le 200$。此后每行包含一个字符串和两个整数，分别表示学生的学号 (字符串长度为 $11$ 位) 和出生月 $(1 \le m \le 12)$ 日 $(1 \le d \le 31)$，学号、月、日之间用一个空格分隔。

输出形式

对每组生日相同的学生，输出一行，其中前两个数字表示月和日，后面跟着所有在当天出生的学生的学号，数字、学号之间都用一个空格分隔。对所有的输出，要求按日期从前到后的顺序输出。对生日相同的学号，按输入的顺序输出。

样例输入

6
07101020105 3 15
07101020115 4 5
07101020118 3 15
07101020108 4 5
07101020111 4 5
07101020121 8 10

样例输出

3 15 07101020105 07101020118
4 5 07101020115 07101020108 07101020111
8 10 07101020121

解题思路

建立 vector<string> birthday[13][32]，然后将对应生日的同学之间 push_back 进对应日期的 vector 即可。要求同日期按输入顺序输出，不需 priority_queue 之类。虽学号是数字但不能直接用 long long，当然你输出保留 11 位，前面补 0 也可以，主要就是前导 0 的问题。

4. 日历问题

个人难度评级：3

问题描述

在我们现在使用的日历中, 闰年被定义为能被 $4$ 整除的年份，但是能被 $100$ 整除而不能被 $400$ 整除的年是例外，它们不是闰年。例如：$1700$, $1800$, $1900$ 和 $2100$ 不是闰年，而 $1600$, $2000$ 和 $2400$ 是闰年。 给定从公元 $2000$ 年 $1$ 月 $1$ 日开始逝去的天数，你的任务是给出这一天是哪年哪月哪日星期几。

输入形式

输入包含若干行，每行包含一个正整数，表示从 $2000$ 年 $1$ 月 $1$ 日开始逝去的天数。输入最后一行是 $-1$, 不必处理。可以假设结果的年份不会超过 $9999$。

输出形式

对每个测试样例，输出一行，该行包含对应的日期和星期几。格式为 “YYYY-MM-DD DayOfWeek”, 其中 “DayOfWeek” 必须是下面中的一个： “Sunday”, “Monday”, “Tuesday”, “Wednesday”, “Thursday”, “Friday” and “Saturday“。

样例输入

1730
1740
1750
1751
-1

样例输出

2004-09-26 Sunday
2004-10-06 Wednesday
2004-10-16 Saturday
2004-10-17 Sunday

解题思路

这个题结合 代码 看得更明白。

打表，建立五个数组，内容如下：

• $[2000,9999]$ 年范围内，每一年的最后一天是 1999 年 12 月 31 号之后的第几天，即只需计算每年天数的前缀和；
• $[2000,9999]$ 年范围内，每一年是否是闰年（这个不要用 true 或者 false 表示，否则代码会超过 100KB 而无法提交）；
• 闰年中，每一个月的最后一天是上一年 12 月 31 日之后第几天，即每个月天数的前缀和；
• 平年中，同上；
• 天数模 7，每个余数所对应最后日期的星期，第 1 个值不是 Monday 也不是 Sunday，而是 Saturday（2000/01/01 就是周六，过 7 的倍数天还是周六）。

首先模 7 算完星期之后，要将输入的天数 + 1，转换为”2000 年 1 月 1 日起的第几天 “。

然后枚举第一个数组，如果某个年份（减 2000）对应的值大于等于天数，则该年份就是所求日期年份。从天数中减掉数组中上一年对应的值（2000 年不用），得到所求日期是这一年的第几天。如果天数减为 0，则赋给它本年天数值（当然，直接输出 12 月 31 日也未尝不可）。

分是否闰年，枚举第三 / 四个数组，以和上面相似的方式确定月份。自然也就很容易得到日期。

格式化输出中，使用 %02d，输出整型并在不足 2 位的时候补 0。

5. 小希的数表

个人难度评级：4

问题描述

Gardon 昨天给小希布置了一道作业，即根据一张由不超过 $5000$ 的 $N$ $(3 \le N \le 100)$ 个正整数组成的数表两两相加得到 $N*(N-1)/2$ 个和，然后再将它们排序。例如，如果数表里含有四个数 $1$，$3$，$4$，$9$，那么正确答案是 $4$，$5$，$7$，$10$，$12$，$13$。小希做完作业以后出去玩了一阵，可是下午回家时发现原来的那张数表不见了，好在她做出的答案还在，你能帮助她根据她的答案计算出原来的数表么？

输入形式

包含多组数据，每组数据以一个 $N$ 开头，接下来的一行有按照大小顺序排列的 $N*(N-1)/2$ 个数，是小希完成的答案。文件最后以一个 $0$ 结束。
假设输入保证解的存在性和唯一性。

输出形式

对于每组数据，输出原来的数表。它们也应当是按照顺序排列的。

样例输入

4
4 5 7 10 12 13
4
5 6 7 8 9 10
0

样例输出

1 3 4 9
2 3 4 6

解题思路

设 $a$ 为原数字列表，$s$ 为和的列表。

首先，由于 $s_i$ 和 $a_i$ 是从小到大排列的，反证法易证 $s_1=a_1+a_2$，$s_2=a_1+a_3$。然而 $s_3$ 并不一定是 $a_2+a_3$，而很可能是 $a_1+a_4$ 等。由此，我们需要枚举 $s_3$ 到 $s_{(n-1)*n/2}$，对于每一个 $s_i$，结合 $s_1$ 和 $s_2$，解出 $a_1$、$a_2$ 和 $a_3$，当它们均为正整数的时候才可能符合条件，能够往下进行。符合这里条件的 $a_2+a+_3$ 可能有多组，可能在后续步骤中会毙掉几组。

然后，我们只需要找出 $s_j=a_1+a_i$，就可以算出 $a_i$。因为 $a_1$ 最小，所以 $s_j$ 排在较靠前的位置，比较好找。比如现在我们要找 $a_1+a_4$，如果将 $a_1$、$a_2$ 和 $a_3$ 两两组合算出和，然后将这些和从 $s$ 中剔除，那么可以证明 $a_1+a_4$ 就是剩下的当中最小的一个和，也就能比较容易地从 $s$ 中找出。当然，仍然要检验 $a_4$ 乃至后面所有的 $a_i$ 是不是正整数。

现在我们找到了 $a_4$，那么该怎么找到 $a_5$ 乃至后面的数呢？我们可以仿照前面的方法，将前面已求出的数两两组合求和，将结果存入一个 set 中（毕竟剔除工作比较复杂）。在遍历每个 $s$ 的时候，如果 $s_i$ 的值处在该 set 中，则跳过。否则，这个值就是 $a_1+a_{j}$，$j$ 是已经确定的 $a$ 数量。然后，将这个 $a_j$ 分别与前面的 $a$ 相加，存入 set，就可以及时维护这个 set。

所有 $a$ 的值都确定完成，你以为就得出解了吗？早着呢，这样你会 WA 掉测试点 3、4、5、6 和 7。刚刚我们所求出的这套解，并不一定能满足题目的条件，也就是加出后面的和。既然已经假定所有的 $a$ 已经解出并符合题目要求，那么 set 中理应出现测试数据给出的所有的 $s_i$。继续遍历，对后面的每一个 $s_i$，都查找它是否在 set 中。如果不在，那么这组 $a$ 就不是符合条件的解，再取一个 $a_2+a_3$ 吧……

你兴致勃勃地将代码交了上去，发现只解决了 7。不同的 $a_i+a_j$ 组合可以得出相同的两个 $s$ 值。这时候再用 set 就明显不合适了，可以考虑使用同一个键值允许出现多次的 set——multiset，同时将已经在 $s$ 中出现的和删除。很容易想到使用 multiset 的 erase 函数处理，但这个函数有多个重载，如果传入一个键值，它会删除该键值的 ** 所有 ** 元素。而如果传入一个指针 / 迭代器，就只会删除指向的这一个元素。我们的需求是出现一次删除一次，那当然要传入迭代器。

6. 数塔

个人难度评级：2

问题描述

给定一个数塔，如下图所示。在此数塔中，从顶部出发，在每一节点可以选择走左下或右下，一直走到底层。请找出一条路径，使路径上的数值和最大。

输入形式

输入时第一行一个整数 $n$，表示该数塔的行数，其余 $n$ 行表示该塔每行的数值

输出形式

输出包含两行，第一行为最大路径上的数值之和， 第二行 $n$ 个数字为从上而下最大路径数值

样例输入

5
9
12 15
10 6 8
2 18 9 5
19 7 10 4 16

样例输出

59
9 12 10 18 10

解题思路

一道标准的搜索题，可以 DFS 也可以 BFS，搜索过程中传递行号、列号、当前路径长度和用 vector 存储的完整路径。

7. 斯诺克台球（不做了）

个人难度评级：6

问题描述

斯诺克台球是一项古老而又时尚的运动，使用长方形球桌，台面四角以及两长边中心位置各有一个球袋，使用的球分为 1 个白球，15 个红球和 6 个彩球共 22 个球。

其中母球（白球）1 只，目标球 21 只。目标球中：红球 15 只各 1 分、黄球 1 只 2 分、绿球 1 只 3 分、咖啡球 1 只 4 分、蓝球 1 只 5 分、粉球 1 只 6 分、黑球 1 只 7 分。

选手需要使用球杆撞击母球去击打目标球来完成得分，每局开始时总是先从红球开始。击球顺序为先打进红球（每次击打允许多个红球同时落袋），然后必须任意指定一个目标彩球击打，如果该彩球被打进（打进后需要再摆回），然后接着击打红球，直到红球全部落袋，然后以黄、绿、咖啡、蓝、粉红、黑的顺序逐个击球（不再摆回），最后以得分高者为胜。任何时候红球落袋都不再摆回，任何时候因犯规导致彩球落袋，彩球必须摆回。

斯诺克比赛由双方轮流击打，必须击打合规的目标球，打进则本方得到相应的分数并继续击打，未打进或犯规轮换为对方击打，未打进不得分，犯规将进行罚分处理。

犯规规则如下：

1.     当击打目标球时，如果先击打到或同时击打到一个或多个其他颜色的球，或者有其他颜色的球落袋，或者打空 (未击打到任何球)，则视为犯规。此时需要比较目标球的分值和与本犯规相关的其他颜色的球的分值，取其中最高的分值，如果该分值小于 4，则对方加 4 分，否则对方加该分值。

2.     当击打红球落袋后，继续击打任意彩球时打空，即未打击到任何球，对方加 4 分。

相比正式的斯诺克比赛，本问题对规则进行了简化，任何时候都可以结束比赛并计算比赛结果，不考虑白球落袋的情况。

信息化时代的智能台球桌能自动记录实际比赛时的击打记录，并传送到后台，但该记录仅仅是流水记录，并且无参赛选手的任何信息，需要你编程计算每场比赛的比分，同时需要计算单杆 100 分及以上的情况（单杆得分是指选手一次连续击打所得分数之和）。

输入形式

输入第一行为正整数 $t$ $(t \le 100)$，表示有 $t$ 组测试数据，每组数据代表一局比赛。

在输入中，球的颜色表示为：

**r - 红色球 y - 黄色球 g - 绿色球 c - 咖啡色球 b - 蓝色球 p - 粉红球 B - 黑色球 **

接下来的每组数据包括若干行，每一行为一次击打的结果，为智能球桌记录下来的流水记录，每组数据最后一行为 - 1，表示每组数据的结束。

流水记录包含用空格分隔的 2 个部分：

首先撞到的球 落袋球及数量

第一部分 “首先撞到的球” 为一个字符串，可以是 “rygcbpB” 中 1 个或多个字符组合（可能有多个字符 “r”）, 或为字符串“$NULL$”。为“$NULL$” 时，第二部分必为空，表示该次击打未撞击到任何球也没有任何球落袋。当红球落袋后继续击打任意彩球时，该部分为 “ygcbpB” 中的任意单个字符时都认为是合规的目标球。

第二部分 “落袋球及数量” 为一个字符串，例如“r2gb”，代表本次击打有两个红球落袋，以及绿球和篮球落袋，红色球 r 后面有数字（大于 $0$ 小于 $16$），表示红球的落袋数，其他彩球后无数字。该部分可以为空，表示本次击打无球落袋。

比赛在 $A$ 与 $B$ 之间进行，每局比赛总是由 $A$ 先开球。

输出形式

输出为 $t+1$ 行，前 $t$ 行每行输出用冒号分隔的两个整数，表示每局比赛 $A$ 与 $B$ 之间的比分；最后一行输出用冒号分隔的两个整数，表示 $t$ 局比赛之后 $A$ 与 $B$ 之间获得的单杆 $100$ 分及以上的次数之比（单杆得分是指选手一次连续击打所得分数之和）。

样例输入

3
r r1
B
r r2
c c
r r1
b g
-1
rp r1
r br2B
NULL
r r12
y y
g p
-1
rr r3
NULL
r r1
yg y
-1

样例输出

6:7
13:24
7:5
0:0

样例说明

第一局比赛：

A 击打红球，打进 1 个红球，得 1 分，比分为 1:0

A 继续击打任意彩球，打到黑球，未打进，不得分，比分为 1:0

轮换为 B 击打红球，打进两个红球，得 2 分，比分为 1:2

B 继续击打任意彩球，打到咖啡球，打进咖啡球，咖啡球摆回，得 4 分，比分为 1:6

B 继续击打红球，打进一个红球，得 1 分，比分为 1:7

B 继续击打任意彩球，打到蓝球，打进绿球，犯规，取分值最大者蓝球，绿球摆回，对方加 5 分，比分为 6:7

-1 比赛结束

第二局比赛：

A 击打红球，首先打到红球和粉球，犯规，打进 1 个红球和咖啡球，犯规，咖啡球摆回，取分值最大的粉球，对方加 6 分，比分为 0:6

B 击打红球，首先打到红球，打进蓝球、2 个红球和黑球，犯规，蓝球和黑球摆回，取分值最大的黑球，对方加 7 分，比分为 7:6

A 击打红球，未打到任何球，犯规，对方加 4 分，比分为 7:10

B 击打红球，打到红球，打进 12 个红球，加 12 分，比分为 7:22

B 击打任意彩球，打到黄球，打进黄球，黄球摆回，得 2 分，比分为 7:24

B 击打黄球，打到绿球，打进粉球，犯规，粉球摆回，对方加 6 分，比分为 13:24

-1 比赛结束

第三局比赛：

A 击打红球，打到 2 个红球，打进 3 个红球，加 3 分，比分为 3:0

A 击打任意彩球，打空，未打到任何球，对方加 4 分，比分为 3:4

B 击打红球，打到 1 个红球，打进 1 个红球，加 1 分，比分为 3:5

B 击打任意彩球，打到黄球和绿球，打进黄球，犯规，黄球摆回，取分值最高的绿球，绿球分值小于 4，对方加 4 分，比分为 7:5 

-1 比赛结束

3 局比赛中无人单杆得分过 100，最后一行输出 0:0

解题思路

大模拟做他🐎呢，笑死，根本做不出来😅

8. 最少钱币数

个人难度评级：4

问题描述

这是一个古老而又经典的问题。用给定的几种钱币凑成某个钱数，一般而言有多种方式。例如：给定了 6 种钱币面值为 2、5、10、20、50、100，用来凑 15 元，可以用 5 个 2 元、1 个 5 元，或者 3 个 5 元，或者 1 个 5 元、1 个 10 元，等等。显然，最少需要 2 个钱币才能凑成 15 元。
        你的任务就是，给定若干个互不相同的钱币面值，编程计算，最少需要多少个钱币才能凑成某个给出的钱数。

输入形式

输入可以有多个测试用例。每个测试用例的第一行是待凑的钱数值 $M$ $(1 \le M \le 2000，整数)$，接着的一行中，第一个整数 $K$ $(1 \le K \le 10)$ 表示币种个数，随后是 $K$ 个互不相同的钱币面值 $K_i$ $(1 \le K_i \le 1000)$。输入 $M=0$ 时结束。

输出形式

每个测试用例输出一行，即凑成钱数值 $M$ 最少需要的钱币个数。如果凑钱失败，输出 “Impossible”。你可以假设，每种待凑钱币的数量是无限多的。

样例输入

156 2 5 10 20 50 10011 20

样例输出

2Impossible

解题思路

DP 题，有点像完全背包。参考了 最少钱币数（DP）_Salmon_lee 的博客 - CSDN 博客。

这道题的最优子结构性质是，可以先得出用前 $i$ 种面值得出 $j$ 元以内的最少钱币数。使用前 $i$ 种面值组合成 $j$ 元的最少钱币数，是 “使用前 $i-1$ 种面值组合成 $j$ 元的最少钱币数” 与“使用前 $i$ 种面值组合成 $j-val$ 元的最少钱币数 + 1，$val$ 为第 $j$ 种钱币的面值”的较小值，即状态转移方程：$dp_{i,j}=min(dp_{i-1,j},dp_{i,j-val})$。两层循环，第一层循环遍历各种面值的钱币，第二层循环遍历各种金额，均为从前往后遍历。二维 DP 示例代码在这里。

那么可不可以压缩成一维呢？自然可以，将前 i 种面值的这一维压掉。状态转移方程变为 $dp_i=min(dp_i,dp_{i-val})$。

注意多组数据，dp 数组需要 memset 多次。

9. 相等的多项式

个人难度评级：2

问题描述

小明现在在学习多项式的展开：就是把一个形如

$(x+a_1)(x+a_2)…(x+a_n)$

展开成如下形式：

$x^n+b_1x^{n-1}+b_2x^{n-2}+…+b_{n-1}x+b_n$

比如 $(x+1)(x+2)=x^2+3x+2$

      $(x+1)^3=x^3+3x^2+3x+1$

小明做了很多练习，但是不知道对错，现在请求你的帮助，判断小明的展开式是否正确。

** 输入格式 **

有多组测试数据。

每组测试数据有三行，第一行是一个正整数 $N$，表示多项式最高指数。$N=0$ 表示输入结束，并且不需要处理。

第二行 N 个整数 ai，用空格隔开，$i=1，…,N(-100 \le a_i \le 100)$

第三行 N 个整数 bi，用空格隔开，$i=1，…,N，(-10^9 \le b_i \le 10^9)$

40% 的测试数据 $1 \le N < 5$；

30% 的测试数据 $5 \le N < 10$；

20% 的测试数据 $10 \le N < 15$；

10% 的测试数据 1$5 \le N \le 20$；

** 输出格式 **

　　对于每组测试数据，输出一行一个字符‘Y’ 如果展开式是正确的，输出‘N’如果展开式错误。

** 样例输入 **

2
1 2
3 2
3
1 1 1
3 3 1
4
0 0 0 1
0 0 0 1
0

** 样例输出 **

Y
Y
N

解题思路

如果还记得二项式定理，这道题会好做很多。使用 DFS，对每个因式分别选择乘上字母或者数字，边界条件为选择完所有因式，此时将该次数的因子加到结果多项式的数组对应项即可。

题目输入的多项式是按次数由大到小排的，由 $n-1$ 到 $0$，而我们乘出的多项式数组应该反向与它比较。

10. 选美比赛

个人难度评级：1

问题描述

在选美大奖赛的半决赛现场，有 $n$ 名选手 $(2<n<100)$ 参加比赛。比赛结束时，要在现场按照选手的出场顺序宣布最后名次，获得相同分数的选手具有相同的名次，名次连续编号，不用考虑同名次的选手人数。如：

选手数量：  7

选手得分：  5，3，4，7，3，5，6

宣布名次：  3，5，4，1，5，3，2

请编程帮助大奖赛组委会完成半决赛的评分排名工作。

输入形式

选手数量：7

选手得分：5 3 4 7 3 5 6

输出形式

选手的排名：3 5 4 1 5 3 2

样例输入

7
5 3 4 7 3 5 6

样例输出

3 5 4 1 5 3 2

样例说明

本题的关键在于如何处理同分数的选手排名问题

解题思路

用结构体存储选手，内含编号、得分和排名三个成员变量。

输入得分顺便指定编号，按照得分降序 sort 一遍，赋给排名（注意：即使有多个第 $n$ 名并列，排在这些后面的仍然是 $n+1$ 名），然后再按照编号升序 sort，输出即可。

11. 蛇行矩阵

个人难度评级：2

问题描述

蛇形矩阵是由 1 开始的自然数依次排列成的一个矩阵上三角形

输入形式

 正整数 N 表示层数，N 不大于 100

输出形式

输出一个 N 行的蛇形矩阵，矩阵三角中同一行的数字用一个空格分开，行尾不要多余的空格。

样例输入

5

样例输出

1 3 6 10 152 5 9 144 8 137 1211

解题思路

首先构建第一列。容易观察得到，上下相邻的两个值有关系 $a_{i,1}=a_{i-1,1}+i-1 (2 \le i \le n)$。要是我还在上高中，也许能算出通项公式，但现在不一定了

然后对于每一行，根据第一列构建剩下的列，根据关系 $a_{i,j}=a_{i,j-1}+i+j-1(1 \le i \le n, 2 \le j \le n-i+1)$。

没必要真按照蛇形去构建，按照上面的方法可以直接打个表交上去，虽然完整的重新构建也不会超时就是了。

12. 疫情期间

个人难度评级：3 | TLE 了测试点 1

问题描述

        正值新冠疫情期间，阿迪没法返回学校学习，他希望通过参加一些比赛来提高一下编程技能，同时做做运动。他收集了接下来的 $n$ 天里每一天的信息，包括健身房是否开放，或者互联网上是否有程序设计竞赛。

        第 $i$ 天可以有以下四种情况之一：

• 该天健身房不开放，互联网上也没有竞赛
• 该天健身房不开放，但互联网上有竞赛
• 该天健身房开放，但互联网上没有竞赛
• 该天健身房开放，互联网上也有竞赛

        每天阿迪要么休息，要么编写程序（如果该天有竞赛），要么做运动（如果该天健身房开放）。

        现在有一个限制条件：不能连续两天都去做运动，或者连续两天都编写程序。阿迪对自己要求很高，希望尽量多写程序或者多做运动，使得休息的天数尽量最少，求出这个天数。

输入形式

        输入的第一行为一个正整数 $n(1 \le n \le 100)$，表示接下来的天数。

        第二行为一个用空格分隔的整数序列 $a_1$、$a_2$、…、$a_n$ $(0 \le a_i \le 3)$，这里

• $a_i=0$，第 $i$ 天健身房不开放，互联网上也没有竞赛
• $a_i=1$，第 $i$ 天健身房不开放，但互联网上有竞赛
• $a_i=2$，第 $i$ 天健身房开放，但互联网上没有竞赛
• $a_i=3$，第 $i$ 天健身房开放，互联网上也有竞赛

输出形式

        输入阿迪可能休息的最小天数。注意限制条件：

• 不能连续两天去做运动
• 不能连续两天编写程序

样例输入 1

4
1 3 2 0

样例输出 1

2

样例输入 2

7
1 3 3 2 1 2 3

样例输出 2

0

样例输入 3

2
2 2

样例输出 3

1

样例说明

在第一个样例中，阿迪在第一天编写程序，在第三天做运动，因此他仅有两天可以休息。

在第二个样例中，阿迪可以在第 1、3、5、7 天编写程序，其他天做运动，因此没有哪天休息。

在第三个样例中，阿迪可以在第 1 天或第 2 天做运动，但不能连续两天运动，因此他有一天休息。

解题思路

暴搜 90 分。DFS 传入天数、休息次数和上一天的行为，分为编程、运动和休息三种情况即可。

其实 90 分也不错了，对吧？

13.7，还是 7

个人难度评级：1

问题描述

输出 7 和 7 的倍数，还有包含 7 的数字例如（17，27，37…70，71，72，73…）

输入形式

一个正整数 $N$。($N$ 不大于 $30000$)

输出形式

从小到大排列的不大于 N 的与 7 有关的正整数，每行一个。

样例输入

20

样例输出

71417

解题思路

可以结合 to_string 和字符串 find 函数来找包含 7 的数字。

14. 组个最小数

个人难度评级：1

问题描述

给定数字 0-9 各若干个。你可以以任意顺序排列这些数字，但必须全部使用。目标是使得最后得到的数尽可能小（注意 0 不能做首位）。例如：给定两个 0，两个 1，三个 5，一个 8，我们得到的最小的数就是 10015558。

现给定数字，请编写程序输出能够组成的最小的数。

输入形式

每个输入包含 1 个测试用例。每个测试用例在一行中给出多个（不超过 50 个）数字（0~9 之间），整数间用一个空格分隔，且至少拥有 1 个非 0 的数字。

输出形式

在一行中输出能够组成的最小的数。

样例输入

2 2 0 0 0 3 0 0 1 0

样例输出

1000000223

解题思路

输入时统计每个数出现次数，先输出一个非零数，然后剩下的从小到大输出。

15. 字频统计

个人难度评级：2

** 问题描述 **

在一个只有字母’a’ 和’b’ 组成的字符串中，统计子串 “ab” 和 “ba” 出现次数的差。

** 输入格式 **

有多组测试数据。

每组测试数据第一行是一个正整数 $N$，表示字符串长度，接下来一行是长度为 $N$ 的字符串，字符串中只有字母’a’ 和’b’。

$N=0$ 表示输入结束，并且不需要处理。

$40%$ 的数列元素个数 $N$ $1 \le N \le 100$；

$30%$ 的数列元素个数 $N$ $1 \le N \le 1000$；

$20%$ 的数列元素个数 $N$ $1 \le N \le 10000$；

$10%$ 的数列元素个数 $N$ $1 \le N \le 100000$；

** 输出格式 **

　　对于每组测试数据，输出一个整数：“ab” 和 “ba” 出现次数的差。

** 样例输入 **

7
aaaaaaa
4
abab
0

** 样例输出 **

0
1

解题思路

这个似乎用不了字符串的 find 成员函数，那就自己写呗。每个字符串遍历两遍，找就行了。

16. 逆序数

个人难度评级：1

** 问题描述 **

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。也就是说，对于 $n$ 个不同的元素，先规定各元素之间有一个标准次序（例如 $n$ 个 不同的自然数，可规定从小到大为标准次序），于是在这 $n$ 个元素的任一排列中，当某两个元素的先后次序与标准次序不同时，就说有 $1$ 个逆序。一个排列中所有逆序总数叫做这个排列的逆序数。

比如：

数列 1 7 3 5 4 8 9

其中 $(7,3)$，$(7,5)$，$(7,4)$，$(5,4)$ 构成逆序，所以其逆序数为 $4$。

对给定的数列，求出其逆序数。

** 输入格式 **

有多组测试数据。

每组测试数据第一行是一个正整数 $N$，表示数列中元素个数，接下来一行 $N$ 个用空格分隔开的正整数，表示数列的 $N$ 个元素，数列元素值小于 $32768$，并且一个数列中没有两个数值相同。

$N=0$ 表示输入结束，并且不需要处理。

$40%$ 的数列元素个数 $N$ $1 \le N \le 10$；

$30%$ 的数列元素个数 $N$ $1 \le N \le 100$；

$20%$ 的数列元素个数 $N$ $1 \le N \le 1000$；

$10%$ 的数列元素个数 $N$ $1 \le N \le 5000$；

** 输出格式 **

　　对于每组测试数据，输出一个整数：数列的逆序数。

** 样例输入 **

7
1 7 3 5 4 8 9
4
1 2 3 4
0

** 样例输出 **

4
0

解题思路

两层循环枚举组合解决。

17. 最小钱币数（贪心算法）

个人难度评级：1

问题描述

阿迪有很多钱。他在银行里有 n 元。出于安全考虑，他想用现金取款（此处不透露原因）。钞票的面额是 1，5，10，20，100 元。取出全部余额后能收到的最小钞票数是多少？

输入形式

输入一个正整数 $n$，$(1 \le n \le 10^9)$

输出形式

阿迪能收到的最小钞票数

样例输入 1

125

样例输出 1

3

样例输入 2

43

样例输出 2

5

样例输入 3

1000000000

样例输出 3

10000000

样例说明

本题可以直接使用贪心策略（优先尽可能多选择大面额的钞票）解决：主要原因是后一个的权值（这里就是纸币面值）是前一个的 2 倍或以上。

可以思考一下如果货币的类型是 1,9,10 元三种，要求凑出 18 元，你可能就会发现贪心算法出错了！

解题思路

上面说得这么明白了我还说啥啊，这题没了 DP 就没了灵魂了。

18. 身份证校验

个人难度评级：1

问题描述

我国国标〖GB 11643-1999〗中规定：公民身份号码是 18 位特征组合码，由十七位数字本体码和一位数字校验码组成。排列顺序从左至右依次为：六位数字地址码，八位数字出生日期码，三位数字顺序码和一位数字校验码。其校验码 (最后一位) 计算方法和步骤为：

(1) 十七位数字本体码加权求和公式

$S = sum(A_i * W_i), i = 0, … , 16$ ，先对前 17 位数字的权求和

其中 $A_i$：表示第 i 位置上的身份证号码数字值

$W_i$：表示第 i 位置上的加权因子，前 17 位加权因子从左到右分别为

$W_i$：7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2

(2) 计算模

$Y = mod(S, 11)$

(3) 通过模 Y 查下表得到对应的校验码

例如：某身份证前 17 位为 11010519491231002

得到和为：167；则模为 $y=167%11=2$

查 (3) 得校验码为 X（大写）

请按上面所述步骤编程，输入一个二代身份证号，检查该身份证是否正确。

输入形式

输入若干行，每行一个身份证号码，最后一行输入 - 1

输出形式

输出 1 代表正确，0 代表错误

样例输入

120223198902021249
130132199210293822
130402198207290622
-1

样例输出

1
1
0

解题思路

如果会用 std::map，可以将校验码和余数对应，很方便。写一堆 if 倒也不是不能做。

18. 最长递增子序列

个人难度评级：2

问题描述

给出一个由 $n$ 个正整数组成的数组。您的任务是找到给定数组的递增子数组的最大长度。

递增子数组由数组中若干个连续元素组成，且子数组中的每个元素严格地大于前一个元素。

输入形式

第一行为一个正整数 $n(1 \le n \le 10^5)$，表示数组元素的个数

第二行给出 $n$ 个正整数 $a_1$ $a_2$……$a_n$  $(1 \le a_i \le 10^9)$ ，整数之间使用空格分隔

输出形式

输出最大递增子数组的长度

样例输入

5
1 7 2 11 15

样例输出

3

样例说明

1 7 可以构成一个递增子数组

2 11 15 可以构成一个递增子数组

所以本样例的输出结果为 3

解题思路

贪心。遍历一遍，有递增的就计数，不递增了就重置。

20.Caesar 密码

个人难度评级：1

问题描述

Julius Caesar 生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是 Caesar 军团中的一名军官，需要把 Caesar 发送的消息破译出来、并提供给你的将军。消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第 5 个字母替换（例如：消息原文中的每个字母 A 都分别替换成字母 F），其他字符不 变，并且消息原文的所有字母都是大写的。 密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

输入形式

最多不超过 100 个数据集组成。每个数据集由 3 部分组成：起始行：START 密码消息：由 1 到 200 个字符组成一行，表示 Caesar 发出的一条消息结束行：END 在最后一个数据集之后，是另一行：ENDOFINPUT

输出形式

每个数据集对应一行，是 Caesar 的原始消息。

样例输入

START
NS BFW, JAJSYX TK NRUTWYFSHJ FWJ YMJ WJXZQY TK YWNANFQ HFZXJX
END
START
N BTZQI WFYMJW GJ KNWXY NS F QNYYQJ NGJWNFS ANQQFLJ YMFS XJHTSI NS WTRJ
END
START
IFSLJW PSTBX KZQQ BJQQ YMFY HFJXFW NX RTWJ IFSLJWTZX YMFS MJ
END
ENDOFINPUT

样例输出

IN WAR, EVENTS OF IMPORTANCE ARE THE RESULT OF TRIVIAL CAUSES
I WOULD RATHER BE FIRST IN A LITTLE IBERIAN VILLAGE THAN SECOND IN ROME
DANGER KNOWS FULL WELL THAT CAESAR IS MORE DANGEROUS THAN HE

解题思路

推荐使用 getline 函数输入数据，一次输入是一整行。

没必要前面提到的 std::map，因为这个太有规律了，对于大写字母，ASCII 直接减 5，如果小于’A’ 再加 26 即可。

21. 回文串

** 问题描述 **

“回文串”是一个正读和反读都一样的字符串，比如 “level” 或者 “noon” 等等就是回文串。给你一个字符串，问最少在字符串尾添加多少字符，可以使得字符串变为回文串。

** 输入格式 **

有多组测试数据。

每组测试数据第一行是一个正整数 $N$，表示字符串长度，接下来一行是长度为 N 的字符串，字符串中只有小写字母。

$N=0$ 表示输入结束，并且不需要处理。

$40 % $ 的数列元素个数 $N$ $1 \le N \le 100$；

$30 % $ 的数列元素个数 $N$ $1 \le N \le 1000$；

$20 % $ 的数列元素个数 $N$ $1 \le N \le 10000$；

$10 % $ 的数列元素个数 $N$ $1 \le N \le 100000$；

** 输出格式 **

　　对于每组测试数据，输出一个非负整数：添加最少的字符数，可以使得字符串变为回文串。

** 样例输入 **

3
aba
4
aaac
0

** 样例输出 **

0
3

解题思路

参考了 HNU 软件能力实训 4-21. 回文串 _Karltan 的博客 - CSDN 博客。

对于每个字符串，逐个截取前 1、2、3…… 到 N 位并反转，连接到原串后面，然后检验是否为回文串即可。

熟练运用 STL 会让这道题非常简单（主要是 reverse 和 substr）。