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

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

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

一、简答题

1. 简答题

夺宝大赛

夺宝大赛的地图是一个由 n×m 个方格子组成的长方形,主办方在地图上标明了所有障碍、以及大本营宝藏的位置。参赛的队伍一开始被随机投放在地图的各个方格里,同时开始向大本营进发。所有参赛队从一个方格移动到另一个无障碍的相邻方格(“相邻”是指两个方格有一条公共边)所花的时间都是 1 个单位时间。但当有多支队伍同时进入大本营时,必将发生火拼,造成参与火拼的所有队伍无法继续比赛。大赛规定:最先到达大本营并能活着夺宝的队伍获得胜利。

假设所有队伍都将以最快速度冲向大本营,请你判断哪个队伍将获得最后的胜利。

时间限制:5000

内存限制:65535

输入

输入首先在第一行给出两个正整数 m 和 n(2 < m,n ≤ 100),随后 m 行,每行给出 n 个数字,表示地图上对应方格的状态:1 表示方格可通过;0 表示该方格有障碍物,不可通行;2 表示该方格是大本营。题目保证只有 1 个大本营。 接下来是参赛队伍信息。首先在一行中给出正整数 k(0 < k < m×n/2),随后 k 行,第 i(1 ≤ i ≤ k)行给出编号为 i 的参赛队的初始落脚点的坐标,格式为 x y。这里规定地图左上角坐标为 1 1,右下角坐标为 n m,其中 n 为列数,m 为行数。注意参赛队只能在地图范围内移动,不得走出地图。题目保证没有参赛队一开始就落在有障碍的方格里。

输出

在一行中输出获胜的队伍编号和其到达大本营所用的单位时间数量,数字间以 1 个空格分隔,行首尾不得有多余空格。若没有队伍能获胜,则在一行中输出 No winner.

样例输入

样例1:

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

样例2:

5 7
1 1 1 1 1 0 1
1 1 1 1 1 0 0
1 1 0 2 1 1 1
1 1 0 0 1 1 1
1 1 1 1 1 1 1
7
7 5
1 3
7 1
1 1
5 5
3 1
3 5

样例输出

样例1:

7 6

样例2:

No winner.

提示

样例 1 说明: 七支队伍到达大本营的时间顺次为:7、不可能、5、3、3、5、6,其中队伍 4 和 5 火拼了,队伍 3 和 6 火拼了,队伍 7 比队伍 1 早到,所以获胜。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;map&gt; #include&lt;queue&gt; using namespace std; struct node{ int xt,yt; }; int u,v,n,m; int mp[111][111]; int ct[111][111]; int ans[10000]; int dx[4]={0,-1,0,1}; int dy[4]={-1,0,1,0}; void bfs(int x,int y){ queue&lt;node&gt;q; q.push({x,y}); while(!q.empty()){ node n1=q.front(); q.pop(); for(int i=0;i&lt;4;i++){ int xtp=n1.xt+dx[i]; int ytp=n1.yt+dy[i]; if(ct[xtp][ytp]||!mp[xtp][ytp]) continue; if(xtp&lt;=0||xtp&gt;n||ytp&lt;=0||ytp&gt;m) continue;     ct[xtp][ytp]=ct[n1.xt][n1.yt]+1;     q.push({xtp,ytp}); } } } int main(){ cin&gt;&gt;n&gt;&gt;m; for(int i=1;i&lt;=n;i++)   for(int j=1;j&lt;=m;j++)  {   scanf("%d",&amp;mp[i][j]);   if(mp[i][j]==2){   u=i,v=j;  }  }  bfs(u,v);  int k; cin&gt;&gt;k; for(int i=1;i&lt;=k;i++){ int a,b; scanf("%d%d",&amp;b,&amp;a); if(ct[a][b]){ if(ans[ct[a][b]]==0) ans[ct[a][b]]=i; else ans[ct[a][b]]=-1;     }     }     int flag=1;     for(int i=1;i&lt;10000;i++)     {      if(ans[i]&gt;0)      {      printf("%d %d",ans[i],i);      flag=0;      break; } } if(flag) printf("No winner.");   return 0; }</pre>
这道题暂未补解析。
2. 简答题

清点代码库

很久之前新浪微博有人发过:“阿里代码库有几亿行代码,但其中有很多功能重复的代码,比如单单快排就被重写了几百遍。请设计一个程序,能够将代码库中所有功能重复的代码找出。各位大佬有啥想法,我当时就懵了,然后就挂了。。。”

这里我们把问题简化一下:首先假设两个功能模块如果接受同样的输入,总是给出同样的输出,则它们就是功能重复的;其次我们把每个模块的输出都简化为一个整数(在 int 范围内)。于是我们可以设计一系列输入,检查所有功能模块的对应输出,从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

