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

全国信息学奥林匹克联赛(NOIP2013)复赛 提高组 day2 VIP

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

一、简答题

1. 简答题

积木大赛

【题目描述】

春春幼儿园举办了一年一度的“积木大赛”。今年比赛的内容是搭建一座宽度为n的大厦,大厦可以看成由n块宽度为1的积木组成,第i块积木的最终高度需要是hi。

在搭建开始之前,没有任何积木(可以看成n块高度为 0 的积木)。接下来每次操作,小朋友们可以选择一段连续区间[L,R],然后将第L块到第R块之间(含第 L 块和第 R 块)所有积木的高度分别增加1。

小M是个聪明的小朋友,她很快想出了建造大厦的最佳策略,使得建造所需的操作次数最少。但她不是一个勤于动手的孩子,所以想请你帮忙实现这个策略,并求出最少的操作次数。

【输入】

输入文件为 block.in

输入包含两行,第一行包含一个整数n,表示大厦的宽度。

第二行包含n个整数,第i个整数为hi。

【输出】

输出文件为 block.out

仅一行,即建造所需的最少操作数。

【输入输出样例】

【样例解释】

其中一种可行的最佳方案,依次选择[1,5] [1,3] [2,3] [3,3] [5,5]

【数据范围】

对于 30%的数据,有1 ≤ n ≤ 10;

对于 70%的数据,有1 ≤ n ≤ 1000;

对于 100%的数据,有1 ≤ n ≤ 100000,0 ≤ hi ≤ 10000。

查看答案与解析
答案:<p>#include &lt;iostream&gt;</p><p>#include &lt;algorithm&gt;</p><p><br/></p><p>using namespace std;</p><p><br/></p><p>const int N = 100010;</p><p><br/></p><p>int n;</p><p>int h[N];</p><p><br/></p><p>int main()</p><p>{</p><p>    scanf("%d", &amp;n);</p><p>    for (int i = 1; i &lt;= n; i ++ ) scanf("%d", &amp;h[i]);</p><p><br/></p><p>    int res = 0;</p><p>    for (int i = 1; i &lt;= n; i ++ ){</p><p>     if(h[i]-h[i-1]&gt;0)res+=h[i]-h[i-1];</p><p>}</p><p>    cout &lt;&lt; res &lt;&lt; endl;</p><p><br/></p><p>    return 0;</p><p>}</p>
这道题暂未补解析。
2. 简答题

花匠

【问题描述】

花匠栋栋种了一排花,每株花都有自己的高度。花儿越长越大,也越来越挤。栋栋决定把这排中的一部分花移走,将剩下的留在原地,使得剩下的花能有空间长大,同时,栋栋希望剩下的花排列得比较别致。

具体而言,栋栋的花的高度可以看成一列整数h1, h2, … , hn。设当一部分花被移走后,剩下的花的高度依次为g1, g2, … , gm,则栋栋希望下面两个条件中至少有一个满足:

条件 A:对于所有的i,g2i > g2i−1,且g2i > g2i+1;

条件 B:对于所有的i,g2i < g2i−1,且g2i < g2i+1。

注意上面两个条件在m = 1时同时满足,当m > 1时最多有一个能满足。

请问,栋栋最多能将多少株花留在原地。

【输入】

输入文件为 flower.in。

输入的第一行包含一个整数n,表示开始时花的株数。

第二行包含n个整数,依次为h1, h2,… , hn,表示每株花的高度。

【输出】

输出文件为 flower.out。

输出一行,包含一个整数m,表示最多能留在原地的花的株数。

【输入输出样例】

【输入输出样例说明】

有多种方法可以正好保留 3 株花,例如,留下第 1、4、5 株,高度分别为 5、1、2,满足条件 B。

【数据范围】

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

对于 30%的数据,n ≤ 25;

对于 70%的数据,n ≤ 1000,0 ≤ hi ≤ 1000;

对于 100%的数据,1 ≤ n ≤ 100,000,0 ≤ hi ≤ 1,000,000,所有的hi随机生成,所有随机数服从某区间内的均匀分布。

