一、编程题
1、1.菲波那契数列
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1，接下来每个数都等于前面2个数之和。
给出一个正整数a，要求菲波那契数列中第a个数对10000取模的结果是多少。
时间限制：1000
内存限制：65536
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数a(1 <= a <= 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第a个数对10000取模得到的结果。
样例输入
4
5
2
19
1
样例输出
5
1
4181
1
参考答案：
略
解析：【喵呜刷题小喵解析】首先，我们需要读取输入的测试数据的组数n，然后对于每组测试数据，我们读取正整数a。对于每个a，我们创建一个列表fib，初始化为[0, 1, 1]，分别表示数列的前三个数。然后，我们循环计算数列中的下一个数，直到计算出第a个数。具体来说，我们从第3个数开始循环，每次将当前数列的倒数第二个数和倒数第三个数相加，得到新的数，然后将新的数添加到数列的末尾。最后，我们输出第a个数对10000取模的结果。注意，由于a的值可能很大，我们需要使用列表来存储数列，而不是使用递归的方式计算数列。否则，递归的方式可能会导致栈溢出。另外，由于每次计算下一个数都需要对10000取模，我们可以直接在计算过程中取模，避免在循环结束后再次取模。
2、2.广义格雷码
在一组数的编码中，若任意两个相邻（首尾也视为相邻）的代码只有一位二进制数不同，则称这种编码为格雷码。如四位格雷码：
0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000
现在将格雷码扩展至其他进制，仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制，每行输出一个n位m进制数，输出任意一种编码即可。（提示：putchar输出效率更高）
时间限制：1000
内存限制：65536
输入
一行，两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000
输出
任意一种编码方案，每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻
样例输入
2 3
样例输出
00
10
20
21
01
11
12
22
02
参考答案：
略
解析：【喵呜刷题小喵解析】1. **解题思路**：* 首先，我们需要理解格雷码的性质：任意两个相邻的代码只有一位二进制数不同。* 格雷码可以通过递归的方式生成，从二进制格雷码扩展到其他进制的格雷码。* 对于m进制的格雷码，我们可以先生成一个m位的二进制格雷码，然后将其转换为m进制。2. **代码解析**：* `scanf("%d%d", &n, &m);`：从标准输入读取n和m的值。* `int a[m][m], idx = 0;`：定义一个m*m的二维数组a用于存储m进制的格雷码，idx用于记录当前生成的格雷码的位置。* `for (int i = 0; i < m; i++) { ... }`：初始化m进制的格雷码表。* `for (int i = 0; i < (1 << n); i++) { ... }`：生成n位的m进制格雷码。* `int num = 0;`：用于存储当前生成的m进制格雷码。* `for (int j = 0; j < n; j++) { ... }`：将二进制格雷码转换为m进制格雷码。* `printf("%0*d\n", n, num);`：输出生成的m进制格雷码。这段代码的主要思想是先生成m进制的二进制格雷码，然后将其转换为m进制格雷码，满足了题目要求的“任意两个相邻的代码只有一位二进制数不同”。
3、3.课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制：1000
内存限制：65536
输入
第一行一个正整数 n 表示课程数量。 接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ ai ≤ bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度
样例输入
3
1 3
2 4
5 5
样例输出
2
参考答案：
略
解析：【喵呜刷题小喵解析】本题是一道编程题，要求找出n门课程中最大冲突程度的两门课程的冲突程度。首先，从输入中读取课程的数量n和每门课程的起始和结束时间。将每门课程存储为一个元组(a, b)，其中a是课程的起始时间，b是课程的结束时间。然后，使用两层循环遍历所有课程对，计算每对课程的冲突程度。对于每对课程，使用一个循环遍历所有天数，如果某一天同时在这两门课程的上课时间内，则冲突程度加1。最后，将最大的冲突程度输出到标准输出中。需要注意的是，由于课程的时间范围较小（1 ≤ ai ≤ bi ≤ 1000），因此可以使用一个循环遍历所有天数来计算冲突程度，而不必使用线段树等数据结构。另外，由于题目要求输出最大的冲突程度，因此在计算每对课程的冲突程度时，需要记录最大的冲突程度，并在计算完所有课程对后输出该值。
4、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，说明已经生成了n对括号，且没有多余的左括号，此时将cur加入到结果res中。3. 如果n大于0，说明还需要生成n对括号，此时可以选择生成一个左括号，即调用generate(n-1, open+1, cur+"(", res)。4. 如果open大于0，说明当前已经生成的括号组合中左括号数量大于右括号数量，此时可以选择生成一个右括号，即调用generate(n, open-1, cur+")", res)。5. 在主函数中，首先读入n，然后调用generate(n, 0, "", res)生成所有合法的括号组合，最后遍历res输出每个组合。时间复杂度为O(n*2^n)，空间复杂度为O(2^n)。
5、5.余数相同问题
参考答案：
略
解析：【喵呜刷题小喵解析】本题要求找到一个小于等于n的正整数i，使得n除以i的余数为2。我们可以使用循环遍历1到n之间的所有正整数，找到第一个满足条件的数。如果找到了符合条件的数，就返回这个数；否则返回None。在Python中，我们可以定义一个函数`find_number(n)`来实现这个算法。在函数中，我们使用一个循环遍历1到n之间的所有正整数，对于每个数i，判断n除以i的余数是否为2。如果是，就返回这个数i；否则继续循环。最后，我们在主程序中读取用户输入的正整数n，调用`find_number(n)`函数，并将结果输出到屏幕上。如果找到了符合条件的数，就输出这个数；否则输出"没有找到符合条件的最小正整数"。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
