一、编程题
1、1.漫漫回国路
2020年5月，国际航班机票难求。一位在美国华盛顿的中国留学生，因为一些原因必须在本周内回到北京。现在已知各个机场之间的航班情况，求问他回不回得来（不考虑转机次数和机票价格）。
时间限制：1000
内存限制：65536
输入
第一行为case个数n(n < 10)。 每一个case，第一行为机场个数N，N ≤ 10。 之后的N行，每一行包含N个整数。第i（1 ≤ i ≤ N）行的第j（1 ≤ j ≤ N）个整数代表从第i个机场出发到第j个机场的能买到的航班的最低票价t（0 < t < 10000）。如果不幸没有航班，那么用-1表示。第i行第i个整数为0。 起点华盛顿杜勒斯国际机场的编号为1，终点北京首都国际机场的编号为N。
输出
每一个case一行。 能够回国，输出字符串：YES。如果无法回国，输出字符串：NO
样例输入
```
2
3
0 100 -1
-1 0 200
-1 -1 0
4
0 1 5 -1
3 0 1 -1
2 4 0 -1
4 1 1 0
```
样例输出
```
YES
NO
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道典型的图论问题，可以使用Dijkstra算法求解。首先，我们需要从输入中读取机场个数N和各个机场之间的航班情况，存储在二维数组prices中。其中，prices[i][j]表示从第i个机场出发到第j个机场的航班最低票价，如果没有航班，则prices[i][j]为-1。然后，我们需要使用Dijkstra算法找到从华盛顿出发到北京的最短路径。具体实现时，我们可以使用一个二维数组paths来存储从每个机场出发到每个机场的最短路径长度，初始时所有路径长度都为-1。然后，我们遍历所有的机场，对于每个机场，我们遍历所有的航班，如果存在从当前机场出发到目标机场的航班，则更新paths数组。接下来，我们使用Dijkstra算法找到从华盛顿出发到北京的最短路径。具体实现时，我们可以使用一个一维数组dist来存储从华盛顿出发到每个机场的最短路径长度，初始时所有路径长度都为无穷大。然后，我们遍历所有的机场，对于每个机场，我们找到当前未访问过的机场中路径长度最短的机场，然后更新其邻居机场的最短路径长度。最后，我们判断是否能够回国，如果能够回国，则输出字符串"YES"，否则输出字符串"NO"。具体实现时，我们可以判断dist[N-1]是否等于无穷大，如果不等于无穷大，则说明能够回国，否则无法回国。
2、2.通配符匹配
给定一个字符串s和一个字符模式p，请实现一个支持'?'和'*'的通配符匹配功能。
其中‘?’可以匹配任何单个字符，如‘a?c’可以成功匹配‘aac’,‘abc’等字符串，但不可匹配‘ac’,‘aaac’等字符串 。
‘*’ 可以匹配任意长度字符串（包括空字符串）,如‘a*c’可以成功匹配‘ac’,‘abdc’,‘abc’,‘aaac’等字符串，但不可匹配‘acb’，‘cac’等字符串。
两个字符串完全匹配才算匹配成功。
时间限制：2000
内存限制：262144
输入
输入为一个数字n表示测试字符串与字符模式对数，换行。(n ≤ 30) 后续2n行为每组匹配的s与p，每行字符串后换行。 s 非空，只包含从 a-z 的小写字母。 p 非空，只包含从 a-z 的小写字母，以及字符 ? 和 *。 字符串s和p的长度均小于50
输出
每一组匹配串匹配成功输出‘yes’,否则输出‘no’。
样例输入
```
3
abc
abc
abc
a*c
abc
a??c
```
样例输出
```
yes
yes
no
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道经典的动态规划问题，可以使用动态规划算法来解决。首先，我们定义一个二维数组dp，其中dp[i][j]表示字符串s的前i个字符和字符串p的前j个字符是否匹配。然后，我们根据题目中给出的通配符匹配规则，进行状态转移。对于字符串p的第j个字符，如果它是‘?’，则可以匹配字符串s的第i个字符，此时dp[i][j] = dp[i-1][j-1]。如果字符串p的第j个字符是‘*’，则可以匹配字符串s的第i个字符，也可以不匹配，此时dp[i][j] = dp[i-1][j] or dp[i][j-1]。最后，返回dp[m][n]，其中m和n分别是字符串s和p的长度。在代码中，我们使用了动态规划的思想，通过状态转移方程，逐步计算出dp数组的值，最终得到结果。需要注意的是，对于字符串p的第0个字符，即空字符串，我们需要单独处理。当字符串p的第0个字符是‘*’时，它可以匹配字符串s的任意前缀，因此dp[0][j] = dp[0][j-1]。在输入部分，我们使用input()函数从标准输入中读取输入数据，并进行处理。在输出部分，我们使用print()函数将结果输出到标准输出中。
3、3.求逆序对数
对于一个长度为N的整数序列A，满足i < j 且 Ai > Aj.的数对(i,j)称为整数序列A的一个逆序
请求出整数序列A的所有逆序对个数
时间限制：500
内存限制：65536
输入
输入包含多组测试数据，每组测试数据有两行 第一行为整数N(1 <= N <= 20000)，当输入0时结束 第二行为N个整数，表示长为N的整数序列
输出
每组数据对应一行，输出逆序对的个数
样例输入
```
5
1 2 3 4 5
5
5 4 3 2 1
1
1
0
```
样例输出
```
0
10
0
```
参考答案：
略
解析：【喵呜刷题小喵解析】本题要求计算一个整数序列的逆序对个数。逆序对是指在一个序列中，满足i < j且A[i] > A[j]的数对(i, j)。首先，我们读入一个整数N，表示序列的长度。然后，我们读入N个整数，表示序列的元素。接着，我们使用两层循环遍历序列，计算逆序对的个数。具体地，对于每一个i，我们遍历i+1到N-1之间的所有j，如果A[i] > A[j]，则计数器count加1。最后，我们输出count，表示逆序对的个数。由于本题存在多组测试数据，我们需要使用循环来读入每一组数据，并输出对应的逆序对个数。当读入的N为0时，表示输入结束，我们退出循环。需要注意的是，本题的时间限制和内存限制比较严格，因此我们需要尽可能优化算法。在本题中，我们可以使用归并排序的思想，将序列分成两部分，分别计算逆序对个数，然后将两部分合并，计算合并过程中的逆序对个数。这样可以避免使用两层循环，从而提高算法的效率。
4、4.分成互质组
给定n个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？
时间限制：1000
内存限制：65536
输入
第一行是一个正整数n。1 <= n <= 10。 第二行是n个不大于10000的正整数。
输出
一个正整数，即最少需要的组数。
样例输入
```
6
14 20 33 117 143 175
```
样例输出
```
3
```
参考答案：
略
解析：【喵呜刷题小喵解析】这个题目要求将给定的n个正整数分成若干组，使得每组中任意两个数互质。互质指的是两个数除了1以外没有其他公约数。我们需要求出最少需要的组数。解决这个问题的一种方法是尝试将每个数字加入已经存在的组，或者创建新的组。首先，我们遍历每个数字，然后检查它是否可以和已经存在的组中的任何数字互质。如果可以，我们将它加入该组；否则，我们创建一个新的组，只包含这个数字。在C++中，我们可以使用`vector`来存储数字和组。对于每个数字，我们遍历所有的组，检查它是否可以和组中的任何数字互质。我们可以使用欧几里得算法（辗转相除法）来计算两个数字的最大公约数。如果最大公约数大于1，那么这两个数字不是互质的。最后，我们输出组的数量，这就是最少需要的组数。在样例输入中，数字14、20、117和175不能和其他数字互质，所以它们各自形成一组；数字33和143可以互质，所以它们形成一组。因此，最少需要的组数是3。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
