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

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

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

一、简答题

1. 简答题

跳石头

【问题描述】

一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有 N 块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。

为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走 M 块岩石(不能移走起点和终点的岩石)。

【输入格式】

输入文件名为 stone.in。

输入文件第一行包含三个整数 L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。

接下来 N 行,每行一个整数,第 i 行的整数 Di(0 < Di < L)表示第 i 块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。

【输出格式】

输出文件名为 stone.out。

输出文件只包含一个整数,即最短跳跃距离的最大值。

【输入输出样例 1】

【输入输出样例 1 说明】

将与起点距离为 2 和 14 的两个岩石移走后,最短的跳跃距离为 4(从与起点距离17 的岩石跳到距离 21 的岩石,或者从距离 21 的岩石跳到终点)。

【数据规模与约定】

对于 20%的数据,0 ≤ M ≤ N ≤ 10。

对于 50%的数据,0 ≤ M ≤ N ≤ 100。

对于 100%的数据,0 ≤ M ≤ N ≤ 50,000,1 ≤ L ≤ 1,000,000,000。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;      //本题数据量大,采用二分法来减少复杂度,避免超时。先把所有的石头点存入数组a</p><p style="text-align: left;">int l,n,m;     //包括起始点0和终点l。这题使用二分答案的思想,顾名思义就是采用二分法查找答案(最短跳跃距离最大值)</p><p style="text-align: left;">int a[100000];  //我们知道,最短跳跃距离必在0-l之间,0和l一开始作为上下界,对于a[mid]用judge进行判断</p><p style="text-align: left;">bool judge(int k){    //如果要达到mid对应最短跳跃距离需要移开石头数count&gt;原有的m,说明实际的答案会比mid小</p><p style="text-align: left;">    int count=0,now=0;    //就把有边界左移,反之,说明可以达到这个最短跳跃距离,是暂时的最优答案,先保存</p><p style="text-align: left;">    for(int i=1;i&lt;n+2;i++){    //然后把左边界右移,试试有没有更优的解,直到上下边界互相跨越</p><p style="text-align: left;">        if(a[i]-a[now]&lt;k){</p><p style="text-align: left;">            count++;</p><p style="text-align: left;">        }else{</p><p style="text-align: left;">            now=i;        //now是现在脚底下的石头,如果不移石头直接过去要更新</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    if(count&gt;m){</p><p style="text-align: left;">        return false;</p><p style="text-align: left;">    }else{</p><p style="text-align: left;">        return true;</p><p style="text-align: left;">    }</p><p style="text-align: left;">}</p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    cin&gt;&gt;l&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;">    a[0]=0;</p><p style="text-align: left;">    a[n+1]=l;</p><p style="text-align: left;">    for(int i=1;i&lt;n+1;i++){</p><p style="text-align: left;">        cin&gt;&gt;a[i];</p><p style="text-align: left;">    }</p><p style="text-align: left;">    int left=0,right=l,mid,ans;</p><p style="text-align: left;">    while(left&lt;=right){       //二分法</p><p style="text-align: left;">        mid=(left+right)/2;</p><p style="text-align: left;">        if(judge(mid)){</p><p style="text-align: left;">            left=mid+1;</p><p style="text-align: left;">            ans=mid;</p><p style="text-align: left;">        }else{</p><p style="text-align: left;">            right=mid-1;</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    cout&lt;&lt;ans;</p><p style="text-align: left;">    //system("pause");</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

子串

【问题描述】

有两个仅包含小写英文字母的字符串 A 和 B。现在要从字符串 A 中取出 k 个互不重叠的非空子串,然后把这 k 个子串按照其在字符串 A 中出现的顺序依次连接起来得到一个新的字符串,请问有多少种方案可以使得这个新串与字符串 B 相等?注意:子串取出的位置不同也认为是不同的方案。

【输入格式】

输入文件名为 substring.in。

第一行是三个正整数 n,m,k,分别表示字符串 A 的长度,字符串 B 的长度,以及问题描述中所提到的 k,每两个整数之间用一个空格隔开。

第二行包含一个长度为 n 的字符串,表示字符串 A。

第三行包含一个长度为 m 的字符串,表示字符串 B。

【输出格式】

输出文件名为 substring.out。

输出共一行,包含一个整数,表示所求方案数。由于答案可能很大,所以这里要求输出答案对 1,000,000,007 取模的结果。

【输入输出样例 1】