查看答案与解析
答案:<p>#include&lt;bits/stdc++.h&gt;</p><p>using namespace std;</p><p>const int N = 1e5 + 5;</p><p>int n,a[N],ans;</p><p>int f[N][2];</p><p><br/></p><p>int main()</p><p>{</p><p><span style="white-space:pre"> </span>scanf("%d",&amp;n);</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>for(int i = 1;i &lt;= n;i ++)</p><p><span style="white-space:pre"> </span>scanf("%d",&amp;a[i]);</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>f[1][0] = f[1][1] = 1;</p><p><span style="white-space:pre"> </span>for(int i = 2;i &lt;= n;i ++)</p><p><span style="white-space:pre"> </span>{</p><p><span style="white-space:pre"> </span>if(a[i] &gt; a[i - 1])</p><p><span style="white-space:pre"> </span>f[i][1] = max(f[i - 1][1],f[i - 1][0] + 1);</p><p><span style="white-space:pre"> </span>else <span style="white-space:pre"> </span>f[i][1] = f[i - 1][1];</p><p><span style="white-space:pre"> </span>if(a[i] &lt; a[i - 1])</p><p><span style="white-space:pre"> </span>f[i][0] = max(f[i - 1][0],f[i - 1][1] + 1);</p><p><span style="white-space:pre"> </span>else <span style="white-space:pre"> </span>f[i][0] = f[i - 1][0];</p><p><span style="white-space:pre"> </span></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",max(f[n][0],f[n][1]));</p><p><span style="white-space:pre"> </span></p><p><span style="white-space:pre"> </span>return 0;</p><p>}</p>
这道题暂未补解析。
3. 简答题

华容道

【问题描述】

小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。

小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的:

1. 在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的;

2. 有些棋子是固定的,有些棋子则是可以移动的;

3. 任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。

给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的时候,空白的格子在第 EXi行第 EYi列,指定的可移动棋子的初始位置为第 SXi行第 SYi列,目标位置为第 TXi行第 TYi列。

假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。

【输入】

输入文件为 puzzle.in。

第一行有 3 个整数,每两个整数之间用一个空格隔开,依次表示 n、m 和 q;

接下来的 n 行描述一个 n*m 的棋盘,每行有 m 个整数,每两个整数之间用一个空格隔开,每个整数描述棋盘上一个格子的状态,0 表示该格子上的棋子是固定的,1 表示该格子上的棋子可以移动或者该格子是空白的。

接下来的 q 行,每行包含 6 个整数依次是 EXi、EYi、SXi、SYi、TXi、TYi,每两个整数之间用一个空格隔开,表示每次游戏空白格子的位置,指定棋子的初始位置和目标位置。

【输出】

输出文件名为 puzzle.out。

输出有 q 行,每行包含 1 个整数,表示每次游戏所需要的最少时间,如果某次游戏无法完成目标则输出−1。

【输入输出样例】

【输入输出样例说明】

棋盘上划叉的格子是固定的,红色格子是目标位置,圆圈表示棋子,其中绿色圆圈表示目标棋子。

1. 第一次游戏,空白格子的初始位置是 (3, 2)(图中空白所示),游戏的目标是将初始位置在(1, 2)上的棋子(图中绿色圆圈所代表的棋子)移动到目标位置(2, 2)(图中红色的格子)上。

2. 第二次游戏,空白格子的初始位置是(1, 2)(图中空白所示),游戏的目标是将初始位置在(2, 2)上的棋子(图中绿色圆圈所示)移动到目标位置 (3, 2)上。

要将指定块移入目标位置,必须先将空白块移入目标位置,空白块要移动到目标位置,

必然是从位置(2,2)上与当前图中目标位置上的棋子交换位置,之后能与空白块交换位置

的只有当前图中目标位置上的那个棋子,因此目标棋子永远无法走到它的目标位置,游戏无

法完成。

【数据范围】

对于 30%的数据,1 ≤ n, m ≤ 10,q = 1;

对于 60%的数据,1 ≤ n, m ≤ 30,q ≤ 10;

对于 100%的数据,1 ≤ n, m ≤ 30,q ≤ 500。

