2024 年 6 月青少年软编等考 C 语言三级真题解析

T1. 谷歌的招聘

2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌用于招聘。内容超级简单，就是一个以 $.com$ 结尾的网址，而前面的网址是一个 $10$ 位素数，这个素数是自然常数 $e$ 中最早出现的 $10$ 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自然常数 $e$ 是一个著名的超越数，前面若干位写出来是这样的：$e=$ 2.718281828459045235360287471352662497757247093699959574966967627724076630353547594571382178525166427427466391932003059921… 其中粗体标出的 $10$ 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 $L$ 的数字中，找出最早出现的 $K$ 位连续数字所组成的素数。

时间限制：1 s
内存限制：64 MB

• 输入
  输入在第一行给出 $2$ 个正整数，分别是 $L$（不超过 $1000$ 的正整数，为数字长度）和 $K$（小于 $10$ 的正整数）。
  接下来一行给出一个长度为 $L$ 的正整数 $N$。
• 输出
  在一行中输出 $N$ 中最早出现的 $K$ 位连续数字所组成的素数。如果这样的素数不存在，则输出 $404$。注意，原始数字中的前导零也计算在位数之内。例如在 $200236$ 中找 $4$ 位素数，$0023$ 算是解；但第一位 $2$ 不能被当成 $0002$ 输出，因为在原始数字中不存在这个 $2$ 的前导零。
• 样例输入 1

  20 5
  23654987725541023819
  

• 样例输出 1

  49877
  

• 样例输入 2

  10 3
  2468024680
  

• 样例输出 2

  404
  

思路分析

此题考查枚举法与素数判断，属于入门题。

我们可以从前向后枚举需要截取的子串的起点 $i$，从 $i$ 开始截取长度为 $K$ 的子串，并将其转换为整数 $num$。接着判断该整数是否为素数即可。为了避免越界，枚举的终点应为 $L-K$。注意最后输出的是长度为 $K$ 的子串，而不是去除前导零之后的 $num$。

/*
 * Name: T1.cpp
 * Problem: 谷歌的招聘
 * Author: Teacher Gao.
 * Date&Time: 2025/02/08 17:24
 */

#include <iostream>
#include <string>

using namespace std;

bool prime(int k) {
   
    if (k < 2) return 0;

    for (int i = 2; i*i <= k; i++) {
   
        if (k % i == 0) return 0;
    }

    return 1;
}

int main()
{
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    int L, K;
    string s;
    cin >> L >> K >> s;

    for (int i = 0; i <= L - K; i++) {
   
        int num = stoi(s.substr(i, K));

        if (prime(num)) {
   
            cout << s.substr(i, K) << endl;
            return 0;
        }
    }

    cout << 404 << endl;

    return 0;
}

T2. 吉利矩阵

所有元素为非负整数，且各行各列的元素和都等于 $7$ 的 $3\times 3$ 方阵称为 “吉利矩阵”，因为这样的矩阵一共有 $666$ 种。

本题就请你统计一下，把 $7$ 换成任何一个 $[2,9]$ 区间内的正整数 $L$，把矩阵阶数换成任何一个 $[2,4]$ 区间内的正整数 $N$，满足条件 “所有元素为非负整数，且各行各列的元素和都等于 $L$” 的 $N\times N$ 方阵一共有多少种？

时间限制：1 s
内存限制：64 MB

• 输入
  输入在一行中给出 $2$ 个正整数 $L$ 和 $N$，意义如题面所述。数字间以空格分隔。
• 输出
  在一行中输出满足题目要求条件的方阵的个数。
• 样例输入

  7 3
  

• 样例输出

  666
  

思路分析

此题考查暴力枚举，属于基础题。

从第一行第一列开始枚举填充，用 $row[i]$ 和 $col[i]$ 分别记录第 $i$ 行和第 $i$ 列元素之和，于是对于位置 $(x,y)$，可以填充的最小数字为 $0$，最大数字为 min ⁡ ( L − r o w [ x ] ,