【输入输出样例 2】

【输入输出样例 3】

【输入输出样例说明】

所有合法方案如下:(加下划线的部分表示取出的子串)

样例 1:aab aab / aab aab

样例 2:a ab aab / a aba ab / a a ba ab / aab a abaa b aab / aa baa b / aab aa b

样例 3:a a b aab / a a baa b / a ab a a b / a aba a ba a b a a b / a a ba a b / aab a a b

【数据规模与约定】

对于第 1 组数据:1≤n≤500,1≤m≤50,k=1;

对于第 2 组至第 3 组数据:1≤n≤500,1≤m≤50,k=2;

对于第 4 组至第 5 组数据:1≤n≤500,1≤m≤50,k=m;

对于第 1 组至第 7 组数据:1≤n≤500,1≤m≤50,1≤k≤m;

对于第 1 组至第 9 组数据:1≤n≤1000,1≤m≤100,1≤k≤m;

对于所有 10 组数据:1≤n≤1000,1≤m≤200,1≤k≤m。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;iostream&gt;</p><p style="text-align: left;">#include&lt;cstring&gt;</p><p style="text-align: left;">#define N 1003</p><p style="text-align: left;">#define M 203</p><p style="text-align: left;">#define mod 1000000007</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">int dp[3][N][M]={0};</p><p style="text-align: left;">char A[N],B[M];</p><p style="text-align: left;">int n=0,m=0,K=0;</p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    ios::sync_with_stdio(false);</p><p style="text-align: left;">    cin&gt;&gt;n&gt;&gt;m&gt;&gt;K;</p><p style="text-align: left;">    cin&gt;&gt;(A+1);cin&gt;&gt;(B+1);</p><p style="text-align: left;">    for(int i=0;i&lt;=n;i++) dp[0][i][0]=1;</p><p style="text-align: left;">    for(int k=1;k&lt;=K;k++){</p><p style="text-align: left;">        memset(dp[k&amp;1],0,sizeof(dp[k&amp;1]));</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;">                if(j&gt;i) break;</p><p style="text-align: left;">                dp[k&amp;1][i][j]+=dp[k&amp;1][i-1][j];</p><p style="text-align: left;">                dp[k&amp;1][i][j]%=mod;</p><p style="text-align: left;">                if(A[i]==B[j]){</p><p style="text-align: left;">                    dp[k&amp;1][i][j]+=(dp[(k-1)&amp;1][i-1][j-1]+dp[k&amp;1][i-1][j-1])%mod;</p><p style="text-align: left;">                    dp[k&amp;1][i][j]%=mod;</p><p style="text-align: left;">                    if(i&gt;1) dp[k&amp;1][i][j]-=dp[k&amp;1][i-2][j-1];</p><p style="text-align: left;">                    dp[k&amp;1][i][j]%=mod;</p><p style="text-align: left;">                    dp[k&amp;1][i][j]+=mod;</p><p style="text-align: left;">                    dp[k&amp;1][i][j]%=mod;</p><p style="text-align: left;">                }</p><p style="text-align: left;">                dp[k&amp;1][i][j]%=mod;</p><p style="text-align: left;">            }</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    cout&lt;&lt;dp[K&amp;1][n][m]&lt;&lt;endl;</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

运输计划

【问题描述】

公元 2044 年,人类进入了宇宙纪元。

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui号星球沿最快的宇航路径飞行到 vi号星球去。显然,飞船驶过一条航道是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后,这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少?

【输入格式】

输入文件名为 transport.in。

第一行包括两个正整数 n、m,表示 L 国中星球的数量及小 P 公司预接的运输计划的数量,星球从 1 到 n 编号。

接下来 n-1 行描述航道的建设情况,其中第 i 行包含三个整数 ai, bi和 ti,表示第i 条双向航道修建在 ai与 bi两个星球之间,任意飞船驶过它所花费的时间为 ti。

接下来 m 行描述运输计划的情况,其中第 j 行包含两个正整数 uj和 vj,表示第 j 个运输计划是从 uj号星球飞往 vj号星球。

【输出格式】

输出文件名为 transport.out。

共 1 行,包含 1 个整数,表示小 P 的物流公司完成阶段性工作所需要的最短时间。

【输入输出样例 1】

【输入输出样例 1 说明】

将第 1 条航道改造成虫洞:则三个计划耗时分别为:11、12、11,故需要花费的时间为 12。

