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

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

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

一、简答题

1. 简答题

产品研发

题目描述

一家公司正在研发一款新产品。该产品共有 K 项关键性能指标,初始时所有指标均为 0。公司的最终目标是让 每一项指标都不低于 P。

研发团队提出了 N 个独立的改进方案。第 i 个方案一旦实施,会同时为第 j 项指标(1≤j≤K)带来 Ai,j 的提升,但实施该方案需要投入 Ci 的研发成本。每个方案最多只能执行一次。

你需要判断:是否存在一系列方案的选择,使得所有指标均达到或超过 P?如果存在,请给出 最小的总研发成本;如果不存在,输出 −1。

输入格式

第一行,三个整数 N,K,P,分别表示方案数量、指标数量和目标阈值。

接下来 N 行,每行 K+1 个整数 Ci,Ai,1,Ai,2,…,Ai,K,分别表示第 i 个方案的成本,以及执行后各指标的提升值。

输出格式

输出一个整数,表示达成目标所需的最小总成本。若无法达成,输出 −1。

输入样例#1

4 3 5
5 3 0 2
3 1 2 3
3 2 4 0
1 0 1 4

输出样例#1

9

输入样例#2

7 3 5
85 1 0 1
37 1 1 0
38 2 0 0
45 0 2 2
67 1 1 0
12 2 2 0
94 2 2 1

输出样例#2

-1

说明提示

1≤N≤100

1≤K,P≤5

0≤Ai,j≤P(1≤i≤N, 1≤j≤K)

1≤Ci≤109(1≤i≤N)

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;climits&gt; #include &lt;algorithm&gt; using namespace std; using ll = long long; const ll INF = 1e18; int N, K, P; // 每个方案:cost,k个增量 struct Plan { ll c; vector&lt;int&gt; add; }; vector&lt;Plan&gt; pl; // 多维dp,K维,每一维0~P // 用递归式编码/解码K维下标转一维索引 int encode(const vector&lt;int&gt;&amp; st) { int res = 0; int base = 1; for (int i = 0; i &lt; K; i++) { res += st[i] * base; base *= (P + 1); } return res; } void decode(int idx, vector&lt;int&gt;&amp; st) { st.assign(K, 0); int base = 1; for (int i = 0; i &lt; K; i++) { st[i] = (idx / base) % (P + 1); base *= (P + 1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin &gt;&gt; N &gt;&gt; K &gt;&gt; P; pl.resize(N); for (int i = 0; i &lt; N; i++) { ll c; cin &gt;&gt; c; vector&lt;int&gt; a(K); for (int j = 0; j &lt; K; j++) cin &gt;&gt; a[j]; pl[i] = {c, a}; } int stateCnt = 1; for (int i = 0; i &lt; K; i++) stateCnt *= (P + 1); vector&lt;ll&gt; dp(stateCnt, INF); vector&lt;int&gt; zero(K, 0); dp[encode(zero)] = 0; // 01背包,逐个方案更新 for (auto&amp; p : pl) { ll cost = p.c; auto&amp; add = p.add; // 倒序遍历所有状态,避免重复选取 vector&lt;ll&gt; tmp = dp; for (int idx = 0; idx &lt; stateCnt; idx++) { if (dp[idx] == INF) continue; vector&lt;int&gt; st; decode(idx, st); // 计算新状态 vector&lt;int&gt; nst(K); for (int j = 0; j &lt; K; j++) { nst[j] = min(st[j] + add[j], P); } int nidx = encode(nst); tmp[nidx] = min(tmp[nidx], dp[idx] + cost); } dp.swap(tmp); } // 目标状态:全部指标=P vector&lt;int&gt; target(K, P); ll ans = dp[encode(target)]; if (ans &gt;= INF) cout &lt;&lt; -1 &lt;&lt; endl; else cout &lt;&lt; ans &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。
2. 简答题

传话对象

题目描述

在一个公司里,有 n 名员工,编号 1 到 n。每名员工都有一个“传话对象”,即第 ii 名员工只会把消息告诉第 ti 名员工(允许告诉自己)。现在,从每名员工出发,依次沿着传话对象传递消息,可以证明经过有限步后,消息一定会回到一个已经传过的员工。

请你分别计算:从第 i 名员工开始,需要传递多少步后,才会第一次遇到一个已经传过消息的员工。

输入格式

第一行,一个整数 n。

第二行,n 个整数 t1,t2,…,tn,表示第 i 名员工的传话对象。

输出格式

输出 n 行,第 i 行一个整数,表示从第 i 名员工出发的答案。

输入样例

4
2 1 1 4

输出样例

2
2
3
1

说明提示