时间限制:7000

内存限制:262144

输入

输入在第一行中给出 2 个正整数,依次为 N(≤ 104)和 M(≤ 102),对应功能模块的个数和系列测试输入的个数。 随后 N 行,每行给出一个功能模块的 M 个对应输出,数字间以空格分隔。

输出

首先在第一行输出不同功能的个数 K。随后 K 行,每行给出具有这个功能的模块的个数,以及这个功能的对应输出。数字间以 1 个空格分隔,行首尾不得有多余空格。输出首先按模块个数非递增顺序,如果有并列,则按输出序列的递增序给出。 注:所谓数列 { A1, …, AM } 比 { B1, …, BM } 大,是指存在 1 ≤ i < M,使得 A1=B1,…,Ai=Bi 成立,且 Ai+1 > Bi+1。

样例输入

7 3
35 28 74
-1 -1 22
28 74 35
-1 -1 22
11 66 0
35 28 74
35 28 74

样例输出

4
3 35 28 74
2 -1 -1 22
1 11 66 0
1 28 74 35
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;bits/stdc++.h&gt; using namespace std; #define PII pair&lt;int,int&gt; const int INF = 0x3f3f3f3f; const int N = 1e4+10; struct cmp{ //自定义set排序     bool operator() (const pair&lt;int,vector&lt;int&gt; &gt;&amp;a, const pair&lt;int,vector&lt;int&gt; &gt;&amp;b) const{         if(a.first!=b.first) return a.first&gt;b.first;         else return a.second&lt;b.second;     } }; int main(){ int n, m; scanf("%d%d", &amp;n, &amp;m); set&lt;vector&lt;int&gt; &gt; st; //存模块 map&lt;vector&lt;int&gt;, int&gt; mp; //存每个模块的个数 set&lt;pair&lt;int,vector&lt;int&gt; &gt;,cmp &gt; St;//排序 for ( int i = 0 ; i &lt; n ; i ++ ){ vector&lt;int&gt; v; for ( int j = 0 ; j &lt; m ; j ++ ){ int x; scanf("%d", &amp;x); v.push_back(x); }         mp[v] ++;         st.insert(v); } printf("%d\n", st.size()); //把所有模块存入ST排序  set&lt;vector&lt;int&gt; &gt;::iterator it;     for(it = st.begin() ; it != st.end() ; it ++)      St.insert({mp[*it],*it}); //输出ST  set&lt;pair&lt;int,vector&lt;int&gt; &gt; &gt;::iterator ite;     for(ite = St.begin() ; ite != St.end() ; ite ++){      cout &lt;&lt; (*ite).first;         for(int i = 0; i &lt; (*ite).second.size() ; i++)             cout&lt;&lt;' '&lt;&lt;(*ite).second[i];         cout&lt;&lt;endl; } return 0; }</pre>
这道题暂未补解析。
3. 简答题

逆散列问题

给定长度为 N 的散列表,处理整数最常用的散列映射是 H(x) = x%N。如果我们决定用线性探测解决冲突问题,则给定一个顺序输入的整数序列后,我们可以很容易得到这些整数在散列表中的分布。例如我们将 1、2、3 顺序插入长度为 3 的散列表HT[]后,将得到HT[0]=3,HT[1]=1,HT[2]=2的结果。

但是现在要求解决的是“逆散列问题”,即给定整数在散列表中的分布,问这些整数是按什么顺序插入的?

时间限制:5000

内存限制:65536

输入

输入的第一行是正整数 N(≤ 1000),为散列表的长度。第二行给出了 N 个整数,其间用空格分隔,每个整数在序列中的位置(第一个数位置为0)即是其在散列表中的位置,其中负数表示表中该位置没有元素。题目保证表中的非负整数是各不相同的。

输出

按照插入的顺序输出这些整数,其间用空格分隔,行首尾不能有多余的空格。注意:对应同一种分布结果,插入顺序有可能不唯一。例如按照顺序 3、2、1 插入长度为 3 的散列表,我们会得到跟 1、2、3 顺序插入一样的结果。在此规定:当前的插入有多种选择时,必须选择最小的数字,这样就保证了最终输出结果的唯一性。

样例输入

11
33 1 13 12 34 38 27 22 32 -1 21

样例输出

