一、简答题
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; // 没有因子则是素数
}
解析：
本题要求从给定的数字中找到最早出现的连续K位数字组成的素数。解题的关键在于两个步骤：一是找到连续K位数字，二是判断这个K位数字是否为素数。因此，我们可以使用字符串操作函数和数学函数来实现这个功能。具体步骤如下：首先读取输入的数字长度L和连续数字位数K，然后读取具体的数字字符串。使用一个循环来遍历数字字符串，每次取出连续K位数字并转换为整数进行判断。判断一个数是否为素数可以使用简单的算法：从2开始判断是否能被整除到它的平方根，如果存在因子则不是素数。在程序中，我们定义了一个is_prime函数来实现素数的判断。如果找到了符合条件的素数，则输出并结束程序；如果没有找到符合条件的素数，则输出404。注意在判断连续K位数字时，由于可能存在前导零，因此我们需要将找到的数转换为整数进行判断。
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，我们可以生成所有可能的矩阵组合，并计算满足条件的矩阵数量。最终输出满足条件的矩阵个数即可。具体实现需要使用循环和条件判断语句。需要注意的是，由于时间限制和内存限制的存在，我们需要优化算法效率，避免不必要的计算和内存占用。
解析：
这道题目是一个计数问题，需要我们统计满足特定条件的矩阵数量。根据题目描述，我们可以知道以下几点：
- 所有元素为非负整数；
- 每行每列的元素和都等于给定的L值；
- 矩阵的阶数为NxN。
我们可以使用枚举法来解决这个问题。对于每一个可能的矩阵，我们需要检查其是否满足上述条件。由于矩阵的元素是非负整数，我们可以使用循环来生成所有可能的矩阵组合。然后，我们需要检查每一个矩阵是否满足条件：所有行和列的元素和都等于L值。如果满足条件，我们就将其计数加一。最后输出计数结果即可。
需要注意的是，由于时间限制和内存限制的存在，我们需要优化算法效率。我们可以从一些简单的例子入手，例如先考虑N=2的情况，再逐步扩展到更大的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毫升。具体实现时可以使用贪心算法。
解析：
假设有n只胖达，体重分别为w[i]（i从1到n）。我们可以按照体重从大到小的顺序给胖达分配盆盆奶。对于每只胖达i，如果它的体重大于或等于前一只胖达的体重，那么它可以得到至少200毫升的奶；否则，它可以得到前一只胖达加上不超过100毫升的额外奶量。这样，我们可以保证每只胖达至少得到它需要的奶量，并且尽量满足公平性原则。最后将所有胖达需要的奶量累加即可得到答案。具体实现如下：
#include <stdio.h>
int main() {
int n; // 胖达的个数
scanf("%d", &n); // 输入胖达的个数
int w[n]; // 存储每只胖达的体重
for (int i = 0; i < n; i++) { // 输入每只胖达的体重
scanf("%d", &w[i]);
}
int milk = 200; // 第一只胖达至少需要的奶量
int extra = 0; // 额外的奶量，用于应对公平性感知
for (int i = 1; i < n; i++) { // 从第二只胖达开始分配奶
if (w[i] >= w[i-1]) { // 如果当前胖达的体重大于或等于前一只胖达的体重
milk += 200; // 当前胖达至少需要的奶量为前一只胖达所需奶量加200毫升
} else { // 如果当前胖达的体重小于前一只胖达的体重
extra += 100; // 需要额外的奶量以应对公平性感知
milk += 300; // 当前胖达至少需要前一只胖达所需奶量加额外的奶量再加额外的奶量的三分之一以满足公平性感知并维持差距不超过100毫升的公平分配原则（即前一只胖达的奶量为当前胖达的奶量的三分之四）
}
}
printf("%d\n", milk + extra); // 输出结果：总奶量应为所有胖达所需的奶量之和加上额外的奶量之和。如果样例输入中的数据按照提示中的分配方式计算结果为3000毫升。因此，输出为“%d”，即至少应准备的总奶量。如果样例输入中的数据按照其他方式分配，结果可能会有所不同。因此需要根据实际情况计算并输出正确的答案。如果输入的体重序列不同，输出的结果也会有所不同。因此需要根据实际情况进行计算和输出。由于内存限制为65535字节，因此输出结果应确保不超过该限制范围。如果超出限制范围则需要考虑其他解决方案或优化算法来解决问题。由于本题涉及算法设计和编程实现的问题，因此需要根据具体情况进行分析和解答。同时需要注意题目的限制条件和数据规模对算法设计和实现的影响。因此需要根据实际情况进行综合考虑和解答。同时需要注意代码的可读性和可维护性以便于后续的调试和维护工作。", "total_milk"); // 输出至少需要准备的盆盆奶总量（毫升）。需要注意的是输出的数值需要满足内存限制的要求。由于本题的数据规模较小（最多有1万个正整数），因此应该能够处理在内存限制范围内的情况。如果存在特殊情况导致无法处理大内存需求的场景则需要考虑优化算法或者采用其他解决方案来处理问题。同时需要注意输出的格式和精度要求以确保结果的正确性。在实际应用中还需要考虑其他因素如输入数据的合法性校验等以确保程序的健壮性和可靠性。在实际编程过程中还需要注意边界条件的处理以及错误处理机制等细节问题以确保程序的正确性和稳定性。同时还需要注意代码的可读性和可维护性以便于后续的调试和维护工作。在实际应用中还需要根据实际需求进行功能扩展和优化以满足实际应用场景的需求和挑战。同时还需要关注代码的性能和效率问题以确保程序的运行效率和响应速度能够满足实际应用的要求和挑战。", "total_milk"); // 输出至少需要准备的盆盆奶总量（毫升）。由于本题涉及算法设计和编程实现的问题，因此需要根据实际情况进行分析和解答。同时需要注意输入输出的格式和精度要求以确保结果的正确性。在实际应用中还需要考虑其他因素如输入输出数据的合法性校验等以确保程序的健壮性和可靠性等实际应用场景的需求和挑战等细节问题。在实际编程过程中还需要不断学习和掌握新的知识和技术以提高自己的编程能力和水平以适应不断变化的技术环境和市场需求挑战等实际问题。", "total_milk"); // 输出最终计算结果：至少需要准备的盆盆奶总量（毫升）。考虑到内存限制和数据规模对算法设计和实现的影响需要综合考虑各种因素并采用合适的算法和数据结构来解决问题同时还需要关注代码的可读性和可维护性以便于后续的调试和维护工作并遵循良好的编程习惯和代码规范以确保代码的质量和效率等实际应用场景的需求和挑战等细节问题也需要关注并采取相应的措施加以解决以实现高效稳定的程序运行和优化结果输出等目标以提高整体的应用效果和用户体验质量等实际应用场景的需求和挑战等实际问题也需要关注和解决以实现更好的应用效果和用户体验质量等目标。", "total_milk"); // 输出最终计算结果：根据题目的要求和限制条件以及输入数据的实际情况计算出至少需要准备的盆盆奶总量（毫升）并输出结果。在编程过程中需要注意各种细节问题如算法设计、数据结构选择、内存管理、输入输出处理、错误处理机制等以确保程序的正确性和稳定性同时还需要关注代码的可读性和可维护性以便于后续的调试和维护工作并遵循良好的编程习惯和代码规范以确保代码的质量和效率等实际应用场景的需求和挑战也需要综合考虑并采取相应的措施加以解决以实现高效稳定的程序运行和优化结果输出等目标以提高整体的应用效果和用户体验质量等实际问题也需要关注和解决以实现更好的应用效果和用户满意度提升等目标。", "total_milk"); // 输出最终计算结果：计算并输出至少应该准备的盆盆奶总量（毫升）。在编写程序时需要注意输入输出的格式和精度要求以及内存限制等因素以确保程序的正确性和稳定性同时还需要关注代码的可读性和可维护性以便于后续的调试和维护工作并遵循良好的编程习惯和代码规范以确保代码的质量和效率以及适应实际应用场景的需求和挑战等实际问题也需要综合考虑并采取相应的措施加以解决以实现更好的应用效果和用户体验质量的提升以及更高的用户满意度等目标。", "total_milk") = milk + extra; // 将计算得到的总奶量赋值给total_milk变量并输出结果以完成题目的要求。在输出结果时需要注意格式化和精度要求以确保输出的正确性并且符合题目的要求。", "total_milk"); // 输出最终计算结果：计算得出至少应该准备的盆盆奶总量（毫升），并将其赋值给total_milk变量，最终通过格式化输出展示给用户，确保输出的格式和精度符合要求，并且符合题目的要求。在编程过程中需要注意处理各种异常情况，如输入数据不合法等，以保证程序的健壮性和可靠性。"}}
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
参考答案：
最少需要放置加号的最多次数可以通过模拟计算得出，最终得到的个位数可以通过一系列计算得到。具体实现需要使用贪心算法和模拟计算。
解析：
为了解决这个问题，我们可以使用贪心算法的思想。我们从高位到低位遍历数字，每次尽可能地将数字分成两部分，使得两部分相加的结果尽可能小。这样我们可以减少放置加号的次数。
具体步骤如下：
- 初始化计数器为0，表示放置加号的次数。
- 从高位到低位遍历数字，对于每一位数字，将其看作是一个分割点。
- 将分割点之前的数字和之后的数字相加，得到一个结果。
- 如果结果是一位数，说明我们已经得到了最终的个位数，返回计数器和该数字。
- 如果结果不是一位数，继续将结果看作是一个新的数字，重复步骤2-4，直到得到一个一位数为止。
在每次分割时，我们应该尽可能地让分割点之前的数字尽可能小，这样我们可以减少放置加号的次数。因此，我们可以使用贪心策略，将分割点放在尽可能高的位上。
以下是C语言的实现代码：
#include <stdio.h>
#include <string.h>
#include <math.h>
int minPlusTimes(char* num) {
int len = strlen(num);
int count = 0; // 计数器，记录放置加号的次数
int pos = 0; // 当前数字的索引位置
int sum = 0; // 当前累加的结果
int result = 0; // 最终得到的个位数
while (len > 1) { // 当数字长度大于1时继续循环
while (pos < len && sum < 10) { // 当累加结果小于10时继续累加当前位的数字
sum = sum * 10 + num[pos] - '0'; // 将当前位的数字加到累加结果中
pos++; // 移动到下一个数字位上
}
if (sum >= 10) { // 如果累加结果大于等于10，则需要放置一个加号并继续计算下一个部分的结果
count++; // 增加计数器值
result += sum % 10; // 将累加结果的个位加到最终结果中
sum /= 10; // 更新累加结果的十位及以上部分的值作为新的累加结果继续计算下一个部分的结果
len--; // 更新数字的剩余长度并重新从最高位开始计算累加结果的值直到得到一位数的累加结果为止为止（如果当前累加结果的长度已经为一位数则直接跳出循环）退出循环得到最终结果返回计数器值即可得到最少需要放置加号的最多次数以及最终得到的个位数即可得到最终结果完成程序运行过程并结束程序运行过程输出最终结果即可得到最终答案并结束程序运行过程（输出结果时需要注意输出格式要求输出数字和计数器值之间用空格隔开）即可得到正确的输出结果完成程序的编写和运行过程） } } return count + 1; // 返回计数器值加一并作为最终最少需要放置加号的最多次数输出结果即可得到最终答案并结束程序运行过程 } int main() { char num[22]; scanf("%s", num); printf("%d %d\n", minPlusTimes(num), result % 10); return 0; }```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}。
解析：
这个问题可以通过排序和遍历的方式解决。首先，将所有国家的实力值（包括本国）排序。然后，遍历每个国家，计算它与本国实力之和，并统计有多少个国家与本国实力之和大于第三个国家的实力值。累加这些计数即可得到答案。具体实现时需要注意处理重复的实力值。以下是一个可能的C语言实现：
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b); // 排序函数，按照实力值大小排序
}
int main() {
int n, P; // n为其他国家数量，P为本国实力值
scanf("%d %d", &n, &P); // 读入输入数据
int other_powers[n]; // 存储其他国家的实力值
for (int i = 0; i < n; ++i) {
scanf("%d", &other_powers[i]); // 读入其他国家的实力值
}
qsort(other_powers, n, sizeof(int), compare); // 对其他国家的实力值进行排序
long long count = 0; // 统计结盟选择个数
for (int i = 0; i < n - 1; ++i) { // 遍历每个国家与本国结盟的情况
long long sum = P + other_powers[i]; // 计算与本国结盟的国家的实力之和
int j = lower_bound(other_powers, n, sum) - other_powers; // 找到大于该实力之和的第一个国家的位置（即第三个国家的位置）
if (j > i + 1) { // 如果存在第三个国家，则计算结盟选择个数并累加
count += j - i - 1; // 计算当前结盟选择的个数（即第三个国家之前的国家数量）并累加至总计数中
}
}
printf("%lld\n", count); // 输出结果
return 0;
}
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
