信息学奥赛-入门级 题库
公路(road)
【题目描述】
小苞准备开着车沿着公路自驾。
公路上一共有n个站点,编号为从1到n。其中站点i与站点i+1的距离为vi公里。
公路上每个站点都可以加油,编号为i的站点一升油的价格为ai元,且每个站点只出售整数升的油。
小苞想从站点1开车到站点n,一开始小苞在站点1且车的油箱是空的。已知车的油箱足够大,可以装下任意多的油,且每升油可以让车前进d公里。问小苞从站点1开到站点n,至少要花多少钱加油?
【输入格式】
从文件road.in中读入数据。
输入的第一行包含两个正整数n和d,分别表示公路上站点的数量和车每升油可以前进的距离。
输入的第二行包含n−1个正整数v1,v2...vn−1,分别表示站点间的距离。
输入的第二行包含n个正整数a1,a2...an,分别表示在不同站点加油的价格。
【输出格式】
输出到文件road.out中。
输出一行,仅包含一个正整数,表示从站点1开到站点n,小苞至少要花多少钱加油。
【样例1输入】
【样例1输出】
【样例1解释】
最优方案下:小苞在站点1买了3升油,在站点2购买了5升油,在站点4购买了2升油。
【样例2】
见选手目录下的road/road2.in与road/road2.ans。
。

旅游巴士(bus)
【题目描述】
小Z打算在国庆假期期间搭乘旅游巴士去一处他向往已久的景点旅游。
旅游景点的地图共有n处地点,在这些地点之间连有m条道路。其中1号地点为景区入口,n号地点为景区出口。我们把一天当中景区开门营业的时间记为0时刻,则从0时刻起,每间隔k单位时间便有一辆旅游巴士到达景区入口,同时有一辆旅游巴士从景区出口驶离景区。
所有道路均只能单向通行。对于每条道路,游客步行通过的用时均为恰好1单位时间。
小Z希望乘坐旅游巴士到达景区入口,并沿着自己选择的任意路径走到景区出口,再乘坐旅游巴士离开,这意味着他到达和离开景区的时间都必须是k的非负整数倍。由于节假日客流众多,小Z在坐旅游巴士离开景区前只想一直沿着景区道路移动,而不.想在任何地点(包括景区入口和出口)或者道路上逗留。
出发前,小Z忽然得知:景区采取了限制客流的方法,对于每条道路均设置了一个“开放时间”ai,游客只有不早于ai时刻才能通过这条道路。
请你帮助小Z设计一个旅游方案,使得他乘坐旅游巴士离开景区的时间尽量地早。
【输入格式】
从文件bus.in中读入数据。
输入的第一行包含3个正整数n,m,k,表示旅游景点的地点数、道路数,以及旅游巴士的发车间隔。
输入的接下来m行,每行包含3个非负整数ui,vi,ai,表示第i条道路从地点ui出发,到达地点vi,道路的“开放时间”为ai。
【输出格式】
输出到文件bus.out中。
输出一行,仅包含一个整数,表示小Z最早乘坐旅游巴士离开景区的时刻。如果不存在符合要求的旅游方案,输出‐1。
【样例1输入】
【样例1输出】
【样例1解释】
图1:

样例1示例
小Z可以在3时刻到达景区入口,沿1→3→4→5的顺序走到景区出口,并在6时刻离开。
【样例2】
见选手目录下的bus/bus2.in与bus/bus2.ans。
【数据范围】
对于所有测试数据有:2≤n≤104,1≤m≤2×104,1≤k≤100,1≤ui,vi≤n,0≤ai≤106。

参考程序1:

参考程序2:

甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定 去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不 去。如果周末丙去了,则甲 (去了/没去) (1 分),乙 (去 了/没去) (1 分),丁 (去了/没去) (1 分),周末 (下雨/ 没下雨) (2 分)。
去了
没去
没去
没下雨
一个人站在坐标(0,0)处,面朝x轴正方向。
第一轮, 他向前走1单位距离,然后右转;第二轮,他向前走2单位距离,然后右转;第三轮,他向前走3单位距离,然后右转……他一直这么走下去。请问第2017轮后,他的坐标是:( , ) 。(请在答题纸上用逗号隔开两空答案)

1009, 1008
如右图所示,共有13个格子。对任何一个格子进行一次操作,会使得它自己以及与它上下左右相邻的格子中的数字改变(由1变0,或由0变1)。现在要使得所有的格子中的数字都变为0,至少需要 次操作。

