首页 › 试卷 › 信息学奥赛 › 信息学奥赛-入门级 › 2020年CCF非专业级别软件能力认证第二轮 (CSP-J)入门级C++语言试题

2020年CCF非专业级别软件能力认证第二轮 (CSP-J)入门级C++语言试题 VIP

信息学奥赛-入门级 共 4 题 2020 年 含标准答案与解析
返回试卷列表
本页为整卷浏览:先自己做一遍,再展开「查看答案与解析」核对。

一、简答题

1. 简答题

优秀的拆分(power)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; /* 定义:分解为了若干个不同的 2 的正整数次幂 性质:是偶数,奇数不存在优秀的拆分 思路: 如果n是偶数,将n进行进制转换 10 -&gt; 1010 */ int a[110],n,k = 0;//k表示a数组的下标 int main(){     cin&gt;&gt;n;     //特判奇数的情况     if(n % 2 != 0){         cout&lt;&lt;-1;         return 0;     }     //进制转换     int t = 1;//表示2的次方     while(n != 0){         if(n % 2 != 0){             k++;             a[k] = t;         }         t = t * 2;         n = n / 2;     }     //逆序输出结果     for(int i = k;i &gt;= 1;i--){         cout&lt;&lt;a[i]&lt;&lt;" ";     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
2. 简答题

直播获奖( live)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; /* 1.获奖人数为k = max(1, int(p × w%)) 2.选手的成绩均为不超过 600 的非负整数 思路:使用数组统计每个分值得分的人数 从大到小统计出k个人,最后一次循环对应的分值就是要求的获奖分数 */ int a[610]; int n,w,x; int main(){     scanf("%d%d",&amp;n,&amp;w);     int k;//获奖人数     int ans;//统计人数     //读入n个人的分数,读一个算一个     for(int i = 1;i &lt;= n;i++){         scanf("%d",&amp;x);         a[x]++;//统计每个分值对应的人数         //计算获奖人数         k = max(1,int(i * w / 100.0));         ans = 0;         //从最高分的人数向下统计出&gt;=k个人         for(int j = 600;j &gt;= 0;j--){             if(ans + a[j] &lt; k) ans += a[j];//+=             else{                 printf("%d ",j);                 break;             }         }     } return 0; }</pre><p><br/></p>
这道题暂未补解析。
3. 简答题

表达式(expr)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; /* 取反某一个操作数的值时,原表达式的值为多少 思路: 1.读入表达式,将表达式建成二叉树 2.计算出表达式的值 3.深搜,求出哪些结点的值修改后对结果有影响 */ const int N = 1e6 + 10; struct node{     int to,next; }a[N];//邻接表 int pre[N],k;//存储以每个点为起点的最后一条边的编号 int num[N];//存储二叉树每个结点的值 char c[N];//存储操作符 int m;//表示c数组的下标 bool f[N];//标记哪些点的值修改后对结果有影响 int n; string s,w;//w用来存储每个操作数的下标 stack&lt;int&gt; st;//用于计算后缀表达式 //建边 void add(int u,int v){     k++;     a[k].to = v;     a[k].next = pre[u];     pre[u] = k; } //深搜求哪些结点的值修改后对结果有影响 void dfs(int x){     f[x] = true;     if(x &lt;= n) return;//如果是叶子结点     if(c[x] == '!') dfs(a[pre[x]].to);     else{         int n1 = a[pre[x]].to,n2 = a[a[pre[x]].next].to;         if(c[x] == '&amp;'){             if(num[n1] == 1) dfs(n2);             if(num[n2] == 1) dfs(n1);         }else if(c[x] == '|'){             if(num[n1] == 0) dfs(n2);             if(num[n2] == 0) dfs(n1);         }     } } int main() {     getline(cin,s);     cin&gt;&gt;n;     for(int i = 1;i &lt;= n;i++){         scanf("%d",&amp;num[i]);     }     //分析表达式,建树     int x,y;     m = n;     for(int i = 0;i &lt; s.size();i++){         if(isdigit(s[i])){             w = w + s[i];             //如果连续数字结束             if(i==s.size()-1||!isdigit(s[i+1])){                 st.push(atoi(w.c_str()));//将操作数的下标入栈                 w = "";             }         }else if(s[i] == '!'){             //如果是取反操作符             m++;             c[m] = s[i];//操作符的编号是m             x = st.top();//取栈顶元素来运算             st.pop(); //出栈             //建边             add(m,x);             num[m] = !num[x];             st.push(m);         }else if(s[i] == '&amp;' || s[i] == '|'){             //如果是&amp; |操作符             m++;             c[m] = s[i];             //取2个操作数             x = st.top();             st.pop();             y = st.top();             st.pop();             //建边             add(m,x);             add(m,y);             //计算结点的值             if(s[i] == '&amp;') num[m] = num[x] &amp; num[y];             else if(s[i] == '|') num[m] = num[x] | num[y];             st.push(m);         }     }     int ans = num[st.top()];     //cout&lt;&lt;ans;     //深搜求哪些结点的值修改后对结果有影响     dfs(st.top());//从根开始深搜     //q次询问     int q;     cin&gt;&gt;q;     while(q--){         scanf("%d",&amp;x);         if(f[x]==true) printf("%d\n",!ans);         else printf("%d\n",ans);     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。
4. 简答题

方格取数(number)


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;bits/stdc++.h&gt; using namespace std; /* 左上角走到右下角 每一步只能向上、向下或向右走一格 不能重复经过已经走过的方格 计算的结果,要用long long */ const int N = 1010; int a[N][N];//读入的每个点的值 typedef long long LL; LL f[N][N]; int n,m; int main(){     scanf("%d%d",&amp;n,&amp;m);     for(int i = 1;i &lt;= n;i++){         for(int j = 1;j &lt;= m;j++){             scanf("%d",&amp;a[i][j]);         }     }     /*     DP求出走到每个点经过的数字和的最大值     一列一列求,对于每一列而言,要求从上向下走到每个点经过的数字和的最大值     也要求从下向上走到每个点经过的数字和的最大值     */     memset(f,-0x7f,sizeof(f));     LL ma;//走到每个格子经过的数字和最大     f[1][0] = 0;     for(int j = 1;j &lt;= m;j++){         //从上向下求         ma = -1e18;         for(int i = 1;i &lt;= n;i++){             ma = max(ma,f[i][j-1]) + a[i][j];             f[i][j] = max(f[i][j],ma);         }         //从下向上求         ma = -1e18;         for(int i = n;i &gt;= 1;i--){             ma = max(ma,f[i][j-1]) + a[i][j];             f[i][j] = max(f[i][j],ma);         }     } cout&lt;&lt;f[n][m]; return 0; }</pre><p><br/></p>
这道题暂未补解析。