首页 › 试卷 › C/C++编程考级 › C/C++编程八级 › 青少年软件编程(C语言八级)等级考试真题试卷(2022年9月)

青少年软件编程(C语言八级)等级考试真题试卷(2022年9月) VIP

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

一、简答题

1. 简答题

道路

N个以 1 … N 标号的城市通过单向的道路相连:。每条道路包含两个参数:道路的长度和需要为该路付的通行费(以金币的数目来表示)

Bob and Alice 过去住在城市 1.在注意到Alice在他们过去喜欢玩的纸牌游戏中作弊后,Bob和她分手了,并且决定搬到城市N。他希望能够尽可能快的到那,但是他囊中羞涩。我们希望能够帮助Bob找到从1到N最短的路径,前提是他能够付的起通行费。

时间限制:1000

内存限制:65536

输入

第一行包含一个整数K, 0 <= K <= 10000, 代表Bob能够在他路上花费的最大的金币数。第二行包含整数N, 2 <= N <= 100, 指城市的数目。第三行包含整数R, 1 <= R <= 10000, 指路的数目. 接下来的R行,每行具体指定几个整数S, D, L 和 T来说明关于道路的一些情况,这些整数之间通过空格间隔: S is 道路起始城市, 1 <= S <= N D is 道路终点城市, 1 <= D <= N L is 道路长度, 1 <= L <= 100 T is 通行费 (以金币数量形式度量), 0 <= T <=100 注意不同的道路可能有相同的起点和终点。

输出

输入结果应该只包括一行,即从城市1到城市N所需要的最小的路径长度(花费不能超过K个金币)。如果这样的路径不存在,结果应该输出-1。

样例输入

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

样例输出

11
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; #include &lt;iostream&gt; #include &lt;vector&gt; using namespace std; struct Road {   int d, L, t; }; int N, K, R; vector&lt;vector&lt;Road&gt;&gt; G(110); // 用二维数组表示临界表,G[s]表示和s邻接的路 int minLen;                  // 全局变量,记录最短的路径长度 int totalCost;               // 当前状态的花费 int totalLen;                // 当前状态的长度 int visited[110]; int minL[110][10010]; // minL[i][j]的意义是当到达i点是花费为j时的最短路径 void Dfs(int s) {   if (s == N) {     minLen = min(minLen, totalLen);     return;   }   int len = G[s].size();   for (int i = 0; i &lt; len; i++) // 枚举和s相邻接额情况   {     Road r = G[s][i];     if (!visited[r.d]) // 如果没有被走过     {       /*下面三个if语句是三条剪枝条件*/       if (totalCost + r.t &gt; K) // 如果当前花销大于K了         continue;       if (totalLen + r.L &gt;=           minLen) // 如果当前的路径已经超过了已存在的最短路径,那就没必要往后dfs了         continue;       // 如果存在两种方式都到达同一点并且花销相同,但是如果当前的长度大于另一种方式的长度,则continue       if (totalLen + r.L &gt; minL[r.d][totalCost + r.t])         continue;       minL[r.d][totalCost + r.t] = totalLen + r.L;       visited[r.d] = 1;       totalCost += r.t;       totalLen += r.L;       Dfs(r.d);       visited[r.d] =           0; // 因为可能存在多种方式的dfs的路径,所以每次dfs之后都要还原到之前的状态       totalCost -= r.t;       totalLen -= r.L;     }   } } int main() {   cin &gt;&gt; K &gt;&gt; N &gt;&gt; R;   for (int i = 0; i &lt; R; i++) {     int s;     Road r;     cin &gt;&gt; s;     cin &gt;&gt; r.d &gt;&gt; r.L &gt;&gt; r.t;     G[s].push_back(r);   }   totalCost = 0;   totalLen = 0;   minLen = 1 &lt;&lt; 30; // 无穷大   memset(visited, 0, sizeof(visited));   for (int i = 1; i &lt;= N; i++)     for (int j = 0; j &lt; 10010; j++)       minL[i][j] = 1 &lt;&lt; 30;   visited[1] = 1;   Dfs(1);   if (minLen &lt; (1 &lt;&lt; 30))     cout &lt;&lt; minLen &lt;&lt; endl;   else     cout &lt;&lt; -1 &lt;&lt; endl;   return 0; }</pre>
这道题暂未补解析。
2. 简答题

