首页 › 试卷 › C/C++编程考级 › C/C++编程七级 › 2025年6月电子学会青少年软件编程(C/C++)7级等级考试真题试卷

2025年6月电子学会青少年软件编程(C/C++)7级等级考试真题试卷 VIP

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

一、简答题

1. 简答题

子序列

题目描述

给定两个整数序列,第一个序列长度为 n,第二个序列长度为 m。请问,这两个序列有多少种公共的子序列?输出数量模 998244353 的余数。

所谓子序列,是指从原序列中选择部分或全部元素组成新序列,这些元素在原序列中不必连续,但要保持在原序列中的顺序。只要下标不同,哪怕数字相同,也要算成不同的子序列。

输入格式

第一行:两个整数表示 n 与 m;

第二行: n 个数字 a1,a2,... ,an;

第三行:m 个数字 b1,b2,... ,bm;

输出格式

单个整数表示答案。

输入样例

4 3
3 4 6 2
3 3 2

输出样例

6

说明提示

1≤n,m≤2000

1≤ai,bj≤100,000

限制

时间限制:1000ms

内存限制:512MiB

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; const int MOD = 998244353; int main() {     int n, m;     cin &gt;&gt; n &gt;&gt; m;     vector&lt;int&gt; a(n), b(m);     for (int i = 0; i &lt; n; ++i) cin &gt;&gt; a[i];     for (int i = 0; i &lt; m; ++i) cin &gt;&gt; b[i];          vector&lt;vector&lt;int&gt;&gt; dp(n + 1, vector&lt;int&gt;(m + 1, 0));          // 空子序列     for (int i = 0; i &lt;= n; ++i) dp[i][0] = 1;     for (int j = 0; j &lt;= m; ++j) dp[0][j] = 1;          for (int i = 1; i &lt;= n; ++i) {         for (int j = 1; j &lt;= m; ++j) {             if (a[i-1] == b[j-1]) {                 dp[i][j] = (dp[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;             } else {                 dp[i][j] = (dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]) % MOD;             }             if (dp[i][j] &lt; 0) dp[i][j] += MOD;         }     }          cout &lt;&lt; dp[n][m] &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
2. 简答题

逻辑表达式

题目描述

给定一个逻辑表达式,以运算符做前缀的形式给出。它包含三种运算符:&、|、^:

& 表示逻辑与运算

| 表示逻辑或运算

^ 表示逻辑异或运算

表达式还包含三种基本逻辑值:0、1、?。

每个 ? 必须赋值成为 0 或 1 中的一种,请问有多少种不同的赋值方式,可以让整个逻辑表达式的值为 0?

由于答案可能很大,请输出方案数模1,000,000,007 的余数。

前缀表达式的定义如下:

0、1、? 都是前缀表达式;

如果 x,y 都是前缀表达式,则 &xy、|xy、^xy 都是前缀表达式;

不满足以上两条规则的表达式都不是前缀表达式。

输入格式

单个字符串表示输入的前缀表达式

输出格式

单个整数:表示答案模 1,000,000,007 的余数。


输入样例#1

&??

输出样例#1

3

输入样例#2

||??|||?^?|0|1&???|??

输出样例#2

4

输入样例#3

|?^?|0|&??||?^?|1??

输出样例#3

64

说明提示

设 ∣s∣表示输入字符串的长度

50%的数据,1≤∣s∣<1,000

100%的数据,1≤∣s∣<200,000

限制

时间限制:1000ms

内存限制:512MiB

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">//C语言参考代码 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #define MOD 1000000007 typedef struct {    long long zero;    long long one; } Node; Node stack[200000]; int top = -1; void push(Node node) {    stack[++top] = node; } Node pop() {    return stack[top--]; } int main() {    char s[200001];    scanf("%s", s);    int len = strlen(s);    for (int i = len - 1; i &gt;= 0; i--) {        char c = s[i];        if (c == '0') {            push((Node){1, 0});        } else if (c == '1') {            push((Node){0, 1});        } else if (c == '?') {            push((Node){1, 1});        } else {            Node right = pop();            Node left = pop();            Node res = {0, 0};            if (c == '&amp;') {                res.zero = (left.zero * right.zero % MOD + left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;                res.one = left.one * right.one % MOD;            } else if (c == '|') {                res.zero = left.zero * right.zero % MOD;                res.one = (left.one * right.zero % MOD + left.zero * right.one % MOD + left.one * right.one % MOD) % MOD;            } else if (c == '^') {                res.zero = (left.zero * right.zero % MOD + left.one * right.one % MOD) % MOD;                res.one = (left.zero * right.one % MOD + left.one * right.zero % MOD) % MOD;            }            push(res);        }    }    Node result = pop();    printf("%lld\n", result.zero);    return 0; }</pre><pre class="brush:cpp;toolbar:false">//C++参考代码 #include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;vector&gt; using namespace std; const int MOD = 1e9+7; struct Node {     long long zero, one;     Node(long long z=0, long long o=0) : zero(z), one(o) {} }; int main() {     string s;     cin &gt;&gt; s;     stack&lt;Node&gt; st;          for (int i = s.size()-1; i &gt;= 0; --i) {         char c = s[i];         if (c == '0') {             st.push(Node(1, 0));         } else if (c == '1') {             st.push(Node(0, 1));         } else if (c == '?') {             st.push(Node(1, 1));         } else {             Node right = st.top(); st.pop();             Node left = st.top(); st.pop();             Node res;                          if (c == '&amp;') {                 res.zero = (right.zero * left.zero % MOD +                             right.zero * left.one % MOD +                             right.one * left.zero % MOD) % MOD;                 res.one = right.one * left.one % MOD;             } else if (c == '|') {                 res.zero = right.zero * left.zero % MOD;                 res.one = (right.one * left.one % MOD +                            right.one * left.zero % MOD +                            right.zero * left.one % MOD) % MOD;             } else if (c == '^') {                 res.zero = (right.zero * left.zero % MOD +                             right.one * left.one % MOD) % MOD;                 res.one = (right.zero * left.one % MOD +                            right.one * left.zero % MOD) % MOD;             }             st.push(res);         }     }          cout &lt;&lt; st.top().zero % MOD &lt;&lt; endl;     return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

联盟

题目描述

在国际会议上,共有 n 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况,请计算存在多少种合法的联盟分配方案。

输入格式

第一行:单个整数 n 表示国家数量

第二行到第 n 行:在第i+1 行有 n-i 个整数 ci,i+1,ci,i+2,…,ci,n,其中

ci,j=0-表示 i 号国家与 j 号国家不接壤

ci,j=1 表示 i 号国家与 j 号国家接壤

输出格式

单个整数:表示合法的联盟分配方案总数。


输入样例#1

3
1 1
1

输出样例#1

6

输入样例#2

4
1 1 1
1 1
1

输出样例#2

0

说明提示

数据范围

对于 50% 的数据,1≤n≤12

对于 100% 的数据,1≤n≤20

样例1说明

三国两两接壤,形成三角形。三个联盟的排列方案为 3!=6种。

限制

时间限制:1000ms

内存限制:512MiB

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; int n; vector&lt;vector&lt;int&gt;&gt; adj; vector&lt;int&gt; color; int count = 0; bool isValid(int country, int c) {     for (int i = 0; i &lt; country; ++i) {         if (adj[i][country] &amp;&amp; color[i] == c) {             return false;         }     }     return true; } void dfs(int country) {     if (country == n) {         count++;         return;     }          for (int c = 1; c &lt;= 3; ++c) {         if (isValid(country, c)) {             color[country] = c;             dfs(country + 1);             color[country] = 0;         }     } } int main() {     cin &gt;&gt; n;     adj.resize(n, vector&lt;int&gt;(n, 0));     color.resize(n, 0);          for (int i = 0; i &lt; n-1; ++i) {         for (int j = i+1; j &lt; n; ++j) {             cin &gt;&gt; adj[i][j];             adj[j][i] = adj[i][j];         }     }          dfs(0);     cout &lt;&lt; count &lt;&lt; endl;     return 0; }</pre>
这道题暂未补解析。
4. 简答题

工作规划

题目描述

n 台机器人正在完成任务。其中,第 i 台机器人需要工作 ti 分钟才能完成任务。这些机器人之间有一些前后约束,其中约束关系共有m条,每一条约束表示机器人 b 要在机器人 a 完成任务后才能开始工作。

请问,所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的,所有机器人一定在有限时间内完成工作。

输入格式

第一行:两个整数 n 和 m

第二行到第 n+1 行:每个机器人需要的时间 ti

接下来 m 行:每行有两个整数 a 和 b,表示第 b 台机器人必须要等第 a 台机器人任务完成之后才能开始工作。

输出格式

单个整数,表示所有机器人任务完成最少需要花多少时间。


输入样例

10 9
3
29
1
35
18
22
8
29
4
12
3 2
4 8
1 7
6 5
7 10
8 1
10 9
2 4
5 3

输出样例

161

说明提示

1≤n≤104

1≤m≤50,000

1≤ti≤105

1≤ai,bi≤n

限制

时间限制:1000ms

内存限制:512MiB

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; #include &lt;string.h&gt; #define MAX_N 10005 #define MAX_M 50005 #define INF 0x3f3f3f3f typedef struct Node {    int to;    struct Node* next; } Node; Node* adj[MAX_N];  // 邻接表 int in_degree[MAX_N];  // 入度数组 int t[MAX_N];  // 每个机器人的工作时间 int earliest_start[MAX_N];  // 每个机器人的最早开始时间 int n, m; // 添加边 void add_edge(int u, int v) {    Node* new_node = (Node*)malloc(sizeof(Node));    new_node-&gt;to = v;    new_node-&gt;next = adj[u];    adj[u] = new_node;    in_degree[v]++; } // 拓扑排序计算最早完成时间 int topological_sort() {    int queue[MAX_N];    int front = 0, rear = 0;    // 初始化队列,将入度为0的节点加入队列    for (int i = 1; i &lt;= n; i++) {        if (in_degree[i] == 0) {            queue[rear++] = i;            earliest_start[i] = 0;  // 入度为0的节点最早开始时间为0        }    }    // 处理队列中的节点    while (front &lt; rear) {        int u = queue[front++];        // 遍历所有后继节点        Node* current = adj[u];        while (current != NULL) {            int v = current-&gt;to;            // 更新后继节点的最早开始时间            if (earliest_start[v] &lt; earliest_start[u] + t[u]) {                earliest_start[v] = earliest_start[u] + t[u];            }            // 减少后继节点的入度            in_degree[v]--;            if (in_degree[v] == 0) {                queue[rear++] = v;            }            current = current-&gt;next;        }    }    // 计算最大最早完成时间    int max_time = 0;    for (int i = 1; i &lt;= n; i++) {        int finish_time = earliest_start[i] + t[i];        if (finish_time &gt; max_time) {            max_time = finish_time;        }    }    return max_time; } int main() {    // 初始化    memset(adj, 0, sizeof(adj));    memset(in_degree, 0, sizeof(in_degree));    memset(earliest_start, 0, sizeof(earliest_start));    // 读取输入    scanf("%d %d", &amp;n, &amp;m);    for (int i = 1; i &lt;= n; i++) {        scanf("%d", &amp;t[i]);    }    for (int i = 0; i &lt; m; i++) {        int a, b;        scanf("%d %d", &amp;a, &amp;b);        add_edge(a, b);    }    // 计算并输出结果    int result = topological_sort();    printf("%d\n", result);    // 释放内存    for (int i = 1; i &lt;= n; i++) {        Node* current = adj[i];        while (current != NULL) {            Node* temp = current;            current = current-&gt;next;            free(temp);        }    }    return 0; }</pre>
这道题暂未补解析。