首页 › 试卷 › C/C++编程考级 › C/C++编程三级 › 青少年软件编程(C/C++)3级等级考试真题试卷(2024年6月)

青少年软件编程(C/C++)3级等级考试真题试卷(2024年6月) VIP

C/C++编程三级 共 5 题 2024 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

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
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include&lt;bits/stdc++.h&gt; using namespace std; bool prime(int num) {     if(num &lt;= 1)         return false;     for(int i=2; i&lt;=sqrt(num); i++)     {         if(num%i == 0)             return false;     }     return true; } int main() {     int L,K;     string str;     cin&gt;&gt;L&gt;&gt;K&gt;&gt;str;     bool flag = false;//没有找到的标记     for(int i=0; i&lt;=L-K; i++)     {      //提取字符串         string temp(str,i,K);         //转成数字         stringstream ss(temp);         int num;         ss&gt;&gt;num;         //判断         if(prime(num))         {             flag = true;             cout&lt;&lt;temp;             break;         }     }     if(!flag)         cout&lt;&lt;"404";     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; int isPrime(long long n) {     if (n &lt; 2) {         return 0;     }     for (long long i = 2; i * i &lt;= n; i++) {         if (n % i == 0) {             return 0;         }     }     return 1; } int main() {     int l, k;     scanf("%d %d", &amp;l, &amp;k);     char s[1001];     scanf("%s", s);     int pos = 0;     for (int i = 0; i &lt;= l - k; i++) {         char w[11];         strncpy(w, s + i, k);         w[k] = '\0';         long long ans = atoll(w);         if (isPrime(ans)) {             printf("%s", w);             return 0;         }         pos++;     }     printf("404");     return 0; }</pre>
这道题暂未补解析。
2. 简答题

吉利矩阵

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

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

时间限制:6000

内存限制:65535

输入

输入在一行中给出 2 个正整数 L 和 N,意义如题面所述。数字间以空格分隔。

输出

在一行中输出满足题目要求条件的方阵的个数。

样例输入

7 3

样例输出

666
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C语言 #include &lt;stdio.h&gt; int res = 0; int sum_row[4] = {0}; int sum_col[4] = {0}; void dfs(int x, int sum, int width) {     if (x == width * width) {         ++res;         return;     }     for (int i = 0; i &lt;= sum; i++) {         if (x % width == width - 1 &amp;&amp; i != sum - sum_row[x / width]) continue;         if (x / width == width - 1 &amp;&amp; i != sum - sum_col[x % width]) continue;         if (sum_row[x / width] + i &lt;= sum &amp;&amp; sum_col[x % width] + i &lt;= sum) {             sum_col[x % width] += i;             sum_row[x / width] += i;             dfs(x + 1, sum, width);             sum_col[x % width] -= i;             sum_row[x / width] -= i;         }     } } int main() {     int sum, width;     scanf("%d %d", &amp;sum, &amp;width);     dfs(0, sum, width);     printf("%d\n", res);     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 #include&lt;iostream&gt; using namespace std; const int N=20; int a[N][N]; int main(){ int l,n;cin&gt;&gt;l&gt;&gt;n; a[2][2]=3; a[2][3]=21; a[2][4]=282; a[3][2]=4; a[3][3]=55; a[3][4]=2008; a[4][2]=5; a[4][3]=120; a[4][4]=10147; a[5][2]=6; a[5][3]=231; a[5][4]=40176; a[6][2]=7; a[6][3]=406; a[6][4]=132724; a[7][2]=8; a[7][3]=666; a[7][4]=381424; a[8][2]=9; a[8][3]=1035; a[8][4]=981541; a[9][2]=10; a[9][3]=1540; a[9][4]=2309384; cout&lt;&lt;a[l][n]; }</pre>
这道题暂未补解析。
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

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include &lt;iostream&gt; using namespace std; int n, ans, A[10005], L[10005], R[10005]; int main(){     cin &gt;&gt; n;     for (int i = 1; i &lt;= n; i++) cin &gt;&gt; A[i];     for (int i = 1; i &lt; n; i++) {         int j = i;         while(j + 1 &lt;= n &amp;&amp; A[j] &gt;= A[j + 1]) {             if (A[j] &gt; A[j + 1]) ++L[i];             ++j;         }     }     for (int i = n; i &gt; 1; i--) {         int j = i;         while(j - 1 &gt;= 1 &amp;&amp; A[j] &gt;= A[j - 1]) {             if (A[j] &gt; A[j - 1]) ++R[i];             --j;         }     }     for (int i = 1; i &lt;= n; i++) ans += max(L[i], R[i]) * 100 + 200;     cout &lt;&lt; ans;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; int max(int a, int b) {     return a &gt; b ? a : b; } int main() {     int n, ans = 0;     int A[10005], L[10005] = {0}, R[10005] = {0};     // 读取胖达的个数     scanf("%d", &amp;n);     // 读取每只胖达的体重     for (int i = 1; i &lt;= n; i++) {         scanf("%d", &amp;A[i]);     }     // 计算 L 数组     for (int i = 1; i &lt; n; i++) {         int j = i;         while (j + 1 &lt;= n &amp;&amp; A[j] &gt;= A[j + 1]) {             if (A[j] &gt; A[j + 1]) ++L[i];             ++j;         }     }     // 计算 R 数组     for (int i = n; i &gt; 1; i--) {         int j = i;         while (j - 1 &gt;= 1 &amp;&amp; A[j] &gt;= A[j - 1]) {             if (A[j] &gt; A[j - 1]) ++R[i];             --j;         }     }     // 计算总量     for (int i = 1; i &lt;= n; i++) {         ans += max(L[i], R[i]) * 100 + 200;     }     // 输出结果     printf("%d\n", ans);     return 0; }</pre>
这道题暂未补解析。
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

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;string.h&gt; #include &lt;stdlib.h&gt; long ansfqy = __LONG_MAX__; int ansnum = 10; void justdfs(long n, long frequency); void exceeddfs(char *n, long frequency); void justdfs(long n, long frequency) {     if (ansfqy &lt; frequency) {         return;     }     if (n &lt; 10 &amp;&amp; (n &lt; ansnum || frequency &lt; ansfqy)) {         ansnum = n;         ansfqy = frequency;         return;     }     long temp = 10;     while (n / temp &gt; 0) {         long nleft = n / temp;         long nright = n % temp;         temp *= 10;         justdfs(nleft + nright, frequency + 1);     } } void exceeddfs(char *n, long frequency) {     if (ansfqy &lt; frequency) {         return;     }     for (int i = 1; i &lt; strlen(n); i++) {         char BIleft[1025], BIright[1025];         strncpy(BIleft, n, i);         BIleft[i] = '\0';         strncpy(BIright, n + i, strlen(n) - i);         BIright[strlen(n) - i] = '\0';         long sum = atol(BIleft) + atol(BIright);         char temp[1025];         sprintf(temp, "%ld", sum);         if (strlen(temp) &lt; 19) {             justdfs(sum, frequency + 1);         } else {             exceeddfs(temp, frequency + 1);         }     } } int main() {     char n[1025];     scanf("%s", n);     if (strlen(n) &lt; 19) {         justdfs(atol(n), 0);     } else {         exceeddfs(n, 0);     }     printf("%ld %d\n", ansfqy, ansnum);     return 0; }</pre>
这道题暂未补解析。
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}。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include &lt;bits/stdc++.h&gt; using namespace std;   typedef long long ll;   const int N = 1e5 + 10;   int n, p; int a[N]; ll s;   int main() {     cin &gt;&gt; n &gt;&gt; p;     for (int i = 1; i &lt;= n; i ++)         cin &gt;&gt; a[i];          sort(a + 1, a + n + 1);       for (int i = 1; i &lt;= n; i ++) {         int l = i + 1, r = n;         int minn = abs(a[i]-p), maxx = a[i] + p;         int n1, n2; // 记录下标         if (l&gt;r) break;           while (l &lt;= r) { // 找到大于最小值的数             int mid = (l + r) / 2;             if (a[mid] &lt;= minn)                  l = mid + 1;             else                 r = mid - 1;         }         n1 = l;                  l = i + 1, r = n;         while (l &lt;= r) { // 找到小于最大值的数             int mid = (l + r) / 2;             if (a[mid] &lt; maxx)                 l = mid + 1;             else                 r = mid - 1;         }         n2 = r;           s += (n2 - n1) + 1;     }          cout &lt;&lt; s;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; long long n, x, cnt; int a[100005]; int cmpfunc(const void *a, const void *b) {     return (*(int *)a - *(int *)b); } int upper_bound(int arr[], int n, int x) {     int l = 0;     int r = n;     while (l &lt; r) {         int mid = l + (r - l) / 2;         if (arr[mid] &lt;= x) {             l = mid + 1;         } else {             r = mid;         }     }     return l; } int lower_bound(int arr[], int n, int x) {     int l = 0;     int r = n;     while (l &lt; r) {         int mid = l + (r - l) / 2;         if (arr[mid] &lt; x) {             l = mid + 1;         } else {             r = mid;         }     }     return l; } int main() {     scanf("%lld %lld", &amp;n, &amp;x);     for (int i = 0; i &lt; n; ++i) {         scanf("%d", &amp;a[i]);     }          qsort(a, n, sizeof(int), cmpfunc);          for (int i = 0; i &lt; n - 1; ++i) {         int l, r;         if (a[i] &lt; x) {             l = upper_bound(a + i + 1, n - i - 1, x - a[i]);         } else {             l = upper_bound(a + i + 1, n - i - 1, a[i] - x);         }         r = lower_bound(a + i + 1, n - i - 1, a[i] + x) - 1;                  if (l == n - i - 1) {             continue;         }                  cnt += (r - l + 1);     }          printf("%lld\n", cnt);     return 0; }</pre>
这道题暂未补解析。