首页 › 试卷 › 信息学奥赛 › 信息学奥赛-入门级 › 全国信息学(计算机)奥林匹克联赛(NOIP2013)复赛 普及组

全国信息学(计算机)奥林匹克联赛(NOIP2013)复赛 普及组 VIP

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

一、简答题

1. 简答题

记数问题

【问题描述】

试计算在区间 1 到 n 的所有整数中,数字 x(0 ≤ x ≤ 9)共出现了多少次?例如,在 1到 11 中,即在 1、2、3、4、5、6、7、8、9、10、11 中,数字 1 出现了 4 次。

【输入】

输入文件名为 count.in。

输入共 1 行,包含 2 个整数 n、x,之间用一个空格隔开。

【输出】

输出文件名为 count.out。

输出共 1 行,包含一个整数,表示 x 出现的次数。

【输入输出样例】

【数据说明】

对于 100%的数据,1≤ n ≤ 1,000,000,0 ≤ x ≤ 9。

查看答案与解析
答案:<p>#include&lt;iostream&gt;</p><p>using namespace std;</p><p>int main()</p><p>{</p><p>    long long n,i,x,b,c,t=0;</p><p>    cin&gt;&gt;n&gt;&gt;x;//输入范围与要查的数字;</p><p>    for(i=1;i&lt;=n;i++)//一到n进行循环;</p><p>    {</p><p>        b=i;//为了不改变i的值,就把i赋值给一个数;</p><p>        while(b!=0)//如果b不等于0,继续循环;</p><p>        {</p><p>            c=b%10;//求是否是x,是的话计数器加一;</p><p>            b=b/10;//求下一个数字是否为x;</p><p>            if(c==x) t++;计数器加一;</p><p>        }</p><p>    }</p><p>    cout&lt;&lt;t&lt;&lt;endl;//输出计数器的数字;</p><p>    return 0;//结束</p><p>}</p>
这道题暂未补解析。
2. 简答题

表达式求值

【问题描述】

给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。

【输入】

输入文件为 expr.in。

输入仅有一行,为需要你计算的表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为 0 到之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。

【输出】

输出文件名为 expr.out。

输出只有一行,包含一个整数,表示这个表达式的值。注意:当答案长度多于 4 位时,请只输出最后 4 位,前导 0 不输出。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【输入输出样例说明】

样例 1 计算的结果为 8,直接输出 8。

样例 2 计算的结果为 1234567891,输出后 4 位,即 7891。

样例 3 计算的结果为 1000000004,输出后 4 位,即 4。

【数据范围】

对于 30%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100;

对于 80%的数据,0≤表达式中加法运算符和乘法运算符的总数≤1000;

对于 100%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100000。

查看答案与解析
答案:<p>#include&lt;cstdio&gt;</p><p>#include&lt;iostream&gt;</p><p>using namespace std;</p><p><br/></p><p>int sum=0,num,tmp;  //定义和,要操作的数,临时数 </p><p>int main()</p><p>{</p><p><span style="white-space:pre"> </span>char op;  //定义操作符 </p><p><span style="white-space:pre"> </span>scanf("%d",&amp;num);  //首先读入一个数字,之后就是一个符号和一个数字的格式</p><p><span style="white-space:pre"> </span>while(scanf("%c",&amp;op) &amp;&amp; op !='\n')   //没有遇到回车符就继续读入</p><p><span style="white-space:pre"> </span>{</p><p><span style="white-space:pre"> </span>scanf("%d",&amp;tmp);  //读入第二个数,根据上面的符号进行下面的操作</p><p><span style="white-space:pre"> </span>if(op == '+')</p><p><span style="white-space:pre"> </span>{</p><p><span style="white-space:pre"> </span>sum=(sum+num)%10000; //遇到加号就加上上一段的值, </p><p><span style="white-space:pre"> </span>num=tmp;  //将每次读入的数 赋值给num </p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>else //除了加号就是乘号 </p><p><span style="white-space:pre"> </span>{</p><p><span style="white-space:pre"> </span>num=(num*tmp)%10000;  //遇到乘号先把两个数乘起来 </p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>} </p><p><span style="white-space:pre"> </span>sum=(sum+num)%10000; //因为我们每次都是先读取符号再操作上一步的值,所以要加上最后一步操作的值。 </p><p><span style="white-space:pre"> </span>printf("%d",sum);</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>return 0; </p><p>}</p>
这道题暂未补解析。
3. 简答题

小朋友的数字

【问题描述】

有 n 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 p 取模后

输出。

【输入】

输入文件为 number.in。

第一行包含两个正整数 n、p,之间用一个空格隔开。

第二行包含 n 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。

【输出】

输出文件名为 number.out。

输出只有一行,包含一个整数,表示最大分数对 p 取模的结果。

【输入输出样例 1】

【输入输出样例说明】

小朋友的特征值分别为 1、3、6、10、15,分数分别为 1、2、5、11、21,最大值 21对 997 的模是 21。

【输入输出样例 2】

【输入输出样例说明】

小朋友的特征值分别为-1、-1、-1、-1、-1,分数分别为-1、-2、-2、-2、-2,最大值

-1 对 7 的模为-1,输出-1。

【数据范围】

对于 50%的数据,1 ≤ n ≤ 1,000,1 ≤ p ≤ 1,000所有数字的绝对值不超过 1000;

对于 100%的数据,其他数字的绝对值均不超过


