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

全国信息学奥林匹克联赛(NOIP2019)复赛 普及组 VIP

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

一、简答题

1. 简答题

数字游戏

【问题描述】

小K同学向小P同学发送了一个长度为8的 01字符串来玩数字游戏,小P  同学想 要知道字符串中究竟有多少个1。

注意:01字符串为每一个字符是0或者1的字符串,如“101”(不含双引号)为一 个长度为3的01字符串。

【输入格式】

输入文件名为number in。

输入文件只有一行, 一个长度为8的01字符串s。


【输出格式】

输出文件名为number.out。

输出文件只有一行,包含一个整数,即01字符串中字符1 的个数。

【输入输出样例1】

【输入输出样例1说明】

该01字符串中有2个字符1。


【输入输出样例2】

【输入输出样例2说明】

该01字符串中有8个字符1。

【数据规模与约定】

对于20%的数据,保证输入的字符全部为0。

对于100%的数据,输入只可能包含字符0和字符1,字符串长度固定为8。

查看答案与解析
答案:<p>#include&lt;bits/stdc++.h&gt;</p><p>using namespace std;</p><p>string str;</p><p>int cnt = 0;</p><p>int main(){</p><p><span style="white-space:pre"> </span>cin &gt;&gt; str;</p><p><span style="white-space:pre"> </span>for(int i = 0;str[i];i++) if(str[i] == '1') cnt++;</p><p><span style="white-space:pre"> </span>cout &lt;&lt; cnt &lt;&lt; endl;</p><p><span style="white-space:pre"> </span>return 0;</p><p>}</p>
这道题暂未补解析。
2. 简答题

公交换乘

【问题描述】

著名旅游城市B市为了鼓励大家采用公共交通方式出行,推出了一种地铁换乘公交 车的优惠方案:

1.在搭乘一次地铁后可以获得一张优惠票,有效期为45分钟,在有效期内可以 消耗这张优惠票,免费搭乘一次票价不超过地铁票价的公交车。在有效期内指 开始乘公交车的时间与开始乘地铁的时间之差小于等于45分钟,即:tbus-tsubway≤45

2.  搭乘地铁获得的优惠票可以累积,即可以连续搭乘若干次地铁后再连续使用优 惠票搭乘公交车。

3.  搭乘公交车时,如果可以使用优惠票一定会使用优惠票;如果有多张优惠票满 足条件,则优先消耗获得最早的优惠票。

现在你得到了小轩最近的公共交通出行记录,你能帮他算算他的花费吗?

【输入格式】

输入文件名为transfer . in。

输入文件的第一行包含一个正整数n,代表乘车记录的数量。

接下来的n行,每行包含3个整数,相邻两数之间以一个空格分隔。第i行的 第1个整数代表第i条记录乘坐的交通工具,0代表地铁,1代表公交车;第2个 整数代表第i条记录乘车的票价pricei;第三个整数代表第i条记录开始乘车的时 间ti (距0时刻的分钟数)。

我们保证出行记录是按照开始乘车的时间顺序给出的,且不会有两次乘车记录出现 在同一分钟。

【输出格式】

输出文件名为transfer . out。

输出文件有一行,包含一个正整数,代表小轩出行的总花费

【 输入输出样例 1】

【输入输出样例1说明】

第一条记录,在第3分钟花费10元乘坐地铁。

第二条记录,在第46分钟乘坐公交车,可以使用第一条记录中乘坐地铁获得的优 惠票,因此没有花费。

第三条记录,在第50分种花费12元乘坐地铁。

第四条记录,在第96分钟乘坐公交车,由于距离第三条记录中乘坐地铁已超过45 分钟,所以优惠票已失效,花费3元乘坐公交车。

第五条记录,在第110分钟花费5元乘坐地铁。

第六条记录,在第135分钟乘坐公交车,由于此时手中只有第五条记录中乘坐地铁 获得的优惠票有效,而本次公交车的票价为6元,高于第五条记录中地铁的票价5元, 所以不能使用优惠票,花费6元乘坐公交车。

总共花费36元。

【输入输出样例2】

【输入输出样例2说明】

第一条记录,在第1分钟花费5元乘坐地铁。

第二条记录,在第16分钟花费20元乘坐地铁。

第三条记录,在第23分钟花费7元乘坐地铁。

第四条记录,在第31分钟乘坐公交车,此时只有第二条记录中乘坐的地铁票价高 于本次公交车票价,所以使用第二条记录中乘坐地铁获得的优惠票。