查看答案与解析
答案:<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=35;</p><p style="text-align: left;">const int fx[5]={0,1,0,-1};</p><p style="text-align: left;">const int fy[5]={1,0,-1,0};</p><p style="text-align: left;">int n,m,q,head,tail,tot,ans;</p><p style="text-align: left;">int num[Max][Max],dis[Max][Max][5],move[Max][Max][5][5];</p><p style="text-align: left;">bool vis[Max][Max],v[Max][Max][5];</p><p style="text-align: left;">int p[1000000][5],d[1000000][5];</p><p> </p><p style="text-align: left;">inline void bfs(int x,int y,int k1,int k2)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int sx=x+fx[k1],sy=y+fy[k1],tx=x+fx[k2],ty=y+fy[k2];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if((!num[sx][sy])||(!num[tx][ty])) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[1][1]=sx,p[1][2]=sy;</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>vis[x][y]=vis[sx][sy]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head&lt;tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  int xx=p[head][1],yy=p[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int i=0;i&lt;=3;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>  <span style="white-space:pre"> </span>int x1=xx+fx[i],y1=yy+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>if(!vis[x1][y1] &amp;&amp; num[x1][y1])</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>   vis[x1][y1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>   p[++tail][1]=x1,p[tail][2]=y1,p[tail][0]=p[head][0]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>   if(x1==tx&amp;&amp;y1==ty) {move[x][y][k1][k2]=p[tail][0];return;}</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <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;">}</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>memset(move,43,sizeof(move));</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=1;j&lt;=m;j++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    if(num[i][j])</p><p style="text-align: left;"><span style="white-space:pre"> </span>      for(int k=0;k&lt;=3;k++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>        for(int l=0;l&lt;=3;l++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>          if(l==k) move[i][j][k][l]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>          else bfs(i,j,k,l);</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">inline void calc(int x,int y,int sx,int sy)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=1,tot=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[1][1]=x,p[1][2]=y,p[1][0]=0;</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>vis[x][y]=vis[sx][sy]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head&lt;tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  int xx=p[head][1],yy=p[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int i=0;i&lt;=3;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>  <span style="white-space:pre"> </span>int x1=xx+fx[i],y1=yy+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>if(num[x1][y1]&amp;&amp;!vis[x1][y1])</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>  vis[x1][y1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>  p[++tail][0]=p[head][0]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>  p[tail][1]=x1,p[tail][2]=y1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>else if(x1==sx&amp;&amp;y1==sy) d[++tot][1]=x1,d[tot][2]=y1,d[tot][0]=p[head][0],d[tot][3]=(i+2)%4;</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;">}</p><p> </p><p style="text-align: left;">inline void SPFA()</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(v,0,sizeof(v));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=tot;i++) dis[d[i][1]][d[i][2]][d[i][3]]=d[i][0],v[d[i][1]][d[i][2]][d[i][3]]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>head=0,tail=tot;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(head&lt;tail)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  head++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  int x=d[head][1],y=d[head][2];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  v[x][y][d[head][3]]=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int i=0;i&lt;=3;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>  <span style="white-space:pre"> </span>int x1=x+fx[i],y1=y+fy[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>if(dis[x1][y1][(i+2)%4] &gt; dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  dis[x1][y1][(i+2)%4]=dis[x][y][d[head][3]]+move[x][y][d[head][3]][i]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(!v[x1][y1][(i+2)%4])</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>tail++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>d[tail][1]=x1,d[tail][2]=y1,d[tail][3]=(i+2)%4;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  <span style="white-space:pre"> </span>v[x1][y1][(i+2)%4]=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>} </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;">}</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>scanf("%d%d%d",&amp;n,&amp;m,&amp;q);</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=1;j&lt;=m;j++) scanf("%d",&amp;num[i][j]);</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>while(q--)</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 x,y,sx,sy,tx,ty;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  scanf("%d%d%d%d%d%d",&amp;x,&amp;y,&amp;sx,&amp;sy,&amp;tx,&amp;ty);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(sx==tx&amp;&amp;sy==ty) {cout&lt;&lt;"0\n";continue;}</p><p style="text-align: left;"><span style="white-space:pre"> </span>  memset(dis,43,sizeof(dis));</p><p style="text-align: left;"><span style="white-space:pre"> </span>  calc(x,y,sx,sy);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  SPFA();</p><p style="text-align: left;"><span style="white-space:pre"> </span>  ans=dis[0][0][0];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  for(int i=0;i&lt;=3;i++) ans=min(ans,dis[tx][ty][i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(ans==dis[0][0][0]) cout&lt;&lt;"-1\n";</p><p style="text-align: left;"><span style="white-space:pre"> </span>  else cout&lt;&lt;ans&lt;&lt;"\n";</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>
这道题暂未补解析。