1≤n≤5×105

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; using ll = long long; const int MAXN = 5e5 + 10; int t[MAXN]; int vis[MAXN]; // 0未访问 1访问中 2已处理 int ans[MAXN]; vector&lt;int&gt; path; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin &gt;&gt; n; for (int i = 1; i &lt;= n; i++) { cin &gt;&gt; t[i]; } for (int i = 1; i &lt;= n; i++) { if (vis[i] != 0) continue; path.clear(); int cur = i; while (true) { if (vis[cur] == 1) { // 找到环起点:cur在path中的位置 int pos = 0; while (path[pos] != cur) pos++; // 环部分 [pos, end] int ring_len = path.size() - pos; for (int j = pos; j &lt; path.size(); j++) { ans[path[j]] = ring_len; vis[path[j]] = 2; } // 树链部分 [0, pos-1] 倒推 for (int j = pos - 1; j &gt;= 0; j--) { ans[path[j]] = ans[t[path[j]]] + 1; vis[path[j]] = 2; } break; } if (vis[cur] == 2) { // 当前路径全部是树链,用已处理点倒推 for (int j = path.size() - 1; j &gt;= 0; j--) { ans[path[j]] = ans[t[path[j]]] + 1; vis[path[j]] = 2; } break; } // 未访问,加入路径标记为访问中 vis[cur] = 1; path.push_back(cur); cur = t[cur]; } } for (int i = 1; i &lt;= n; i++) { cout &lt;&lt; ans[i] &lt;&lt; '\n'; } return 0; }</pre>
这道题暂未补解析。
3. 简答题

能量护盾

题目描述

在一处被宇宙射线笼罩的星域中,你驾驶着一艘小型探索飞船,需要从坐标 (xs,ys) 航行到坐标 (xt,yt)。

飞船可以以速度 1 向任意方向移动,自身视为一个点。

星域中分布着 N 个圆形能量护盾,第 i 个护盾的圆心为 (xi,yi),半径为 ri。护盾之间可能相互重叠,也可能存在包含关系。

飞船一旦进入某个护盾的内部,就能免受宇宙射线的伤害。若一个点不在任何护盾内部,则飞船会持续受到宇宙射线的照射。

你的目标是:在从起点到终点的航行过程中,尽可能减少受到宇宙射线照射的总时间。

请你计算这个最小照射时间。

输入格式

第一行,四个整数 xs,ys,xt,yt,分别表示起点和终点的坐标。

第二行,一个整数 N,表示圆形护盾的数量。

接下来 N 行,每行三个整数 xi,yi,ri,描述第 i 个护盾的圆心坐标和半径。

输出格式

输出一个实数,表示受到宇宙射线照射的最小时间,保留 10 位小数。

输入样例#1

-2 -2 2 2
1
0 0 1

输出样例#1

3.6568542495

输入样例#2

-2 0 2 0
2
-1 0 2
1 0 2

输出样例#2

0.0000000000

输入样例#3

4 -2 -2 4
3
0 0 2
4 0 1
0 4 1

输出样例#3

4.0000000000

说明提示

−109≤xs,ys,xt,yt≤109

(xs,ys)≠(xt,yt)

1≤N≤1000

−109≤xi,yi≤109

1≤ri≤109

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cmath&gt; #include &lt;iomanip&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; const double INF = 1e18; const double eps = 1e-8; struct Point { ll x, y; Point() {} Point(ll x_, ll y_) : x(x_), y(y_) {} }; struct Circle { ll x, y, r; Circle() {} Circle(ll x_, ll y_, ll r_) : x(x_), y(y_), r(r_) {} }; // 两点距离 double dis_pp(const Point&amp; a, const Point&amp; b) { ll dx = a.x - b.x; ll dy = a.y - b.y; return sqrt(1.0 * dx * dx + 1.0 * dy * dy); } // 点到圆的暴露长度,点在圆内返回0 double dis_pc(const Point&amp; p, const Circle&amp; c) { double d = dis_pp(p, Point(c.x, c.y)); if (d &lt;= c.r + eps) return 0.0; return d - c.r; } // 两个圆之间暴露长度,相交/包含返回0 double dis_cc(const Circle&amp; a, const Circle&amp; b) { double d = dis_pp(Point(a.x, a.y), Point(b.x, b.y)); double sumr = a.r + b.r; if (d &lt;= sumr + eps) return 0.0; return d - sumr; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout &lt;&lt; fixed &lt;&lt; setprecision(10); ll xs, ys, xt, yt; cin &gt;&gt; xs &gt;&gt; ys &gt;&gt; xt &gt;&gt; yt; Point S(xs, ys), T(xt, yt); int N; cin &gt;&gt; N; vector&lt;Circle&gt; cir(N); for (int i = 0; i &lt; N; i++) { cin &gt;&gt; cir[i].x &gt;&gt; cir[i].y &gt;&gt; cir[i].r; } // 总点数:0起点,1~N护盾,N+1终点 int tot = N + 2; vector&lt;vector&lt;double&gt;&gt; g(tot, vector&lt;double&gt;(tot, INF)); for (int i = 0; i &lt; tot; i++) g[i][i] = 0; // 0(S) &lt;-&gt; N+1(T) g[0][N+1] = dis_pp(S, T); g[N+1][0] = dis_pp(S, T); // 0(S) 和所有护盾 1~N for (int i = 1; i &lt;= N; i++) { double d = dis_pc(S, cir[i-1]); g[0][i] = d; g[i][0] = d; } // N+1(T) 和所有护盾 1~N for (int i = 1; i &lt;= N; i++) { double d = dis_pc(T, cir[i-1]); g[N+1][i] = d; g[i][N+1] = d; } // 护盾之间 i,j (1~N) for (int i = 1; i &lt;= N; i++) { for (int j = i + 1; j &lt;= N; j++) { double d = dis_cc(cir[i-1], cir[j-1]); g[i][j] = d; g[j][i] = d; } } // Floyd 求全源最短路,N&lt;=1000 tot=1002,1e9?不行!换Dijkstra单源 vector&lt;double&gt; dist(tot, INF); vector&lt;bool&gt; vis(tot, false); dist[0] = 0; for (int step = 0; step &lt; tot; step++) { int u = -1; double minv = INF; for (int i = 0; i &lt; tot; i++) { if (!vis[i] &amp;&amp; dist[i] &lt; minv) { minv = dist[i]; u = i; } } if (u == -1) break; vis[u] = true; for (int v = 0; v &lt; tot; v++) { if (g[u][v] &lt; INF &amp;&amp; dist[v] &gt; dist[u] + g[u][v]) { dist[v] = dist[u] + g[u][v]; } } } cout &lt;&lt; dist[N+1] &lt;&lt; endl; return 0; }</pre>
这道题暂未补解析。
4. 简答题