控制公司

有些公司是其他公司的部分拥有者,因为他们获得了其他公司发行的股票的一部分。例如,福特公司拥有马自达公司12%的股票。据说,如果至少满足了以下条件之一,公司A就可以控制公司B了:

l 公司A = 公司B。

l 公司A拥有大于50%的公司B的股票。

l 公司A控制K(K >= 1)个公司,记为C1, …, CK,每个公司Ci拥有xi%的公司B的股票,并且x1+ … + xK > 50%。(ps:A可以控制自己,即Ci可以为A)

你将被给予一系列的三对数(i,j,p),表明公司i拥有公司j的p%的股票。计算所有的数对(h,s),表明公司h控制公司s。

写一个程序读入三对数(i,j,p),并且找出所有的数对(h,s),使得公司h控制公司s。

时间限制:1000

内存限制:65536

输入

第一行: N,表明接下来三对数的数量。 第二行到第N+1行:每行三个整数作为一个三对数(i,j,p),如上文所述。 I,J≤100,N,P≤100

输出

输出零个或更多个的控制其他公司的公司。每行包括两个整数表明序号为第一个整数的公司控制了序号为第二个整数的公司。将输出的每行以第一个数字升序排列(并且第二个数字也升序排列来避免并列)。请不要输出控制自己的公司。

样例输入

3
1 2 80
2 3 80
3 1 20

样例输出

1 2
1 3
2 3
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; unsigned long long int n, gf[1000][1000], mp[1000][1000]; void jf(int x, int y) // x公司加上i公司股票 {   for (int i = 1; i &lt;= 100; i++) {     if (gf[x][i] + gf[y][i] &gt; 100)       gf[x][i] = 100; // 判断     else       gf[x][i] += gf[y][i];   }   return; } void find(int x) // 递归 {   for (int i = 1; i &lt;= 100; i++) {     if (gf[x][i] &gt;= 50 &amp;&amp; mp[x][i] == 0 &amp;&amp; x != i) {       mp[x][i] = 1; // 标记 x公司可以控制i公司       jf(x, i);       find(x); // 加上以后再找一遍       return;     }   } } int main() {   cin &gt;&gt; n;   for (int i = 1; i &lt;= n; i++) {     int a, b, c;     cin &gt;&gt; a &gt;&gt; b &gt;&gt; c;     gf[a][b] = c;   }   int t = 1;   while (t &lt;= 100) // 枚举每一个公司   {     find(t);     t++;   }   for (int i = 1; i &lt;= 100; i++) {     for (int j = 1; j &lt;= 100; j++) {       if (mp[i][j] == 1)         cout &lt;&lt; i &lt;&lt; " " &lt;&lt; j &lt;&lt; endl;     }   } }</pre>
这道题暂未补解析。
3. 简答题

发现它,抓住它

一个城市中有两个犯罪团伙A和B,你需要帮助警察判断任意两起案件是否是同一个犯罪团伙所为,警察所获得的信息是有限的。假设现在有N起案件(N<=100000),编号为1到N,每起案件由团伙A或团伙B所为。你将按时间顺序获得M条信息(M<=100000),这些信息分为两类:

