一、简答题
1、谷歌的招聘
2004年7月，谷歌在硅谷的101号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。
自然常数 e 是一个著名的超越数，前面若干位写出来是这样的：e = 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 10 位数就是答案。
本题要求你编程解决一个更通用的问题：从任一给定的长度为 L 的数字中，找出最早出现的 K 位连续数字所组成的素数。
时间限制：7000
内存限制：65535
输入
输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和 K（小于10的正整数）。接下来一行给出一个长度为 L 的正整数 N。
输出
在一行中输出 N 中最早出现的 K 位连续数字所组成的素数。如果这样的素数不存在，则输出“404”。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023 算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。
样例输入
样例1：
20 5 23654987725541023819
样例2：
10 3 2468024680
样例输出
样例1：
49877
样例2：
404
参考答案：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
bool is_prime(int num); // 判断是否为素数的函数声明
int main() {
int L, K; // 数字长度和连续数字位数
scanf("%d %d", &L, &K); // 输入数字长度和连续数字位数
char num[L + 1]; // 存储输入的数，多加一个字符用于存储字符串结束符'\0'
scanf("%s", num); // 输入数字字符串
int start = 0; // 从数字字符串的起始位置开始查找连续的K位数字
while (start + K <= L) { // 当找到的数字长度大于等于K位时继续查找
int num_K = atoi(num + start); // 将找到的K位数字转换为整数
if (is_prime(num_K)) { // 如果找到的K位数字是素数，则输出并结束程序
printf("%d", num_K);
return 0;
}
start++; // 未找到素数，继续查找下一个K位数字
}
printf("404"); // 未找到符合条件的素数，输出404
return 0;
}
bool is_prime(int num) { // 判断一个数是否为素数
if (num < 2) return false; // 小于2的数不是素数
int sqrt_num = sqrt(num); // 素数一定小于等于它的平方根，只需判断到它的平方根即可
for (int i = 2; i <= sqrt_num; i++) { // 判断num是否为素数
if (num % i == 0) return false; // 存在因子则不是素数
}
return true; // 没有因子则是素数
}
2、吉利矩阵
所有元素为非负整数，且各行各列的元素和都等于 7 的 3x3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。
本题就请你统计一下，把 7 换成任何一个 [2, 9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2, 4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 NxN 方阵一共有多少种？
时间限制：6000
内存限制：65535
输入
输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。
输出
在一行中输出满足题目要求条件的方阵的个数。
样例输入
7 3
样例输出
666
参考答案：
吉利矩阵的数量需要根据给定的参数L和N进行计算。由于题目给出的矩阵元素是非负整数，我们可以使用枚举法来求解。对于每一个可能的矩阵，我们需要检查其元素是否满足条件：所有元素为非负整数，且各行各列的元素和都等于给定的L值。对于给定的L和N，我们可以生成所有可能的矩阵组合，并计算满足条件的矩阵数量。最终输出满足条件的矩阵个数即可。具体实现需要使用循环和条件判断语句。需要注意的是，由于时间限制和内存限制的存在，我们需要优化算法效率，避免不必要的计算和内存占用。
3、胖达与盆盆奶
大熊猫，俗称“胖达”，会排队吃盆盆奶。它们能和谐吃奶的前提，是它们认为盆盆奶的分配是“公平”的，即：更胖的胖达能吃到更多的奶，等胖的胖达得吃到一样多的奶。另一方面，因为它们是排好队的，所以每只胖达只能看到身边胖达的奶有多少，如果觉得不公平就会抢旁边小伙伴的奶吃。
已知一只胖达每次最少要吃 200 毫升的奶，当另一份盆盆奶多出至少 100 毫升的时候，它们才能感觉到是“更多”了，否则没感觉。
现在给定一排胖达的体重，请你帮饲养员计算一下，在保持给定队形的前提下，至少应该准备多少毫升的盆盆奶？
时间限制：6000
内存限制：65535
输入
输入首先在第一行给出正整数 n（≤ 104），为胖达的个数。随后一行给出 n 个正整数，表示 n 只胖达的体重（公斤）。每个数值是不超过 200 的正整数，数字间以空格分隔。
输出
在一行中输出至少应该准备多少毫升的盆盆奶。
样例输入
10 180 160 100 150 145 142 138 138 138 140
样例输出
3000
提示
样例解释： 盆盆奶的分配量顺序为： 400 300 200 500 400 300 200 200 200 300
参考答案：
需要准备的盆盆奶总量至少为每一只胖达最少需要的奶量（即每只胖达至少200毫升）的总和，再加上一些额外的奶量以应对胖达们对公平性的感知。根据题目的描述，我们知道只有当另一份盆盆奶多出至少100毫升的时候，胖达才会感觉到是"更多"。因此，我们可以按照体重从大到小的顺序分配盆盆奶，使得每相邻的两个胖达之间的奶量差距不超过100毫升。具体实现时可以使用贪心算法。
4、加号放哪里
给定任一个正整数 N，我们要从它开始，经过一系列操作得到一个个位数。操作方法是在 N 的各位数字之间放置一个加号，然后执行这个加法计算，得到一个新的数字 N1，再对 N1 执行同样操作，得到 N2 …… 以此类推，直到最后得到的数字只有 1 位，则停止。
例如我们从 N=1234567890 出发，在 5 和 6 之间放置加号，计算 12345+67890=80235；然后在 0 和 2 之间放置加号，计算 80+235=315；然后在 1 和 5 之间放置加号，计算 31+5=36；最后在 3 和 6 之间放置加号，得到 3+6=9 而停止。这样我们通过 4 次计算得到了一个个位数 9。
本题就请你为任一给定的正整数计算：最少需要多少次加号放置可以得到个位数？
注意：加号必须放置在两个数字之间，不可放置在数字的首尾。
时间限制：7000
内存限制：65536
输入
输入在一行中给出一个正整数 n（≤ 1020）。
输出
在一行中首先输出将输入的整数变为个位数，需要放置加号的最少次数；随后输出最后得到的那个个位数。如果最后得到的个位数不唯一，输出最小的那个。 数字间以 1 个空格分隔，行首尾不得有多余空格。
样例输入
1234567890
样例输出
3 9
提示
样例解释： 最优划分是： 1. 12345678+90=12345768 2. 1234+5768=7002 3. 7+002=9
参考答案：
最少需要放置加号的最多次数可以通过模拟计算得出，最终得到的个位数可以通过一系列计算得到。具体实现需要使用贪心算法和模拟计算。
5、三足鼎立
当三个国家中的任何两国实力之和都大于第三国的时候，这三个国家互相结盟就呈“三足鼎立”之势，这种状态是最稳定的。
现已知本国的实力值，又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟，以成三足鼎立。有多少种选择呢？
时间限制：10000
内存限制：65536
输入
输入首先在第一行给出 2 个正整数 n（2 ≤ n ≤ 105）和 P（≤ 109），分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数，表示n 个其他国家的实力值。每个数值不超过 109，数字间以空格分隔。
输出
在一行中输出本国结盟选择的个数。
样例输入
7 30 42 16 2 51 92 27 35
样例输出
9
提示
样例解释： 能联合的另外 2 个国家的 9 种选择分别为： {16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
