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

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

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

一、简答题

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;iostream&gt; #include&lt;algorithm&gt; #include&lt;cmath&gt; #include&lt;cstdio&gt; #include&lt;vector&gt; #include&lt;cstring&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><p><br/></p>
这道题暂未补解析。
2. 简答题

Rainbow的商店

Rainbow开了一家商店,在一次进货中获得了N个商品。

已知每个商品的利润和过期时间。

Rainbow每天只能卖一个商品,并且过期商品不能再卖。

Rainbow也可以选择在每天出售哪个商品,并且一定可以卖出。

由于这些限制,Rainbow需要制定一份合理的售卖计划。请你计算一下,Rainbow最终可以获得的最大收益。

时间限制:1000

内存限制:262144

输入

第一行两个整数N。 接下来N行每行两个整数,分别表示每个商品的利润、过期时间。 1<=N,利润,时间<=10000。

输出

输出一个整数,表示Rainbow最终可以获得的最大收益。

样例输入

7
20 1
2 1
10 3
100 2
8 2
5 20
50 10

样例输出

185

提示

第1天卖出20 第2天卖出100 第3天卖出10 第4天卖出50(实际上只要在第10天卖就可以) 第5天卖出5(实际上只要在第20天前卖就可以) 总计185 其它2件商品由于过期、每天只能卖一个的限制,在最优策略下应该不出售。

查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;algorithm&gt; #include&lt;queue&gt; #pragma warning (disable:4996); using namespace std; int N; struct Goods { int w; int d; friend bool operator &lt;(const Goods a, const Goods b) { if (a.w != b.w) { return a.w &lt; b.w;//大的天数小的在前 } else { return a.d &gt; b.d; } } }good[10005]; bool vis[10005] = {}; int main() { cin &gt;&gt; N; priority_queue&lt;Goods&gt;que; int maxval=0; for (int i = 1; i &lt;= N; i++) { scanf("%d %d", &amp;good[i].w, &amp;good[i].d); que.push(good[i]); } while (!que.empty()) { Goods now = que.top(); que.pop(); for (int i = now.d; i &gt;= 1; i--) { if (!vis[i]) { vis[i] = 1; maxval += now.w; break; } } } printf("%d\n", maxval); return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

冰阔落 I

老王喜欢喝冰阔落。

初始时刻,桌面上有n杯阔落,编号为1到n。老王总想把其中一杯阔落倒到另一杯中,这样他一次性就能喝很多很多阔落,假设杯子的容量是足够大的。

有m 次操作,每次操作包含两个整数x与y。

若原始编号为x 的阔落与原始编号为y的阔落已经在同一杯,请输出"Yes";否则,我们将原始编号为y 所在杯子的所有阔落,倒往原始编号为x 所在的杯子,并输出"No"。

最后,老王想知道哪些杯子有冰阔落。

 

时间限制:10000

内存限制:65536

输入

有多组测试数据,少于 5 组。 每组测试数据,第一行两个整数 n, m (n, m<=50000)。接下来 m 行,每行两个整数 x, y (1<=x, y<=n)。

输出

每组测试数据,前 m 行输出 "Yes" 或者 "No"。 第 m+1 行输出一个整数,表示有阔落的杯子数量。 第 m+2 行有若干个整数,从小到大输出这些杯子的编号。

样例输入

3 2
1 2
2 1
4 2
1 2
4 3

样例输出

No
Yes
2
1 3 
No
No
2
1 4
查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; string str; int a[50000+5],cnt; int root(int x) {     if(a[x]==x) return x;     return root(a[x]); } void find(int l,int r) {     int ll=root(l),rr=root(r);     if(ll==rr)     {         printf("Yes\n");         //cout&lt;&lt;"Yes"&lt;&lt;endl;     }     else     {         a[rr] =ll;         cnt--;         //cout&lt;&lt;"No"&lt;&lt;endl;         printf("No\n");     } } int main() {     int m,n,l,r;     while(scanf("%d %d",&amp;n,&amp;m)!=EOF)     {         cnt=n;         for(int i=1;i&lt;=n;i++)         {             a[i]=i;         }         for(int i=1;i&lt;=m;i++)         {             scanf("%d %d",&amp;l,&amp;r);             //cin&gt;&gt;l&gt;&gt;r;             find(l,r);         }         printf("%d\n",cnt);         //cout&lt;&lt;cnt&lt;&lt;endl;         for(int i=1;i&lt;=n;i++)             if(a[i]==i) printf("%d ",i);//cout&lt;&lt;i&lt;&lt;" ";         //cout&lt;&lt;endl;         printf("\n");     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

青蛙的约会(2023年5月8级)

两只青蛙在网上相识了,它们聊得很开心,于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上,于是它们约定各自朝西跳,直到碰面为止。可是它们出发之前忘记了一件很重要的事情,既没有问清楚对方的特征,也没有约定见面的具体位置。不过青蛙们都是很乐观的,它们觉得只要一直朝着某个方向跳下去,总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上,不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙,你被要求写一个程序来判断这两只青蛙是否能够碰面,会在什么时候碰面。 我们把这两只青蛙分别叫做青蛙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;iostream&gt; #include&lt;cmath&gt; #include&lt;algorithm&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><p><br/></p>
这道题暂未补解析。