D [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息表明它们属于不同的团伙所为

A [a] [b]

其中[a]和[b]表示两起案件的编号,这条信息需要你回答[a]和[b]是否是同一个团伙所为

注意你获得信息的时间是有先后顺序的,在回答的时候只能根据已经接收到的信息做出判断。

时间限制:1000

内存限制:65536

输入

第一行是测试数据的数量T(1<=T<=20)。 每组测试数据的第一行包括两个数N和M,分别表示案件的数量和信息的数量,其后M行表示按时间顺序收到的M条信息。

输出

对于每条需要回答的信息,你需要输出一行答案。如果是同一个团伙所为,回答"In the same gang.“,如果不是,回答"In different gangs.”,如果不确定,回答”Not sure yet."。

样例输入

1
5 5
A 1 2
D 1 2
A 1 2
D 2 4
A 1 4

样例输出

Not sure yet.
In different gangs.
In the same gang.
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; template &lt;class T&gt; struct DisjointSet {   int *parent;   T *data;   map&lt;T, int&gt; m;   int capacity;   int size;   DisjointSet(int max = 1000) {     capacity = max;     size = 0;     parent = new int[max + 1];     data = new T[max + 1];   }   ~DisjointSet() {     delete[] parent;     delete[] data;   }   bool insert(T x) {     if (size == capacity)       return false;     size++;     data[size] = x;     parent[size] = -1;     m[x] = size;     return true;   }   int getIndex(T x) {     for (int i = 1; i &lt;= size; i++)       if (data[i] == x)         return i;     return -1;   }   int find(T x) {     typename map&lt;T, int&gt;::iterator it;     it = m.find(x);     if (it == m.end())       return -1;     int i, rt;     i = rt = it-&gt;second;     while (parent[rt] &gt; 0)       rt = parent[rt];     return rt;   }   void unionSet(T x, T y) {     int rx, ry;     rx = find(x);     ry = find(y);     if (rx == -1 || ry == -1)       return;     if (rx == ry)       return;     if (parent[rx] &lt; parent[ry]) {       parent[rx] += parent[ry];       parent[ry] = rx;     } else {       parent[ry] += parent[rx];       parent[rx] = ry;     }     find(x);     find(y);   } }; int main() {   int t;   cin &gt;&gt; t;   while (t--) {     DisjointSet&lt;int&gt; s;     int n, m;     cin &gt;&gt; n &gt;&gt; m;     for (int i = 1; i &lt;= n; i++)       s.insert(i);     for (int i = 1; i &lt;= m; i++) {       int a, b;       char c;       cin &gt;&gt; c &gt;&gt; a &gt;&gt; b;       if (c == 'D')         s.unionSet(a, b);       else {         if (s.find(a) != s.find(b))           cout &lt;&lt; "Not sure yet.";         else if (s.parent[a] == s.parent[b])           cout &lt;&lt; "In the same gang.";         else           cout &lt;&lt; "In different gangs.";         cout &lt;&lt; endl;       }     }   }   return 0; }</pre>
这道题暂未补解析。
4. 简答题

青蛙的约会

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙A和青蛙B,并且规定纬度线上东经0度处为原点,由东往西为正方向,单位长度1米,这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x,青蛙B的出发点坐标是y。青蛙A一次能跳m米,青蛙B一次能跳n米,两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

时间限制:1000

内存限制:65536

输入

输入只包括一行5个整数x,y,m,n,L,其中x≠y < 2000000000,0 < m、n < 2000000000,0 < L < 2100000000。

输出

输出碰面所需要的跳跃次数,如果永远不可能碰面则输出一行"Impossible"

样例输入

1 2 3 4 5

样例输出

4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;algorithm&gt; #include &lt;cmath&gt; #include &lt;iostream&gt; using namespace std; typedef long long ll; ll exgcd(ll a, ll b, ll &amp;x, ll &amp;y) {   if (b == 0) {     x = 1;     y = 0;     return a;   }   ll gcd = exgcd(b, a % b, y, x);   y -= (a / b) * x;   return gcd; } ll inv(ll a, ll b, ll c) {   ll x, y;   ll gcd = exgcd(a, b, x, y);   if (c % gcd != 0)     return -1;   x *= c / gcd; // 得到当前情况下的一个x   b /= gcd;     // 根据通解x = x0 + (b * t) / gcd 所以b = b / gcd   b = abs(       b); // 为了得到正数解,所以要abs,而且要在上一步/gcd之后,因为gcd可能是负的   ll ans = x % b;   if (ans &lt; 0)     ans += b;   return ans; } int main() {   ll x, y, n, m, L;   cin &gt;&gt; x &gt;&gt; y &gt;&gt; m &gt;&gt; n &gt;&gt; L;   ll res = inv(m - n, L, y - x);   if (res == -1)     cout &lt;&lt; "Impossible";   else     cout &lt;&lt; res;   return 0; }</pre>
这道题暂未补解析。