首页 › 试卷 › 信息学奥赛 › 信息学奥赛-提高级 › 全国信息学(计算机)奥林匹克联赛(NOIP2008)复赛 提高组

全国信息学(计算机)奥林匹克联赛(NOIP2008)复赛 提高组 VIP

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

一、简答题

1. 简答题

笨小猴

【问题描述】

笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!

这种方法的具体描述如下:假设 maxn 是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果 maxn-minn 是一个质数,那么笨小猴就认为这是个 Lucky Word,这样的单词很可能就是正确的答案。

【输入】

输入文件 word.in 只有一行,是一个单词,其中只可能出现小写字母,并且长度小于 100。

【输出】

输出文件 word.out 共两行,第一行是一个字符串,假设输入的的单词是 Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;

第二行是一个整数,如果输入单词是 Lucky Word,输出 maxn-minn 的值,否则输出 0。 

【输入输出样例 1】

【输入输出样例 1 解释】

单词 error 中出现最多的字母 r 出现了 3 次,出现次数最少的字母出现了 1 次,3-1=2,2 是质数。

【输入输出样例 2】

【输入输出样例 2 解释】

单词 olympic 中出现最多的字母 i 出现了 2 次,出现次数最少的字母出现了 1 次,2-1=1,1不是质数。

查看答案与解析
答案:<p>#include&lt;bits/stdc++.h&gt;  //万能头文件</p><p>using namespace std;</p><p>int primenum(int m);  //质数的判断</p><p>int main()</p><p>{</p><p><span style="white-space:pre"> </span>char ch[1000];</p><p><span style="white-space:pre"> </span>int array[100]={0};</p><p><span style="white-space:pre"> </span>int m,n,i,j,k;</p><p><span style="white-space:pre"> </span>int maxn=-500,minn=9999;</p><p><span style="white-space:pre"> </span>scanf("%s",ch);</p><p><span style="white-space:pre"> </span>for(int m=0;m&lt;strlen(ch);m++){</p><p><span style="white-space:pre"> </span>array[ch[m]-'a']++;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>for(int m=0;m&lt;26;m++){</p><p><span style="white-space:pre"> </span>if(array[m]&gt;maxn&amp;&amp;array[m]!=0) maxn=array[m];</p><p><span style="white-space:pre"> </span>if(array[m]&lt;minn&amp;&amp;array[m]!=0) minn=array[m];</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>if(primenum(maxn-minn)){</p><p><span style="white-space:pre"> </span>printf("Lucky Word\n%d",maxn-minn);</p><p><span style="white-space:pre"> </span>}else{</p><p><span style="white-space:pre"> </span>printf("No Answer\n0");</p><p><span style="white-space:pre"> </span>}</p><p>}</p><p>int primenum(int m)</p><p>{</p><p><span style="white-space:pre"> </span>int i;</p><p><span style="white-space:pre"> </span>if(m==2||m==3)<span style="white-space:pre"> </span>return 1;</p><p><span style="white-space:pre"> </span>if(m==1||m==0)<span style="white-space:pre"> </span>return 0;</p><p><span style="white-space:pre"> </span>if(m%6!=1&amp;&amp;m%6!=5) return 0;  //优化质数的判断方法</p><p><span style="white-space:pre"> </span>for(i=5;i&lt;=sqrt(m);i+=5){</p><p><span style="white-space:pre"> </span>if(m%i==0||m%(i+2)==0){</p><p><span style="white-space:pre"> </span>return 0;</p><p><span style="white-space:pre"> </span>}<span style="white-space: pre;"> </span></p>
这道题暂未补解析。
2. 简答题

火柴棒等式

【问题描述】

给你 n 根火柴棍,你可以拼出多少个形如“A+B=C”的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0)。用火柴棍拼数字 0-9 的拼法如图所示:

注意:

1. 加号与等号各自需要两根火柴棍

2. 如果 A≠B,则 A+B=C 与 B+A=C 视为不同的等式(A、B、C>=0)

3. n 根火柴棍必须全部用上

【输入】

输入文件 matches.in 共一行,又一个整数 n(n<=24)。

