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

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

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

一、简答题

1. 简答题

数字游戏


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;cstring&gt; using namespace std;   int main(){        char str[10];        cin &gt;&gt; str;        int ans=0;        for(int i=0;i&lt;8;i++){//题意说了,长度固定是8               if(str[i]=='1'){                      ans++;               }        }        cout &lt;&lt; ans&lt;&lt;endl;          return 0; }</pre><p><br/></p>
解析:

这道题考察字符串的操作、循环结构、分支结构等知识点。输入字符串,注意看题的最后,总长度是8.遍历字符串中每一个字符,如果字符为1则计数变量加一,最后输出计算变量的值。 

2. 简答题

公交换乘


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #include &lt;cmath&gt; #include &lt;cstring&gt; using namespace std; struct tra{        int kind,value,time; }a[100005]; //保存打折车票的位置   车票的数量 int discount[100005],number; int main() {        int ans=0;        int n,start=1;        cin&gt;&gt;n;        //每张车票都要判断        for(int i=1;i&lt;=n;i++){               cin&gt;&gt;a[i].kind&gt;&gt;a[i].value&gt;&gt;a[i].time ;               if(a[i].kind==0){//地铁票,需要花费                     discount[++number]=i;                     ans+=a[i].value;               }               else{                      int j=0;                      for(j=start;j&lt;=number;j++){//超时的优惠票,没有用,舍弃                             int t=discount[j];                             if(a[i].time-a[t].time &gt;45) {                                    start++;                                    continue;                             }                             if(a[i].value &lt;=a[t].value){//未超时,且票据小于等于地铁票,可以用                                    a[t].value=0;                                    break;                             }                                                       }                      if(j&gt;number) {//没有优惠券                             ans+=a[i].value;                      }               }        }        //输出答案        cout&lt;&lt;ans&lt;&lt;endl;        return 0; }</pre><p><br/></p>
解析:

和2016年海港有些像,模拟题。

车票有2中,如果是地铁票,必须要花钱。如果是公交车票,就不一定了。

如果45分钟内,有做过的地铁票,并且费用大于等于公交车的,就免费;

否则要花费。

3. 简答题

纪念品


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;cstring&gt; using namespace std;   int T,N,M; int dp[10001]; int price[101][10001]; int main(){        cin&gt;&gt;T&gt;&gt;N&gt;&gt;M;        for(int i=1;i&lt;=T;i++){               for(int j=1;j&lt;=N;j++){                      cin&gt;&gt;price[i][j];               }        }        int maxn=0;        for(int i=2;i&lt;=T;i++){               maxn=0;               memset(dp,0,sizeof(dp));               for(int j=1;j&lt;=N;j++){                      for(int k=price[i-1][j];k&lt;=M;k++){                             dp[k]=max(dp[k],dp[k-price[i-1][j]]+price[i][j]-price[i-1][j]);                             maxn=max(maxn,dp[k]);                      }               }               M+=maxn;        }        cout &lt;&lt;M&lt;&lt; endl;          return 0; }</pre><p><br/></p>
解析:

如果只有1天的话,买了再卖,总共剩下M个金币。

T天N种纪念币,根据题目设定范围,100以内,可以用二维表格推导。

时间不可逆,只能1~N。

每天买哪些纪念品呢?根据测试样例分析,纪念品任意多,没有个数限制。根据金币的上限,可以推到出这个就是完全背包。大家可以套一下完全背包的算法。每天需要做一次完全背包处理,当天不想卖出金币,相当于卖出金币再买入金币。

4. 简答题

加工零件


查看答案与解析
答案:<pre class="brush:cpp;toolbar:false">#include&lt;iostream&gt; #include&lt;queue&gt; #include&lt;cstring&gt; #include&lt;cstdio&gt; using namespace std; const int MAXN=1e5+5; const int MAXM=2e5+5; int n,m,que; int head[MAXN],v[MAXM],next[MAXM],cnt=0; int dis[MAXN][2]; void add_edge(int s,int t){        v[++cnt]=t;        next[cnt]=head[s];        head[s]=cnt; } void spfa(){        //0表示偶数        //1表示奇数        memset(dis,0x3f,sizeof(dis));        dis[1][0]=0;//起始路径0        queue&lt;int&gt; q;//队列实现        q.push(1);        while(!q.empty()){               int cur=q.front();               q.pop();               for(int i=head[cur];i;i=next[i]){                      int np=v[i];                      if(dis[cur][0]+1&lt;dis[np][1] || dis[cur][1]+1&lt;dis[np][0])                             q.push(np);                      dis[np][1]=min(dis[np][1],dis[cur][0]+1);                      dis[np][0]=min(dis[np][0],dis[cur][1]+1);               }        } } int main(){        scanf("%d%d%d",&amp;n,&amp;m,&amp;que);        for(int i=0;i&lt;m;i++){               int u,v;               scanf("%d%d",&amp;u,&amp;v);               add_edge(u,v);               add_edge(v,u);        }        spfa();        while(que--){               int a,l;               scanf("%d%d",&amp;a,&amp;l);               if(head[1]&amp;&amp;dis[a][l&amp;1]&lt;=l)printf("Yes\n");               else printf("No\n");        }        return 0; }</pre><p><br/></p>
解析:

这道题考察图论的知识运用,是属于最短路径的变形题目,可以利用spfa或Dijkstra来完成,难度较高。

根据性质,工人之间的关系是图。相连接,之间的路径权值是1。加工零件的过程可以相互传递,来回都是偶数次,因此在求个最短路时看奇偶步数内能否可达,要求与L的奇偶性一致。