一、编程题
1、和数
给定一个正整数序列，判断其中有多少个数，等于数列中其他两个数的和。 比如，对于数列1 2 3 4, 这个问题的答案就是2, 因为3 = 2 + 1, 4 = 1 + 3。
时间限制：10000
内存限制：65536
输入
共两行，第一行是数列中数的个数n ( 1 <= n <= 100)，第二行是由n个不大于10000的正整数组成的数列，相邻两个整数之间用单个空格隔开。
输出
一个整数，即数列中等于其他两个数之和的数的个数。
样例输入
4
1 2 3 4
样例输出
2
参考答案：
无
解析：【喵呜刷题小喵解析】：这是一个经典的编程题，主要考察对算法的理解和实现。首先，我们从题目中知道需要找出一个正整数序列中，等于数列中其他两个数之和的数的个数。这是一个典型的三重循环问题，外层循环遍历每个数，然后内层循环遍历所有可能的数对，检查当前数是否等于这两个数之和。如果等于，则计数器加1。具体实现上，我们首先从输入中读取数列的长度n和数列本身。然后，我们使用三重循环遍历所有可能的数对，检查当前数是否等于这两个数之和。如果等于，则将计数器加1。最后，我们将计数器的值输出即可。时间复杂度方面，由于我们使用了三重循环，时间复杂度为O(n^3)，其中n为数列的长度。由于题目中限制了n的最大值为100，因此这个算法可以在规定的时间内完成。空间复杂度方面，我们只需要存储输入的数列，因此空间复杂度为O(n)。由于题目中限制了数列中每个数的最大值为10000，因此这个算法可以在规定的内存限制内完成。
2、质数的和与积
两个质数的和是S，它们的积最大是多少？
时间限制：10000
内存限制：65536
输入
一个不大于10000的正整数S，为两个质数的和。
输出
一个整数，为两个质数的最大乘积。数据保证有解。
样例输入
50
样例输出
589
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求找到两个质数，它们的和是S，然后求出这两个质数的最大乘积。首先，我们需要一个函数来判断一个数是否为质数。这个函数的实现方法是，从2开始，依次判断这个数是否能被2到它的平方根之间的任何整数整除，如果能，则不是质数，否则是质数。然后，我们需要遍历所有小于S的质数，对于每个质数i，我们再遍历所有大于等于i且小于S的质数j，如果i和j的和等于S，则更新最大乘积。最后，我们读取输入的S，调用max_product函数，输出最大乘积。需要注意的是，由于题目要求S不大于10000，所以我们可以遍历所有小于S的质数，时间复杂度是O(S*logS)，是可以接受的。
3、爬楼
已知楼梯的数量，可以每次走2级或者3级，求不同的走法数
例如：楼梯一共有7级，一共3种方法：2 2 3或者 2 3 2 或者 3 2 2。
时间限制：1000
内存限制：65536
输入
输入包含若干行，每行包含一个正整数N，代表楼梯级数，1 <= N <= 50。 最后一行为0，表示测试结束。
输出
不同的走法数，每一行输入对应一行输出
样例输入
7
0
样例输出
3
参考答案：
无
解析：【喵呜刷题小喵解析】这是一个经典的动态规划问题，可以使用动态规划算法来解决。我们定义一个数组`dp`，其中`dp[i]`表示楼梯有`i`级时不同的走法数。根据题目，楼梯可以每次走2级或者3级，因此我们可以得到状态转移方程：`dp[i] = dp[i - 1] + dp[i - 2]`，即走法数等于走`i-1`级楼梯的走法数加上走`i-2`级楼梯的走法数。我们可以初始化`dp[1]`为1，`dp[2]`为2，然后依次计算`dp[3]`，`dp[4]`，`dp[5]`等，直到`dp[n]`。最后输出`dp[n]`即可。注意，在输入时，需要判断输入是否为0，如果是0则结束程序。此代码的时间复杂度为O(n)，空间复杂度也为O(n)，满足题目要求。
4、生成括号
Paul是一名数学专业的同学，在课余选修了C++编程课，现在他能够自己写程序判断判断一个给定的由’(‘和’)’组成的字符串是否是正确匹配的。可是他不满足于此，想反其道而行之，设计一个程序，能够生成所有合法的括号组合，请你帮助他解决这个问题。
时间限制：1000
内存限制：65536
输入
输入只有一行N，代表生成括号的对数（1 ≤ N ≤ 10)。
输出
输出所有可能的并且有效的括号组合，按照字典序进行排列，每个组合占一行。
样例输入
3
样例输出
((()))
(()())
(())()
()(())
()()()
参考答案：
无
解析：【喵呜刷题小喵解析】本题要求生成所有合法的括号组合，按照字典序进行排列，每个组合占一行。可以使用递归的方式来解决这个问题。具体思路如下：1. 定义一个递归函数generate(n, open, cur, res)，其中n表示剩余的括号对数，open表示当前已经使用的左括号数量，cur表示当前已经生成的括号组合，res表示最终的结果。2. 如果open为0且n也为0，说明已经生成了一个合法的括号组合，将其加入结果res中。3. 如果n大于0，说明还需要生成更多的括号组合，此时可以选择生成一个左括号，即调用generate(n-1, open+1, cur+"(", res)。4. 如果open大于0，说明已经使用了左括号，此时可以选择生成一个右括号，即调用generate(n, open-1, cur+")", res)。5. 在主函数中，首先读入剩余的括号对数n，然后调用generate(n, 0, "", res)生成所有合法的括号组合，最后遍历结果res并输出。需要注意的是，在递归的过程中，需要保证open的数量始终大于等于0，否则就会出现不合法的括号组合。
5、铺砖
对于一个2行N列的走道。现在用1*2,2*2的砖去铺满。问有多少种不同的方式。
时间限制：3000
内存限制：131072
输入
整个测试有多组数据，请做到文件底结束。每行给出一个数字N，0 <= n <= 250
输出
如题
样例输入
2
8
12
100
200
样例输出
3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251
参考答案：
无
解析：【喵呜刷题小喵解析】这个问题是一个经典的动态规划问题，可以使用动态规划来解决。首先，我们定义一个数组dp，其中dp[i]表示用1*2和2*2的砖铺满一个2行i列的走道有多少种不同的方式。然后，我们可以发现，对于dp[i]，它可以通过dp[i-1]和dp[i-2]计算出来。具体来说，dp[i]等于dp[i-1]和dp[i-2]的和，因为我们可以选择使用1*2的砖铺满最后一列，也可以选择使用2*2的砖铺满最后两列。最后，我们只需要遍历计算出dp数组，然后输出dp[n]即可。在Python中，我们可以使用以下代码实现：```pythondef count_ways(n):dp = [0] * (n + 1)dp[0] = 1dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]for _ in range(int(input())):n = int(input())print(count_ways(n))```其中，`int(input())`用于读入多组测试数据，`int(input())`用于读入每一组测试数据中的n。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