【输出】

输出文件 matches.out 共一行,表示能拼成的不同等式的数目。

【输入输出样例 1】

【输入输出样例 1 解释】

2 个等式为 0+1=1 和 1+0=1。 

【输入输出样例 2】

【输入输出样例 2 解释】

9 个等式为:

0+4=4

0+11=11

1+10=11

2+2=4

2+7=9

4+0=4

7+2=9

10+1=11

11+0=11

查看答案与解析
答案:<p>#include&lt;bits/stdc++.h&gt;</p><p>using namespace std;</p><p>int a[10]={6,2,5,5,4,5,6,3,7,6};</p><p>int s[2010]={6}; </p><p>int main(){</p><p><span style="white-space:pre"> </span>int n;</p><p><span style="white-space:pre"> </span>scanf("%d",&amp;n);</p><p><span style="white-space:pre"> </span>int sum=0;</p><p><span style="white-space:pre"> </span>for(int i=0;i&lt;=2000;i++){</p><p><span style="white-space:pre"> </span>int t=i;</p><p><span style="white-space:pre"> </span>while(t){</p><p><span style="white-space:pre"> </span>s[i]+=a[t%10];</p><p><span style="white-space:pre"> </span>t/=10;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>for(int i=0;i&lt;=1000;i++){</p><p><span style="white-space:pre"> </span>for(int j=0;j&lt;=1000;j++){</p><p><span style="white-space:pre"> </span>if(s[i]+s[j]+s[i+j]+4==n) sum++;</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>printf("%d\n",sum); </p><p><span style="white-space:pre"> </span>return 0;</p><p>} </p>
这道题暂未补解析。
3. 简答题

传纸条

【问题描述】

小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个 m 行 n 列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1),小轩坐在矩阵的右下角,坐标(m,n)。从小渊传到小轩的纸条只可以向下或者向右传递,从小轩传给小渊的纸条只可以向上或者向左传递。

在活动进行中,小渊希望给小轩传递一张纸条,同时希望小轩给他回复。班里每个同学都可以帮他们传递,但只会帮他们一次,也就是说如果此人在小渊递给小轩纸条的时候帮忙,那么在小轩递给小渊的时候就不会再帮忙。反之亦然。

还有一件事情需要注意,全班每个同学愿意帮忙的好感度有高有低(注意:小渊和小轩的好心程度没有定义,输入时用 0 表示),可以用一个 0-100 的自然数来表示,数越大表示越好心。小渊和小轩希望尽可能找好心程度高的同学来帮忙传纸条,即找到来回两条传递路径,使得这两条路径上同学的好心程度只和最大。现在,请你帮助小渊和小轩找到这样的两条路径。

【输入】

输入文件 message.in 的第一行有 2 个用空格隔开的整数 m 和 n,表示班里有 m 行 n 列(1<=m,n<=50)。

接下来的 m 行是一个 m*n 的矩阵,矩阵中第 i 行 j 列的整数表示坐在第 i 行 j 列的学生的好心程度。每行的 n 个整数之间用空格隔开。

【输出】

输出文件 message.out 共一行,包含一个整数,表示来回两条路上参与传递纸条的学生的好心程度之和的最大值。

【输入输出样例】

【限制】

30%的数据满足:1<=m,n<=10

100%的数据满足:1<=m,n<=50