图书馆

题目描述

某城市有 n 条东西向街道和 n 条南北向街道,构成一个 n×n 的街区网格。每个交叉路口处恰好建有一座图书馆,且每一行、每一列的交叉路口都恰好有一座图书馆。已知第 i 座图书馆的坐标 (xi,yi) 表示它位于第 xi 条东西向街道与第 yi 条南北向街道的交汇处。

城市规划师想要知道:有多少个 正方形区域(由连续的若干条东西向街道和连续的若干条南北向街道围成),使得该区域内每一行、每一列也恰好各有一座图书馆?

输入格式

第一行,一个整数 n。

第二行,n 个整数 x1,x2,…,xn,表示第 i 座图书馆的东西向街道编号。

第三行,n 个整数 y1,y2,…,yn,表示第 i 座图书馆的南北向街道编号。

输入保证:1≤xi,yi≤n,且每行每列恰好只有一座图书馆。

输出格式

输出一个整数,表示满足条件的正方形区域个数。

输入样例

7
1 2 3 4 5 6 7
4 3 1 6 2 5 7

输出样例

10

说明提示

1≤n≤105

1≤xi,yi≤n

输入保证每行每列恰好有一座图书馆。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;stack&gt; #include &lt;algorithm&gt; using namespace std; typedef long long ll; vector&lt;int&gt; a, leftBig, rightBig; ll total = 0; void dfs(int l, int r, int mid) {     int maxVal = a[mid];     vector&lt;int&gt; minLeft, minRight;     int mn = maxVal;     minLeft.push_back(mn);     for (int i = mid - 1; i &gt;= l; i--) {         mn = min(mn, a[i]);         minLeft.push_back(mn);     }     mn = maxVal;     minRight.push_back(mn);     for (int i = mid + 1; i &lt;= r; i++) {         mn = min(mn, a[i]);         minRight.push_back(mn);     }     int L = minLeft.size() - 1;     int R = minRight.size() - 1;     int i = 0, j = 0;     while (i &lt;= L &amp;&amp; j &lt;= R) {         int curMin = min(minLeft[i], minRight[j]);         if (maxVal - curMin == i + j) total++;         if (i == L) j++;         else if (j == R) i++;         else if (minLeft[i+1] &lt; minRight[j+1]) i++;         else j++;     }     int lm = leftBig[mid], rm = rightBig[mid];     if (lm &gt;= l) dfs(l, mid-1, lm);     if (rm &lt;= r) dfs(mid+1, r, rm); } int main() {     ios::sync_with_stdio(false);     cin.tie(nullptr);     int n;     cin &gt;&gt; n;     vector&lt;int&gt; x(n), y(n);     a.resize(n+2);     leftBig.assign(n+2, 0);     rightBig.assign(n+2, n+1);     for (int i = 0; i &lt; n; i++) cin &gt;&gt; x[i];     for (int i = 0; i &lt; n; i++) cin &gt;&gt; y[i];     for (int i = 0; i &lt; n; i++) a[x[i]] = y[i];     stack&lt;int&gt; st;     for (int i = 1; i &lt;= n; i++) {         while (!st.empty() &amp;&amp; a[st.top()] &lt; a[i]) st.pop();         if (!st.empty()) leftBig[i] = st.top();         st.push(i);     }     while (!st.empty()) st.pop();     for (int i = n; i &gt;= 1; i--) {         while (!st.empty() &amp;&amp; a[st.top()] &lt; a[i]) st.pop();         if (!st.empty()) rightBig[i] = st.top();         st.push(i);     }     int root = 1;     for (int i = 2; i &lt;= n; i++) if (a[i] &gt; a[root]) root = i;     dfs(1, n, root);     total += n;     cout &lt;&lt; total &lt;&lt; endl;     return 0; }</pre>
解析:

输出应该是9,题目给出的输出为10,貌似有错误。