1 13 12 21 33 34 38 27 22 32
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;vector&gt; using namespace std; int m; int main() { cin &gt;&gt; m; vector&lt;int&gt;v(m); vector&lt;int&gt;temp; for (int i = 0; i &lt; m; i++) { cin &gt;&gt; v[i]; if (v[i] != -1) temp.push_back(v[i]); } sort(temp.begin(), temp.end()); int length = temp.size(); vector&lt;bool&gt;finding_value(length, 0); vector&lt;bool&gt;hashtable(m, 0); int num = 0, index = 0; //length 为插入数据长度 while (num != length) { for (int i = 0; i &lt; length; i++) { if (!finding_value[i]) //如果这个值没有找到位置 { int posi = temp[i] % m; //temp[i]的线性探测初始位置 if (v[posi] == temp[i]) { printf("%d ", temp[i]); finding_value[i] = 1; hashtable[posi] = 1; num++; break; } else { for (int t = 0; t &lt; m; t++) { int new_posi = (posi + t) % m; if (hashtable[new_posi]) continue; if (!hashtable[new_posi] &amp;&amp; v[new_posi] != temp[i]) break; finding_value[i] = hashtable[new_posi] = 1; printf("%d ", temp[i]); num++; break; } } } } } }</pre>
这道题暂未补解析。
4. 简答题

可怜的简单题

九条可怜今年出了一道简单题 —— 打算按照如下的方式生成一个随机的整数数列 A:

1 . 最开始,数列 A 为空。

2 . 可怜会从区间 [1,n] 中等概率随机一个整数 i 加入到数列 A 中。

3 . 如果不存在一个大于 1 的正整数 w,满足 A 中所有元素都是 w 的倍数,数组 A 将会作为随机生成的结果返回。否则,可怜将会返回第二步,继续增加 A 的长度。

现在,可怜告诉了你数列 n 的值,她希望你计算返回的数列 A 的期望长度。

时间限制:60000

内存限制:1048576

输入

输入一行两个整数 n, p (1 ≤ n ≤ 1011, n < p ≤ 1012),p 是一个质数。

输出

在一行中输出一个整数,表示答案对 p 取模的值。具体来说,假设答案的最简分数表示为 x/y,你需要输出最小的非负整数 z 满足 y × z ≡ x mod p。

样例输入

样例1:

2 998244353

样例2:

100000000 998244353

样例输出

样例1:

2

样例2:

3054970
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; typedef long long ll; const int Lim=2.2e7, MAXN=Lim+10; ll n, p; inline ll fmul(ll a,ll x) { return (__int128)a*x%p; } inline ll fpow(ll a,ll x) { ll ans=1; for(;x;x&gt;&gt;=1,a=fmul(a, a) ) if(x&amp;1) ans=fmul(ans, a); return ans; } inline ll inv(ll a) { return fpow(a, p-2); } ll smu[MAXN]; int prime[MAXN],  cntprime; bool nprime[MAXN]; unordered_map&lt;ll, ll&gt;  M; inline ll summu(ll n){     if(n&lt;=Lim) return smu[n];     if(M.count(n)) return M[n];     for(ll r=n, l, d;r&gt;=1; r=l-1){         d=n/r;         l=n/(d+1)+1;         if(d&lt;=Lim||M.count(d)) continue;         ll tmp=1;         for(ll ll=2, rr, dd;ll&lt;=d;ll=rr+1){             dd=d/ll;             rr=d/dd;             if(dd&lt;=Lim) tmp-=fmul(rr-ll+1, smu[dd]);             else tmp-=fmul(rr-ll+1, M[dd]);         }         M[d]=(tmp%p+p)%p;     }     return M[n]; } inline void sieve(){     smu[1]=1;     for(int i=2;i&lt;=Lim;++i){         if(!nprime[i]) prime[++cntprime]=i, smu[i]=-1;         for(int j=1;j&lt;=cntprime;++j)             if(i*prime[j]&gt;Lim) break;             else if(i%prime[j]){                 nprime[i*prime[j]]=1;                 smu[i*prime[j]]=-smu[i];             }             else{                 nprime[i*prime[j]]=1;                 smu[i*prime[j]]=0;                 break;             }     }     for(int i=2;i&lt;=Lim;++i){         smu[i]+=smu[i-1];         if(smu[i]&gt;=p) smu[i]-=p;         else if(smu[i]&lt;0) smu[i]+=p;     } } int main(){     ios::sync_with_stdio(0);     cin.tie(0); cout.tie(0);     cin&gt;&gt;n&gt;&gt;p;     sieve();     ll ans=0;     summu(n);     for(ll l=2, r, d, tmp=n%p;l&lt;=n;l=r+1){         d=n/l;         r=n/d;         ans+=fmul( summu(r)-summu(l-1) , inv(d-tmp+p) );     }     ans=(ans%p+p)%p;     ans=( fmul(ans, n)+summu(n)+p )%p;     cout&lt;&lt;ans;     cout.flush();     return 0; }</pre>
这道题暂未补解析。