查看答案与解析
答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p> </p><p style="text-align: left;">int n,m,s[101][101],dp[101][101][101];</p><p> </p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    freopen("message.in","r",stdin);</p><p style="text-align: left;">    freopen("message.ans","w",stdout);</p><p style="text-align: left;">    std::cin&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;">    for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;">        for(int j=1;j&lt;=m;j++)   </p><p style="text-align: left;">            std::cin&gt;&gt;s[i][j];</p><p style="text-align: left;">    for(int i=3;i&lt;=m+n;i++)</p><p style="text-align: left;">        for(int j=1;j&lt;=std::min(i-1,n);j++)</p><p style="text-align: left;">            for(int k=1;k&lt;=std::min(i-1,n);k++){</p><p style="text-align: left;">                if(i&lt;m+n&amp;&amp;j==k)continue;</p><p style="text-align: left;">                dp[i][j][k]=std::max(dp[i-1][j][k],dp[i-1][j-1][k-1]);</p><p style="text-align: left;">                if(j-1!=k)dp[i][j][k]=std::max(dp[i][j][k],dp[i-1][j-1][k]);</p><p style="text-align: left;">                if(k-1!=j)dp[i][j][k]=std::max(dp[i][j][k],dp[i-1][j][k-1]);</p><p style="text-align: left;">                dp[i][j][k]+=s[j][i-j]+s[k][i-k];</p><p style="text-align: left;">            }</p><p style="text-align: left;">    std::cout&lt;&lt;dp[m+n][n][n]&lt;&lt;std::endl;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
4. 简答题

双栈排序

【问题描述】

Tom 最近在研究一个有趣的排序问题。如图所示,通过 2 个栈 S1 和 S2,Tom 希望借助以下 4 种操作实现将输入序列升序排序。

操作 d

如果栈 S2 不为空,将 S2 栈顶元素弹出至输出序列

如果一个 1~n 的排列 P 可以通过一系列操作使得输出序列为 1,2,…,(n-1),n,Tom就称 P 是一个“可双栈排序排列”。例如(1,3,2,4)就是一个“可双栈排序序列”,而(2,3,4,1)不是。下图描述了一个将(1,3,2,4)排序的操作序列:<a,c,c,b,a,d,d,b>

当然,这样的操作序列有可能有几个,对于上例(1,3,2,4),<a,c,c,b,a,d,d,b>是另外一个可行的操作序列。Tom 希望知道其中字典序最小的操作序列是什么。

【输入】

输入文件 twostack.in 的第一行是一个整数 n。

第二行有 n 个用空格隔开的正整数,构成一个 1~n 的排列。

【输出】

输出文件 twostack.out 共一行,如果输入的排列不是“可双栈排序排列”,输出数字 0;

否则输出字典序最小的操作序列,每两个操作之间用空格隔开,行尾没有空格。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【限制】

30%的数据满足: n<=10

50%的数据满足: n<=50

100%的数据满足: n<=1000

查看答案与解析
答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=1010;</p><p style="text-align: left;">int n,m=1,size,tot1,tot2,p1[Max],p2[Max];</p><p style="text-align: left;">int first[Max],f[Max],num[Max],vis[Max];</p><p style="text-align: left;">struct shu{int to,next,len;}edge[Max*Max];</p><p> </p><p style="text-align: left;">inline int get_int()</p><p style="text-align: left;">{</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;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(c=getchar();(!isdigit(c))&amp;&amp;(c!='-');c=getchar());</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c=='-') f=-1,c=getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(;isdigit(c);c=getchar()) x=(x&lt;&lt;3)+(x&lt;&lt;1)+c-'0';</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x*f;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void build(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[++size].next=first[x],first[x]=size,edge[size].to=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>edge[++size].next=first[y],first[y]=size,edge[size].to=x;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void pre()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>f[n]=num[n];</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=n-1;i&gt;=1;i--) f[i]=min(f[i+1],num[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int j=i+1;j&lt;=n;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    if(f[j]&lt;num[i]&amp;&amp;num[i]&lt;num[j]) build(i,j);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline bool dfs(int p,int color)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[p]=color;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[p];u;u=edge[u].next)</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 to=edge[u].to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(!vis[to]) dfs(to,3-color);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  else if(color==vis[to]) return 0;</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 1;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">int main()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>n=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) num[i]=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>pre();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++) if(!vis[i]&amp;&amp;!dfs(i,1)) {puts("0");return 0;}</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;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>  if(vis[i]==1)p1[++tot1]=num[i],printf("a ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>  else p2[++tot2]=num[i],printf("c ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>  while(m==p1[tot1]||m==p2[tot2])</p><p style="text-align: left;"><span style="white-space:pre"> </span>  {</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>if(m==p1[tot1]) tot1--,printf("b ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>else tot2--,printf("d ");</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>m++;</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>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。