查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">#define int __int128</p><p style="text-align: left;">int read(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x=0,f=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>char c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(c&gt;'9'||c&lt;'0'){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='-'){</p><p style="text-align: left;"><span style="white-space:pre"> </span>f=-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(c&lt;='9'&amp;&amp;c&gt;='0'){</p><p style="text-align: left;"><span style="white-space:pre"> </span>x=x*10+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p style="text-align: left;">void write(int x){</p><p style="text-align: left;">    if(x&lt;0) putchar('-'),x=-x;</p><p style="text-align: left;">    if(x&gt;9) write(x/10);</p><p style="text-align: left;">    putchar(x%10+'0');</p><p style="text-align: left;">}</p><p style="text-align: left;">int n,p,f[1000006],ca,te[1000006],score[1000006],ans;</p><p style="text-align: left;">signed main(){</p><p style="text-align: left;">//<span style="white-space:pre"> </span>freopen("number.in","r",stdin);</p><p style="text-align: left;">//<span style="white-space:pre"> </span>freopen("number.out","w",stdout);</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>p=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>ca=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>te[1]=f[1]=ca;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=2;i&lt;=n;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>ca=read();</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[i]=max(ca,f[i-1]+ca);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>int maxx=f[1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=2;i&lt;=n;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>te[i]=max(f[i],maxx);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(f[i]&gt;maxx){</p><p style="text-align: left;"><span style="white-space:pre"> </span>maxx=f[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>score[1]=te[1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>int temp=score[1]+te[1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=score[1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=2;i&lt;=n;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>score[i]=temp;</p><p style="text-align: left;"><span style="white-space:pre"> </span>temp=max(temp,score[i]+te[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=max(ans,score[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>write(ans%p);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
4. 简答题

车站分级

【问题描述】

一条单向的铁路线上,依次有编号为 1, 2, …, n 的 n 个火车站。每个火车站都有一个级别,最低为 1 级。现有若干趟车次在这条线路上行驶,每一趟都满足如下要求:如果这趟车次停靠了火车站 x,则始发站、终点站之间所有级别大于等于火车站 x 的都必须停靠。(注意:起始站和终点站自然也算作事先已知需要停靠的站点)

例如,下表是 5 趟车次的运行情况。其中,前 4 趟车次均满足要求,而第 5 趟车次由于停靠了 3 号火车站(2 级)却未停靠途经的 6 号火车站(亦为 2 级)而不满足要求。

现有 m 趟车次的运行情况(全部满足要求),试推算这 n 个火车站至少分为几个不同的级别。

【输入】

输入文件为 level.in。

第一行包含 2 个正整数 n, m,用一个空格隔开。

第 i + 1 行(1 ≤ i ≤ m)中,首先是一个正整数 si(2 ≤ si ≤ n),表示第 i 趟车次有 si 个停靠站;接下来有 si个正整数,表示所有停靠站的编号,从小到大排列。每两个数之间用一个空格隔开。输入保证所有的车次都满足要求。

【输出】

输出文件为 level.out。

输出只有一行,包含一个正整数,即 n 个火车站最少划分的级别数。

【输入输出样例】

【数据范围】

对于 20%的数据,1 ≤ n, m ≤ 10;

对于 50%的数据,1 ≤ n, m ≤ 100;

对于 100%的数据,1 ≤ n, m ≤ 1000。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define in  read()</p><p style="text-align: left;">#define N 10009</p><p style="text-align: left;">#define M 9000009 </p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">inline char nc(){</p><p style="text-align: left;">    static char buf[100000],*p1=buf,*p2=buf;</p><p style="text-align: left;">    return p1==p2&amp;&amp;(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int read(){</p><p style="text-align: left;">    char ch=nc();int sum=0;</p><p style="text-align: left;">    while(!(ch&gt;='0'&amp;&amp;ch&lt;='9'))ch=nc();</p><p style="text-align: left;">    while(ch&gt;='0'&amp;&amp;ch&lt;='9')sum=sum*10+ch-48,ch=nc();</p><p style="text-align: left;">    return sum;</p><p style="text-align: left;">}</p><p style="text-align: left;">int n,m,du[N],chu[N];</p><p style="text-align: left;">int nxt[M],to[M],head[N],cnt=0;</p><p style="text-align: left;">void add(int x,int y){nxt[++cnt]=head[x];head[x]=cnt;to[cnt]=y;}</p><p style="text-align: left;">int s[N],g[1009][1009],dis[N];</p><p style="text-align: left;">bool vis[1009];</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=in;m=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>int i,j,k;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i&lt;=m;++i){</p><p style="text-align: left;"><span style="white-space:pre"> </span>k=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(vis,0,sizeof(vis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(j=1;j&lt;=k;++j){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int hh=in;</p><p style="text-align: left;"><span style="white-space:pre"> </span>s[j]=hh;vis[hh]=1;<span style="white-space:pre"> </span></p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(j=s[1];j&lt;=s[k];++j){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[j]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int p=1;p&lt;=k;++p){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!g[s[p]][j]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[s[p]][j]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>add(s[p],j);</p><p style="text-align: left;"><span style="white-space:pre"> </span>du[j]++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>queue&lt;int&gt; q;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(i=1;i&lt;=n;++i)</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!du[i]) dis[i]=1,q.push(i);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ans=-1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(!q.empty()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int u=q.front();q.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int e=head[u];e;e=nxt[e]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int v=to[e];</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[v]=dis[u]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=max(ans,dis[v]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>du[v]--;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!du[v]) q.push(v);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>cout&lt;&lt;ans;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。