第五条记录,在第38分钟乘坐公交车,此时第一条和第三条记录中乘坐地铁获得  的优惠票都可以使用,使用获得最早的优惠票,即第一条记录中乘坐地铁获得的优惠票。

第六条记录,在第68分钟乘坐公交车,使用第三条记录中乘坐地铁获得的优惠票。 总共花费32元。

【数据规模与约定】

查看答案与解析
答案:<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;">int n,opt,m,t,num=0,ans=0;</p><p style="text-align: left;">struct data {</p><p style="text-align: left;"><span style="white-space:pre"> </span>int m,t;</p><p style="text-align: left;"><span style="white-space:pre"> </span>bool ok;</p><p style="text-align: left;">} p[100001];</p><p style="text-align: left;">int main() {</p><p style="text-align: left;"><span style="white-space:pre"> </span>scanf("%d",&amp;n);</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%d%d",&amp;opt,&amp;m,&amp;t);</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(opt==0) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>num++;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[num].m=m;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[num].t=t;</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[num].ok=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans+=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>if(opt==1) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>bool ok=0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int j=1; j&lt;=num; j++) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(t-p[j].t&lt;=45&amp;&amp;p[j].ok==0&amp;&amp;m&lt;=p[j].m) {</p><p style="text-align: left;"><span style="white-space:pre"> </span>p[j].ok=1;</p><p style="text-align: left;"><span style="white-space:pre"> </span>ok=1;</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>}</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(ok==0)</p><p style="text-align: left;"><span style="white-space:pre"> </span>ans+=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>printf("%d\n",ans);</p><p><br style="text-align: left;"/></p><p style="text-align: left;"><span style="white-space:pre"> </span>return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。
3. 简答题

纪念品

【问题描述】

小伟突然获得一种超能力,他知道未来T天N种纪念品每天的价格。某个纪念品  的价格是指购买一个该纪念品所需的金币数量,以及卖出一个该纪念品换回的金币数量。

每天,小伟可以进行以下两种交易无限次:

1. 任选一个纪念品,若手上有足够金币,以当日价格购买该纪念品;

2. 卖出持有的任意一个纪念品,以当日价格换回金币。

每天卖出纪念品换回的金币可以立即用于购买纪念品,当日购买的纪念品也可以当 日卖出换回金币。当然, 一直持有纪念品也是可以的。

T天之后,小伟的超能力消失。因此他一定会在第T天卖出所有纪念品换回金币。 小伟现在有M枚金币,他想要在超能力消失后拥有尽可能多的金币。

【输入格式】

输入文件名为souvenir . in。

第一行包含三个正整数T,N,M,相邻两数之间以一个空格分开,分别代表未来天数 T,纪念品数量N,小伟现在拥有的金币数量M。

接下来T行,每行包含N个正整数,相邻两数之间以一个空格分隔。第i行的N个正整数分别为Pi1,Pi2, …… ,Pin,其中Pi,j表示第i天第j种纪念品的价格。

【输出格式】

输出文件名为souvenir . out。

输出仅一行,包含一个正整数,表示小伟在超能力消失后最多能拥有的金币数量。

【输入输出样例1】

【 输入输出样例1说明】

最佳策略是:

第二天花光所有100枚金币买入5个纪念品1;

第三天卖出5个纪念品1,获得金币125枚;

第四天买入6个纪念品1,剩余5枚金币;

第六天必须卖出所有纪念品换回300枚金币,第四天剩余5枚金币,共305枚金币。

超能力消失后,小伟最多拥有305枚金币。

【输入输出样例2】

【输入输出样例2说明】

最佳策略是:

第一天花光所有金币买入10个纪念品1;

第二天卖出全部纪念品1得到150枚金币并买入8个纪念品2和1个纪念品3,剩 余1枚金币;

第三天必须卖出所有纪念品换回216枚金币,第二天剩余1枚金币,共217枚金币。 超能力消失后,小伟最多拥有217枚金币。

【数据规模与约定】

对于10%的数据,T=1。

对于30%的数据,T≤4,N≤4,M≤100,所有价格10≤Pij≤100。 

另有15%的数据,T≤100,N=1。

另有15%的数据,T=2,N≤100。

对于100%的数据,T≤100,N≤100,M≤,所有价格1≤Pij≤10⁴,数 据保证任意时刻,小明手上的金币数不可能超过10⁴。

