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

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

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

一、简答题

1. 简答题

计算系数

【问题描述】

给定一个多项式请求出多项式展开后项的系数。

【输入】

输入文件名为 factor.in。

共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。

【输出】

输出文件名为 factor.out。

输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取模后的结果。

【输入输出样例】

【数据范围】

对于 30%的数据,有 0≤k≤10;

对于 50%的数据,有 a = 1,b = 1;

对于 100%的数据,有 0≤k≤1,000,0≤n, m≤k,且 n + m = k,0≤a,b≤1,000,000。

查看答案与解析
答案:<p style="text-align: left;">#include&lt;iostream&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">long long mod=10007;</p><p style="text-align: left;">long long Mood(long long a,long long b){</p><p style="text-align: left;"><span style="white-space:pre"> </span>long long sum=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>a%=mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(b){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(b&amp;1)</p><p style="text-align: left;"><span style="white-space:pre"> </span>    sum=sum*a%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>a=a*a%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>b=b&gt;&gt;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>return sum;</p><p style="text-align: left;">}</p><p style="text-align: left;">int a,b,k,n,m;</p><p style="text-align: left;">long long ans=0;</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>cin&gt;&gt;a&gt;&gt;b&gt;&gt;k&gt;&gt;n&gt;&gt;m;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=Mood(a,n)*Mood(b,m)%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=1,j=k;i&lt;=n;i++,j--){//逆元 </p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=ans*j%mod;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans=ans*Mood(i,mod-2)%mod;</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&lt;&lt;endl;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
2. 简答题

聪明的质监员

【问题描述】

小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1到 n 逐一编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是:

1、给定 m 个区间[Li,Ri];

2、选出一个参数 W;

3、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi :

这批矿产的检验结果 Y 为各个区间的检验值之和。即:

若这批矿产的检验结果与所给标准值 S 相差太多,就需要再去检验另一批矿产。小 T不想费时间去检验另一批矿产,所以他想通过调整参数 W 的值,让检验结果尽可能的靠近标准值 S,即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。

【输入】

输入文件 qc.in。

第一行包含三个整数 n,m,S,分别表示矿石的个数、区间的个数和标准值。

接下来的 n 行,每行 2 个整数,中间用空格隔开,第 i+1 行表示 i 号矿石的重量 wi 和价值 vi 。

接下来的 m 行,表示区间,每行 2 个整数,中间用空格隔开,第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意:不同区间可能重合或相互重叠。

【输出】

输出文件名为 qc.out。

输出只有一行,包含一个整数,表示所求的最小值。

【输入输出样例】

【输入输出样例说明】

当 W 选 4 的时候,三个区间上检验值分别为 20、5、0,这批矿产的检验结果为 25,此时与标准值 S 相差最小为 10。

【数据范围】

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

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

对于 50%的数据,有 1≤n,m≤5,000;

对于 70%的数据,有 1≤n,m≤10,000;

对于 100%的数据,有 1≤n,m≤200,000,0 < wi, vi≤10^6,0 < S≤10^12,1≤Li≤Ri≤n。

查看答案与解析
答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">#define int long long</p><p style="text-align: left;">using namespace std;</p><p> </p><p style="text-align: left;">const int Max=200005;</p><p style="text-align: left;">int n,m,s,l,r,mid,maxx,ans=1e18,v;</p><p style="text-align: left;">int w[Max],c[Max],sum1[Max],sum2[Max],L[Max],R[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 int check(int W)</p><p style="text-align: left;">{</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ans=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>  sum1[i]=sum1[i-1],sum2[i]=sum2[i-1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(w[i]&gt;=W) sum1[i]+=c[i],sum2[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>for(int i=1;i&lt;=m;i++) ans+=(sum2[R[i]]-sum2[L[i]-1])*(sum1[R[i]]-sum1[L[i]-1]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>return ans;</p><p style="text-align: left;">}</p><p> </p><p style="text-align: left;">signed 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(),s=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=1;i&lt;=n;i++) w[i]=get_int(),c[i]=get_int(),maxx=max(maxx,w[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span> for(int i=1;i&lt;=m;i++) L[i]=get_int(),R[i]=get_int();</p><p style="text-align: left;"><span style="white-space:pre"> </span> l=1,r=maxx;</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,v=check(mid);</p><p style="text-align: left;"><span style="white-space:pre"> </span>   if(v&lt;=s) ans=min(s-v,ans),r=mid;</p><p style="text-align: left;"><span style="white-space:pre"> </span>   else 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> l=1,r=maxx;</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+1)&gt;&gt;1,v=check(mid);</p><p style="text-align: left;"><span style="white-space:pre"> </span>  if(v&gt;=s) ans=min(ans,v-s),l=mid;</p><p style="text-align: left;"><span style="white-space:pre"> </span>  else r=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> 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>
这道题暂未补解析。
3. 简答题

观光公交

【问题描述】

风景迷人的小城 Y 市,拥有 n 个美丽的景点。由于慕名而来的游客越来越多,Y 市特意安排了一辆观光公交车,为游客提供更便捷的交通服务。观光公交车在第 0 分钟出现在 1号景点,随后依次前往 2、3、4……n 号景点。从第 i 号景点开到第 i+1 号景点需要 Di 分钟。任意时刻,公交车只能往前开,或在景点处等待。