3
约定二叉树的根节点高度为1。一棵结点数为2016的二叉树最少有 个叶子结点;一棵结点数为2016的二叉树最小的高度值是 。
1(2 分)
11(3 分)
把M个同样的球放到N个同样的袋子里,允许有的袋子空着不放,问共有多少种不同的放置方法?(用K表示)。
例如:M=7,N=3时,K=8;在这里认为(5,1,1)和(1,5,1)是同一种放置方法。
问:M=8,N=5时,K= 。
18
某系统自称使用了一种防窃听的方式验证用户密码。密码是n个数 s1, s2, … , sn ,均为0或1。该系统每次随机生成n个数a1, a2, … , an,均为0或1,请用户回答(s1a1+s2a2+… +snan)除以2的余数。如果多次的回答总是正确,即认为掌握密码。该系统认为, 即使 问答的过程被泄露, 也无助于破解密码—— 因为用户并没有直接发送密码。
然而, 事与愿违。例如,当n= 4 时, 有人窃听了以下 5 次问答:
就破解出了密码 s1= ,s2= ,s3= ,s4= 。
s1 = 0,s2 = 1,s3 = 1,s4 = 1
在NOI期间,主办单位为了欢迎来自全国各地的选手,举行了盛大的晚宴。在第十八桌,有5名大陆选手和5名港澳选手共同进膳。为了增进交流,他们决定相隔就坐,即每个大陆选手左右相邻的都是港澳选手、每个港澳选手左右相邻的都是大陆选手。那么,这一桌共有 种不同的就坐方案。注意:如果在两个方案中,每个选手左边相邻的选手均相同,则视为同一个方案。
2880
甲乙丙丁四人在考虑周末要不要外出郊游。
已知①如果周末下雨,并且乙不去,则甲一定不去;②如果乙去,则丁一定去;③如果丙去,则丁一定不去;④如果丁不去,而且甲不去,则丙一定不去。如果周末丙去了,则甲________(去了/没去)(1 分),乙________(去了/没去)(1 分),丁________(去了/没去)(1 分),周末________(下雨/没下雨)(2 分)。
答:去了 没去 没去 没下雨 (第4 空 2 分,其余 1 分)
从 1 到 2018 这 2018 个数中,共有__________个包含数字 8 的数。
包含数字 8 的数是指有某一位是“8”的数, 例如“2018”与“188”。
答:544
成绩
【问题描述】
牛牛最近学习了 C++入门课程,这门课程的总成绩计算方法是:
总成绩 = 作业成绩 × 20% + 小测成绩 × 30% + 期末考试成绩 × 50%
牛牛想知道,这门课程自己最终能得到多少分。
【输入格式】
输入文件名为 score.in。
输入文件只有 1 行,包含三个非负整数A、B、C,分别表示牛牛的作业成绩、小测
成绩和期末考试成绩。相邻两个数之间用一个空格隔开,三项成绩满分都是 100 分。
【输出格式】
输出文件名为 score.out。
输出文件只有 1 行,包含一个整数,即牛牛这门课程的总成绩,满分也是 100 分。
【输入输出样例 1】

【输入输出样例 1 说明】
牛牛的作业成绩是 100 分,小测成绩是 100 分,期末考试成绩是 80 分,总成
绩是 100 × 20% + 100 × 30% + 80 × 50% = 20 + 30 + 40 = 90。
【输入输出样例 2】

【输入输出样例 2 说明】
牛牛的作业成绩是 60 分,小测成绩是 90 分,期末考试成绩是 80 分,总成绩是
60 × 20% + 90 × 30% + 80 × 50% = 12 + 27 + 40 = 79。
【数据说明】
对于 30% 的数据,A = B = 0。
对于另外 30% 的数据,A = B = 100。
对于 100% 的数据, 0 ≤ A、B、C ≤ 100 且 A、B、C 都是 10 的整数倍。
#include<iostream>
using namespace std;
int main()
{
int A, B, C;
cin >> A >> B >> C;
cout << A * 0.2 + B * 0.3 + C * 0.5;
return 0;
}
回文日期 (date)
【问题描述】
在日常生活中,通过年、月、 日这三个要素可以表示出一个唯一确定的日期。
牛牛习惯用 8 位数字表示一个日期,其中,前 4 位代表年份,接下来 2 位代表月 份,最后 2 位代表日期。 显然:一个日期只有一种表示方法,而两个不同的日期的表 示方法不会相同。
牛牛认为,一个日期是回文的,当且仅当表示这个日期的 8 位数字是回文的。现 在,牛牛想知道:在他指定的两个日期之间 (包含这两个日期本身),有多少个真实存 在的日期是回文的。
【提示】
一个8位数字是回文的,当且仅当对于所有的 i
从左向右数的第 i 个 数字和第 9 - i 个数字 (即从右向左数的第i 个数字) 是相同的。
例如:
● 对于 2016 年 11 月 19 日,用8位数字 20161119 表示,它不是回文的。
● 对于 2010 年 1 月 2 日,用 8 位数字 20100102 表示,它是回文的。
● 对于 2010 年 10 月 2 日,用 8 位数字 20101002 表示,它不是回文的。
每一年中都有 12 个月份:
其中, 1 、 3 、 5 、 7 、 8 、 10 、 12 月每个月有 31 天; 4 、 6 、 9 、 11 月每个 月有30 天;而对于 2 月,闰年时有 29 天,平年时有 28 天。
一个年份是闰年当且仅当它满足下列两种情况其中的一种:
1. 这个年份是 4 的整数倍,但不是 100 的整数倍;
2. 这个年份是 400 的整数倍。 例如:
● 以下几个年份都是闰年: 2000 、 2012 、 2016 。
● 以下几个年份是平年: 1900 、 2011 、 2014 。
【输入格式】
从文件date.in 中读入数据。
输入包括两行,每行包括一个 8 位数字。
第一行表示牛牛指定的起始日期date1 。
第二行表示牛牛指定的终止日期date2 。
保证 date1 和 date2 都是真实存在的日期,且年份部分一定为 4 位数字,且首位数 字不为 0 。
保证 date1 一定不晚于 date2 。
【输出格式】
输出到文件date.out 中。
输出一行,包含一个整数,表示在 date1 和 date2 之间,有多少个日期是回文的。
【样例1输入】
20110101
20111231
【样例1输出】
1
【样例2输入】
20000101
20101231
【样例2输出】
2
【样例说明】
对于样例1 ,符合条件的日期是 20111102 。
对于样例2 ,符合条件的日期是 20011002 和 20100102 。
【子任务】
对于 60% 的数据,满足 date1 = date2 。
#include<iostream>
#include<cstdio>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
using namespace std;
int i,j,n,m,a,b,c,sum,ans;
int s[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=12;i++)
{
for(j=1;j<=s[i];j++)
{
c=(j%10)*1000+(j/10)*100+(i%10)*10+(i/10);
sum=c*10000+i*100+j;
if (sum<n||sum>m)
continue;
ans++;
}
}
printf("%d",ans);
return 0;
}