查看答案与解析
答案:<p>#include&lt;bits/stdc++.h&gt;</p><p>using namespace std;</p><p>const int N = 1e2+10;</p><p>const int M = 1e4+10;</p><p>int t,n,m;</p><p>int val[N][N];</p><p>int f[N];<span style="white-space:pre"> </span>//第 x 天最多有多少钱</p><p>int tmp[M],mx;</p><p>void solve(){</p><p><span style="white-space:pre"> </span>f[1] = m;</p><p><span style="white-space:pre"> </span>for(int day = 2;day &lt;= t;day++){</p><p><span style="white-space:pre"> </span>for(int i = 1;i &lt; day;i++){</p><p><span style="white-space:pre"> </span>memset(tmp,0,sizeof tmp); mx = m;</p><p><span style="white-space:pre"> </span>for(int j = 1;j &lt;= n;j++){</p><p><span style="white-space:pre"> </span>for(int v = val[i][j]; v &lt;= f[i];v++){</p><p><span style="white-space:pre"> </span>tmp[v] = max(tmp[v-val[i][j]]+val[day][j],tmp[v]);</p><p><span style="white-space:pre"> </span>mx = max(mx,tmp[v]+f[i]-v);</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>f[day] = max(f[day],mx);</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>f[day] = max(f[day],f[day-1]);</p><p><span style="white-space:pre"> </span>}</p><p><span style="white-space:pre"> </span>//for(int i = 1;i &lt;= t;i++) printf("%d\n",f[i]);</p><p><span style="white-space:pre"> </span>printf("%d\n",f[t]);</p><p>}</p><p>int main(){</p><p><span style="white-space:pre"> </span>scanf("%d%d%d",&amp;t,&amp;n,&amp;m);</p><p><span style="white-space:pre"> </span>for(int i = 1;i &lt;= t;i++)</p><p><span style="white-space:pre"> </span>for(int j = 1;j &lt;= n;j++) scanf("%d",&amp;val[i][j]);</p><p><span style="white-space:pre"> </span>solve();</p><p><span style="white-space:pre"> </span>return 0;</p><p>}</p>
这道题暂未补解析。
4. 简答题

加工零件

【问题描述】

凯凯的工厂正在有条不紊地生产一种神奇的零件,神奇的零件的生产过程自然也很 神奇。工厂里有n位工人,工人们从1~n编号。某些工人之间存在双向的零件传送 带。保证每两名工人之间最多只存在一条传送带。

如果x号工人想生产一个被加工到第L(L>1)阶段的零件,则所有 与 x 号 工 人 有传送带直接相连的工人,都需要生产一个被加工到第L- 1阶段的零件(但x号工 人自己无需生产第L - 1阶段的零件)。

如果x号工人想生产一个被加工到第1阶段的零件,则所有与x号工人有传送带直接 相连的工人,都需要为x号工人提供一个原材料。

轩 轩 是 1 号工人。现在给出q张工单,第i张工单表示编号为ai的工人想生产 一个第Li阶段的零件。轩轩想知道对于每张工单,他是否需要给别人提供原材料。他 知道聪明的你一定可以帮他计算出来!

【输入格式】

输入文件名为work.in。

第一行两个正整数n,m和q,分别表示工人的数目、传送带的数目和工单的数目。

接下来m行,每行两个正整数u和v,表示编号为u和v的工人之间存在 一条零 件传输带。保证u≠v。

接下来q行,每行两个正整数a和L,表示编号为a的工人想生产 一个第L阶段 的零件。

【输出格式】

输出文件名为work . out。

共q行,每行一个字符串“Yes”或者“No”。如果按照第i张工单生产,需要编号为 1的轩轩提供原材料,则在第i行输出“Yes”;否则在第i行输出“No”。注意输出不含 引号。

【输入输出样例 1】

【输入输出样例1说明】

编号为1的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。

编号为2的工人想生产第1阶段的零件,需要编号为1和3的工人提供原材料。

编号为3的工人想生产第1阶段的零件,需要编号为2的工人提供原材料。

编号为1的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零 件,需要编号为1和3的工人提供原材料。

编号为2的工人想生产第2阶段的零件,需要编号为1和3的工人生产第1阶段 的零件,他/她们都需要编号为2的工人提供原材料。

编号为3的工人想生产第2阶段的零件,需要编号为2的工人生产第1阶段的零件,需要编号为1和3的工人提供原材料。

【输入输出样例2】

【输入输出样例2说明】

编号为1的工人想生产第1阶段的零件,需要编号为2和5的工人提供原材料。