设共有 m 个游客,每位游客需要乘车 1 次从一个景点到达另一个景点,第 i 位游客在Ti 分钟来到景点 Ai,希望乘车前往景点 Bi(Ai<Bi)。为了使所有乘客都能顺利到达目的地,公交车在每站都必须等待需要从该景点出发的所有乘客都上车后才能出发开往下一景点。假设乘客上下车不需要时间。 

一个乘客的旅行时间,等于他到达目的地的时刻减去他来到出发地的时刻。因为只有一辆观光车,有时候还要停下来等其他乘客,乘客们纷纷抱怨旅行时间太长了。于是聪明的司机 ZZ 给公交车安装了 k 个氮气加速器,每使用一个加速器,可以使其中一个 Di 减 1。对于同一个 Di 可以重复使用加速器,但是必须保证使用后 Di 大于等于 0。

那么 ZZ 该如何安排使用加速器,才能使所有乘客的旅行时间总和最小?

【输入】

输入文件名为 bus.in。

第 1 行是 3 个整数 n, m, k,每两个整数之间用一个空格隔开。分别表示景点数、乘客数和氮气加速器个数。

第 2 行是 n-1 个整数,每两个整数之间用一个空格隔开,第 i 个数表示从第 i 个景点开往第 i+1 个景点所需要的时间,即 Di。

第 3 行至 m+2 行每行 3 个整数 Ti, Ai, Bi,每两个整数之间用一个空格隔开。第 i+2 行表示第 i 位乘客来到出发景点的时刻,出发的景点编号和到达的景点编号。

【输出】

输出文件名为 bus.out。共一行,包含一个整数,表示最小的总旅行时间。

【输入输出样例】 

【输入输出样例说明】

对 D2 使用 2 个加速器,从 2 号景点到 3 号景点时间变为 2 分钟。

公交车在第 1 分钟从 1 号景点出发,第 2 分钟到达 2 号景点,第 5 分钟从 2 号景点出发,

第 7 分钟到达 3 号景点。

第 1 个旅客旅行时间 7-0 = 7 分钟。

第 2 个旅客旅行时间 2-1 = 1 分钟。

第 3 个旅客旅行时间 7-5 = 2 分钟。

总时间 7+1+2 = 10 分钟。

【数据范围】

对于 10%的数据,k=0;

对于 20%的数据,k=1;

对于 40%的数据,2 ≤ n ≤ 50,1 ≤ m ≤ 1,000,0 ≤ k ≤ 20,0 ≤ Di ≤ 10,0 ≤ Ti ≤ 500;

对于 60%的数据,1 ≤ n ≤ 100,1 ≤ m ≤ 1,000,0 ≤ k ≤ 100,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 10,000;

对于 100%的数据,1 ≤ n ≤ 1,000,1 ≤ m ≤ 10,000,0 ≤ k ≤ 100,000,0 ≤ Di ≤ 100,0 ≤ Ti ≤ 100,000。

查看答案与解析
答案:<p style="text-align: left;">#include &lt;iostream&gt;</p><p style="text-align: left;">#include &lt;cstdio&gt;</p><p style="text-align: left;">#include &lt;cstring&gt;</p><p style="text-align: left;">using namespace std;</p><p style="text-align: left;">const int maxn=1010;</p><p style="text-align: left;">const int maxm=10010;</p><p style="text-align: left;">int d[maxn];//en[maxn];</p><p style="text-align: left;">int dis[maxn];</p><p style="text-align: left;">int a[maxm],b[maxm],t[maxm];</p><p style="text-align: left;">int tim[maxn];</p><p style="text-align: left;">int c[maxn];</p><p style="text-align: left;">int g[maxn];</p><p style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("bus.in","r",stdin);</p><p style="text-align: left;"><span style="white-space:pre"> </span>freopen("bus.out","w",stdout);</p><p style="text-align: left;"><span style="white-space:pre"> </span>int n,m,k;</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d %d %d",&amp;n,&amp;m,&amp;k);</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>scanf("%d",&amp;d[i]);</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>scanf("%d %d %d",&amp;t[i],&amp;a[i],&amp;b[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>//en[b[i]]++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>tim[a[i]]=max(tim[a[i]],t[i]);</p><p style="text-align: left;"><span style="white-space:pre"> </span>c[b[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>for(int i=1;i&lt;n;i++)</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[i+1]=max(tim[i],dis[i])+d[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>int ans=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>ans+=dis[b[i]]-t[i];</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>c[i]=c[i-1]+c[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(k--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[n]=n;</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[n-1]=n;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i=n-2;i;i--){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[i+1]&gt;tim[i+1])</p><p style="text-align: left;"><span style="white-space:pre"> </span>g[i]=g[i+1];</p><p style="text-align: left;"><span style="white-space:pre"> </span>else g[i]=i+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>int maxx=0,u;</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>if(c[g[i]]-c[i]&gt;maxx&amp;&amp;d[i]&gt;0){</p><p style="text-align: left;"><span style="white-space:pre"> </span>maxx=c[g[i]]-c[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>u=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(!maxx)</p><p style="text-align: left;"><span style="white-space:pre"> </span>break;</p><p style="text-align: left;"><span style="white-space:pre"> </span>d[u]--;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans-=maxx;</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[1]=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>dis[i+1]=max(tim[i],dis[i])+d[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>printf("%d\n",ans);</p><p style="text-align: left;">return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。