一、编程题
1、谁是你的潜在朋友
“臭味相投”——这是我们描述朋友时喜欢用的词汇。两个人是朋友通常意味着他们存在着许多共同的兴趣。然而作为一个宅男，你发现自己与他人相互了解的机会并不太多。幸运的是，你意外得到了一份北大图书馆的图书借阅记录，于是你挑灯熬夜地编程，想从中发现潜在的朋友。 首先你对借阅记录进行了一番整理，把N个读者依次编号为1,2,…,N，把M本书依次编号为1,2,…,M。同时，按照"臭味相投"的原则，和你喜欢读同一本书的人，就是你的潜在朋友。你现在的任务是从这份借阅记录中计算出每个人有几个潜在朋友。
时间限制：1000
内存限制：65536
输入
第一行两个整数N,M，2 <= N ，M<= 200。接下来有N行，第i(i = 1,2,…,N)行每一行有一个数，表示读者i-1最喜欢的图书的编号P(1<=P<=M)
输出
包括N行，每行一个数，第i行的数表示读者i有几个潜在朋友。如果i和任何人都没有共同喜欢的书，则输出"BeiJu"（即悲剧，^ ^）
样例输入
4 5
2
3
2
1
样例输出
1
BeiJu
1
BeiJu
参考答案：
无
解析：【喵呜刷题小喵解析】首先，我们读取输入，获取读者数量和图书数量。然后，我们创建一个字典`books`，用于存储每本书对应的读者列表。接下来，我们遍历每个读者，获取他们最喜欢的图书编号，并将其添加到对应的图书列表中。然后，我们创建一个列表`friends`，用于存储每个读者的潜在朋友数量。我们遍历每个读者，对于他最喜欢的每本书，我们检查是否有其他读者也喜欢这本书。如果有，那么我们将其他读者的数量加到这个读者的`friends`列表中，但要减去1，因为当前读者自己不需要和自己成为朋友。最后，我们遍历每个读者的`friends`列表，如果数量为0，表示他没有任何潜在朋友，我们输出" BeiJu"；否则，我们输出潜在朋友的数量。
2、课程冲突
小 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门课程中冲突程度最大的两门课的冲突程度。首先，我们需要读取输入的课程信息，每门课程用两个整数ai和bi表示，表示这门课从第ai天一直上到第bi天。然后，我们需要遍历所有课程对，计算它们之间的冲突程度。对于每一对课程，我们遍历每一天，如果这一天同时在这两门课程的上课时间内，那么冲突程度就加1。最后，我们找出所有课程对中的最大冲突程度，并输出。在Python中，我们可以使用列表来存储课程信息，使用嵌套循环来遍历所有课程对，使用另一个循环来遍历每一天。需要注意的是，由于课程的天数范围在1到1000之间，所以我们可以直接遍历每一天，而不需要使用额外的数据结构来存储每一天的上课情况。时间复杂度为O(n^2 * 1000)，其中n为课程数量。这个算法的时间复杂度比较高，但是对于本题的数据规模（n<=1000）来说，是可以接受的。需要注意的是，由于题目要求输出最大的冲突程度，所以我们需要在遍历所有课程对的过程中，实时更新最大冲突程度。此外，还需要注意的是，输入的数据可能会非常大，因此需要使用较快的数据结构，比如Python的内置数据类型，而不是使用额外的数据结构来存储数据。
3、踩方格
有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设：
a. 每走一步时，只能从当前方格移动一格，走到某个相邻的方格上；
b. 走过的格子立即塌陷无法再走第二次；
c. 只能向北、东、西三个方向走；
请问：如果允许在方格矩阵上走n步，共有多少种不同的方案。2种走法只要有一步不一样，即被认为是不同的方案。
时间限制：1000
内存限制：65536
输入
允许在方格上行走的步数n(n <= 20)
输出
计算出的方案数量
样例输入
2
样例输出
7
参考答案：
无
解析：【喵呜刷题小喵解析】本题是一个经典的动态规划问题，可以使用动态规划算法来解决。首先，我们定义一个数组dp，其中dp[i]表示走i步的方案数。根据题目要求，dp[0]为1，表示走0步的方案数为1，即原地不动。dp[1]为3，表示走1步的方案数为3，即向北、东、西三个方向走。对于走i步的方案数，我们可以根据走i-1步的方案数来推导。由于只能向北、东、西三个方向走，所以走i步的方案数等于走i-1步的方案数乘以3。因此，我们可以得到状态转移方程：dp[i] = 3 * dp[i - 1]。最后，我们只需要计算dp[n]即可得到走n步的方案数。注意，由于题目要求时间限制和内存限制，我们需要使用动态规划算法来优化计算过程，避免重复计算。
4、迷信的病人
医院为了方便对患者进行建档和管理，引入了9位整数ID号来标识每个病人。最近医院入住了一个迷信的病人，他认为ID号的好坏直接决定了自己的命运。他对ID号x有如下要求:
（1）x的前三位数构成的整数是素数
（2）x的后三位数构成的整数是平方数（所谓平方数，是指它是某一个正整数的平方，e.g. 1,4,9,16…）
（3）x中不包含"13"
为了避免不必要的医患矛盾，医院须尽量满足他的需求。现给定正整数区间[m,n]，请你判断存在几个满足病人需求的ID号。
时间限制：1000
内存限制：65536
输入
两个正整数m，n，以空格隔开。(999999999>=n>=m>=111111111)
输出
一个整数（满足要求的ID的个数）。
样例输入
157689476 157689687
样例输出
5
提示
存在5个满足要求的ID：157689484,157689529,157689576,157689625,157689676
参考答案：
无
解析：【喵呜刷题小喵解析】：本题要求在给定的整数区间[m, n]内，找出满足特定条件的整数ID个数。这些ID需要满足以下三个条件：1. ID的前三位数构成的整数是素数。2. ID的后三位数构成的整数是平方数。3. ID中不包含"13"。我们可以使用Python编写一个程序来解决这个问题。首先，我们需要定义两个辅助函数：1. `is_prime(n)`：判断一个整数n是否为素数。2. `is_square(n)`：判断一个整数n是否为平方数。然后，我们可以编写一个函数`count_ids(m, n)`，它遍历整数区间[m, n]内的每个整数，检查每个整数是否满足上述三个条件。如果满足条件，计数器`count`加1。最后，我们打印出满足条件的ID个数。在Python中，我们可以使用`map()`函数将输入的字符串转换为整数，然后使用`split()`函数将输入的字符串按空格分割。注意，由于题目中给出的整数范围很大，我们需要在遍历整数时进行优化，以避免超时。我们可以使用循环变量`i`直接遍历整数，而不是将每个整数转换为字符串进行检查。这样可以减少字符串转换和字符串操作的时间复杂度，提高程序的效率。
5、Pell数列
Pell数列a1, a2, a3, …的定义是这样的，a1 = 1, a2 = 2, … , an = 2 * an − 1 + an - 2 (n > 2)。 给出一个正整数k，要求Pell数列的第k项模上32767是多少。
时间限制：3000
内存限制：65536
输入
第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。
输出
n行，每行输出对应一个输入。输出应是一个非负整数。
样例输入
2
1
8
样例输出
1
408
参考答案：
无
解析：【喵呜刷题小喵解析】根据题目描述，Pell数列的定义是a1 = 1, a2 = 2, an = 2 * an - 1 + an - 2 (n > 2)。对于每一组输入k，我们需要计算出Pell数列的第k项模上32767的结果。由于k的值可能很大，直接计算Pell数列的第k项可能会超时。因此，我们可以使用递推的方式来计算Pell数列的第k项。具体地，我们可以使用三个变量a1, a2, a3来分别表示Pell数列的第1项、第2项、第3项。初始时，a1 = 1, a2 = 2。然后，我们根据Pell数列的定义，每次计算出一项新的数，并更新a1, a2, a3的值。当k > 2时，我们可以使用递推式an = 2 * an - 1 + an - 2来计算Pell数列的第n项。由于我们只关心Pell数列的第k项模上32767的结果，所以在每次计算新的数时，我们都需要取模。当k = 2时，Pell数列的第2项就是a2。当k = 1时，Pell数列的第1项就是a1。最后，我们输出Pell数列的第k项模上32767的结果即可。由于题目要求输出非负整数，因此在输出时，我们需要确保输出的结果是非负的。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