编号为1的工人想生产第2阶段的零件,需要编号为2和5的工人生产第1阶段 的零件,需要编号为1,3,4 的工人提供原材料。

编号为1的工人想生产第3阶段的零件,需要编号为2和5的工人生产第2阶段的零件,需要编号为1,3,4的工人生产第1阶段的零件,需要编号为2,3,4,5 的工人提供 原材料。

编号为1的工人想生产第4阶段的零件,需要编号为2和5的工人生产第3阶段 的零件,需要编号为1,3,4的工人生产第2阶段的零件,需要编号为2,3,4,5 的工人生产 第1阶段的零件,需要全部工人提供原材料。

编号为1的工人想生产第5阶段的零件,需要编号为2和5的工人生产第4阶段 的零件,需要编号为1,3,4的工人生产第3阶段的零件,需要编号为2,3,4,5 的工人生产 第2阶段的零件,需要全部工人生产第1阶段的零件,需要全部工人提供原材料。

【数据规模与约定】

共20个测试点。

查看答案与解析
答案:<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;">const int N = 2e5+10;</p><p style="text-align: left;">const int M = 2*N;</p><p style="text-align: left;">typedef long long ll;</p><p style="text-align: left;">int n,m,q;</p><p style="text-align: left;">int head[N],edge[M],ver[M],nex[M] ,tot = 1;</p><p style="text-align: left;">void addEdge(int x,int y,int z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>ver[++tot] = y; edge[tot] = z;</p><p style="text-align: left;"><span style="white-space:pre"> </span>nex[tot] = head[x]; head[x] = tot;</p><p style="text-align: left;">}</p><p style="text-align: left;">int getInt(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int res = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>bool neg = false;</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 != '-' &amp;&amp; (c &lt; '0' || c &gt; '9')) c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(c == '-') neg = true, c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(c &gt;= '0' &amp;&amp; c &lt;= '9') res = res*10+c-'0',c = getchar();</p><p style="text-align: left;"><span style="white-space:pre"> </span>return neg?-res:res;</p><p style="text-align: left;">}</p><p style="text-align: left;">queue&lt;int&gt; que;</p><p style="text-align: left;">int dis[N],vis[N];</p><p style="text-align: left;">bool solve(int a,int l){</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[a] &lt;= l &amp;&amp; !((dis[a]&amp;1) ^ (l&amp;1))) return true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[a+n] &lt;= l &amp;&amp; !((dis[a+n]&amp;1) ^ (l&amp;1))) return true;</p><p style="text-align: left;"><span style="white-space:pre"> </span>return false;</p><p style="text-align: left;">}</p><p style="text-align: left;">void SPFA(int s){</p><p style="text-align: left;"><span style="white-space:pre"> </span>que.push(s);</p><p style="text-align: left;"><span style="white-space:pre"> </span>memset(dis,0x3f,sizeof dis);</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[s] = 0;</p><p style="text-align: left;"><span style="white-space:pre"> </span>while(que.size()){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int x = que.front(); que.pop();</p><p style="text-align: left;"><span style="white-space:pre"> </span>vis[x] = false;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = head[x];i ;i = nex[i]){</p><p style="text-align: left;"><span style="white-space:pre"> </span>int y = ver[i], z = edge[i];</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(dis[y] &gt; dis[x]+z){</p><p style="text-align: left;"><span style="white-space:pre"> </span>dis[y] = dis[x]+z;</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(!vis[y]) que.push(y),vis[y] = true;</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 style="text-align: left;">int main(){</p><p style="text-align: left;"><span style="white-space:pre"> </span>n = getInt(); m = getInt(); q = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1,x,y;i &lt;= m;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>x = getInt(); y = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>addEdge(x,y+n,1); addEdge(y+n,x,1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>addEdge(x+n,y,1); addEdge(y,x+n,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>SPFA(1);</p><p style="text-align: left;"><span style="white-space:pre"> </span>//for(int i = 1;i &lt;= n&lt;&lt;1;i++) cout &lt;&lt; dis[i] &lt;&lt; endl;</p><p style="text-align: left;"><span style="white-space:pre"> </span>for(int i = 1,a,l;i &lt;= q;i++){</p><p style="text-align: left;"><span style="white-space:pre"> </span>a = getInt(); l = getInt();</p><p style="text-align: left;"><span style="white-space:pre"> </span>if(solve(a,l)) puts("Yes");</p><p style="text-align: left;"><span style="white-space:pre"> </span>else puts("No");</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>
这道题暂未补解析。