将第 2 条航道改造成虫洞:则三个计划耗时分别为:7、15、11,故需要花费的时间为 15。

将第 3 条航道改造成虫洞:则三个计划耗时分别为:4、8、11,故需要花费的时间为 11。

将第 4 条航道改造成虫洞:则三个计划耗时分别为:11、15、5,故需要花费的时间为 15。

将第 5 条航道改造成虫洞:则三个计划耗时分别为:11、10、6,故需要花费的时间为 11。

故将第 3 条或第 5 条航道改造成虫洞均可使得完成阶段性工作的耗时最短,需要花费的时间为 11。

【数据规模与约定】

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

查看答案与解析
答案:<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=300005;</p><p style="text-align: left;">int n,m,s,ans,tot,l,r,mid;</p><p style="text-align: left;">int first[Max],son[Max],pos[Max],top[Max],depth[Max],father[Max],size[Max],dis[Max],num[Max],len[Max],val[Max],v[Max];</p><p style="text-align: left;">struct shu{int to,next,len;}edge[Max&lt;&lt;1];</p><p style="text-align: left;">struct bian{int x,y,len;}d[Max];</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 style="text-align: left;">inline void build(int x,int y,int z){edge[++s].next=first[x],first[x]=s,edge[s].to=y,edge[s].len=z;}</p><p style="text-align: left;">inline void dfs1(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>size[point]=1,father[point]=fa,depth[point]=depth[fa]+1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int u=first[point];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(to==fa) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  val[to]=edge[u].len,dis[to]=dis[point]+edge[u].len;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  dfs1(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  size[point]+=size[to];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(size[to] &gt; size[son[point]]) son[point]=to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void dfs2(int point,int fa)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(son[point])</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  pos[son[point]]=++tot,len[tot]=val[son[point]],top[son[point]]=top[point];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  dfs2(son[point],point);</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(int u=first[point];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(top[to]) continue;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  pos[to]=++tot,top[to]=to;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  dfs2(to,point);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int LCA(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(top[x]!=top[y])</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(depth[top[x]] &lt; depth[top[y]]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  x=father[top[x]];</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(depth[x] &gt; depth[y]) swap(x,y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline bool comp(const bian &amp;a,const bian &amp;b){return a.len&gt;b.len;}</p><p style="text-align: left;">inline void solve(int x,int y)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(top[x]!=top[y])</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(depth[top[x]] &lt; depth[top[y]]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  num[pos[top[x]]+1]++,num[pos[x]+1]--;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  x=father[top[x]];</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(x==y) return;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(depth[x] &gt; depth[y]) x^=y,y^=x,x^=y;</p><p style="text-align: left;"><span style="white-space:pre"> </span>num[pos[x]+1]++,num[pos[y]+1]--;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline int mx(int x,int y){return x &lt; y ? y : x;}</p><p style="text-align: left;">inline int check(int mid)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int k=0,x=0,sum=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(d[k+1].len&gt;mid) k++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(v[k]) return v[k];</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(num,0,sizeof(num));</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=k;i++) solve(d[i].x,d[i].y);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n;i++){sum+=num[i];if(sum == k) x=mx(x,len[i]);}</p><p style="text-align: left;"><span style="white-space:pre"> </span>v[k]=x;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return x;</p><p style="text-align: left;">}</p><p style="text-align: left;">inline void print(int x){if(x&gt;9) print(x/10);putchar('0'+x%10);}</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(),m=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=n-1;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>  int x=get_int(),y=get_int(),z=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>  build(x,y,z),build(y,x,z);</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>top[1]=tot=pos[1]=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dfs1(1,0),dfs2(1,0);</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1;i&lt;=m;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>  d[i].x=get_int(),d[i].y=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span>  d[i].len=dis[d[i].x]+dis[d[i].y]-2*dis[LCA(d[i].x,d[i].y)];</p><p style="text-align: left;"><span style="white-space:pre"> </span>}</p><p style="text-align: left;"><span style="white-space:pre"> </span>sort(d+1,d+m+1,comp);</p><p style="text-align: left;"><span style="white-space:pre"> </span>l=0,r=d[1].len;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(l&lt;r)</p><p style="text-align: left;"><span style="white-space:pre"> </span>{</p><p style="text-align: left;"><span style="white-space:pre"> </span>  mid=(l+r)&gt;&gt;1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  (d[1].len - check(mid) &lt;= mid) ? r=mid : l=mid+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>print(r);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。