CSP-J难度模拟赛(IOI赛制)
题目 | ||||
---|---|---|---|---|
Time limit | 1000ms | 1000ms | 2000ms | 1000ms |
Memory limit | 256MiB | 1024MiB | 512MiB | 512MiB |
输入输出 | 传统题 | 传统题 | 传统题 | 传统题 |
A. 酸碱度中和
题目描述
小明有瓶生理盐水,由于浓度不太一样, 以及混进来了一些奇怪的东西,第瓶生理盐水的酸碱度是。
小明觉得个瓶子太多了,于是他决定把这瓶盐水重新灌装进个瓶子中。
把若干瓶盐水混到一起的前提条件是:每一瓶盐水的酸碱度是一样的。
这显然太困难了,所以小明准备去哆啦A梦的杂货铺购买道具“酸碱度修改器”。
“酸碱度修改器”有一个属性值,当你使用它在某一瓶盐水上的时候,可以把这瓶盐水的酸碱度增加/减少最多。比如你有一个属性为的“酸碱度修改器”,那么你可以把原来酸碱度为的生理盐水的酸碱度修改为中的任何一个值。
“酸碱度修改器”可以重复使用。但是,对于每一瓶生理盐水来说只能使用一次。
属性值越大的“酸碱度修改器”越贵,因此,小明决定购买尽量小的,请帮助小明算一算,他最少要买属性为多少的“酸碱度修改器”。
输入格式
第一行输入。
接下来一行输入个正整数表示。
输出格式
一个数字表示答案。
样例输入 #1
4 2
1 3 5 7
样例输出 #1
1
样例解释 #1
把和修改成,把和修改成,只需要属性为的修改器即可。
样例输入 #2
4 1
1 3 5 7
样例输出 #2
3
数据范围
对于30%的数据:。
对于50%的数据:。
对于另外20%的数据:。
对于100%的数据:。
B. 聪明的小明
题目描述
小明开了个酒厂,他的酒厂里面会出产种酒。
有一天,市长要来他的酒厂视察,他可太高兴了。
为了应对这次视察,他决定在一个陈列长廊上摆放瓶酒。市长走过这个长廊的时候就会看到每一瓶酒。
通过市长秘书处的打听,小明得到了一个重要消息:市长将会在考察完毕后,从长廊里面连续的取走瓶酒作为纪念。
为了让市长带走的酒里,一定包含酒厂中产出的每一种酒,小明决定仔细研究这瓶酒具体来摆放哪些酒。
请帮助小明算一算,他有多少种摆放酒的方案吧!
输入格式
第一行三个正整数,如题所述。
输出格式
输出答案 。
样例 #1
样例输入 #1
4 2 3
样例输出 #1
10
提示
【样例 1 解释】
一共种方案:
[1121],[1122],[1211],[1212],[1221],[2212],[2211],[2122],[2121],[2112]
样例输入 #2
10 4 6
样例输出 #2
81552
样例输入 #3
100000 7 10
样例输出 #3
77680521
数据范围
对于25%的数据:。
对于另5%的数据:。
对于另20%的数据:。
对于另20%的数据:。
对于100%的数据:。
C. 线段树
题目描述
小明有一棵线段树。
啥是线段树呢?你可以想象成,一开始,你有一个区间,然后,你可以取中点,把它划分成两个区间。(之前那个区间也还在的哦)
然后,你可以继续划分下去,直到把每一个区间都划分成长度为为止,下图就是一棵线段树,维护了区间的信息。
假设线段树上,每个节点都存储了它表示的区间内所有元素的信息(比如区间的和)。
那么,当我想知道一个区间的信息的时候,我一定可以在线段树上找到一些区间,这些区间互相没有交集,且并起来刚好是区间。
比如,我在上图的线段树中,要查询的信息,那么我找到两个区间,就可以表示区间的信息了。(把替代成显然也是合法的策略,但是这样选择的区间更多了,不够优秀)。
我们称,对于一次查询,我们需要用到的区间个数为,比如上图中。
我们的问题是:给定线段树根节点所表示的区间范围是,以及有次查询,第次查询是,假设你可以在最初时候自由的选择区间分割的位置,最小是多少?
输入格式
第一行输入。
接下来行,每行两个数字。
输出格式
一个数字表示答案。
样例输入 #1
4 2
1 3
4 4
样例输出 #1
2
样例解释 #1
对于我们来说,我们可以在第一层分割时候,把区间分割成,这样两个查询都只需要一次操作。
样例输入 #2
5 3
1 3
3 5
2 4
样例输出 #2
5
样例解释 #2
我们在第一层把区间分割成,然后把分割成,分割成,分割成。
这样,对于的查询,我们需要用到两个区间。
对于的查询,我们需要用到一个区间。
对于的查询,我们需要用到两个区间。
样例输入 #3
10 8
1 5
2 6
2 4
2 8
2 9
3 5
3 6
1 10
样例输出 #3
11
数据范围
对于30%的数据:保证。
对于50%的数据:保证。
对于70%的数据:保证。
对于100%的数据:保证$1\leq n \leq 500,1\leq q\leq 10^5,1\leq l_i\leq r_i\leq n$。
D. [J-PSC 3202] 路公
题目描述
小苞准备开着车沿着公路自驾。
公路上一共有 个站点,编号为从 到 。其中站点 与站点 的距离为 公里。
公路上每个站点都可以加油,编号为 的站点一升油的价格为 元,且每个站点只出售整数升的油。
小苞想从站点 开车到站点 ,一开始小苞在站点 且车的油箱是空的。已知车的油箱容量是,且每升油可以让车前进 公里。问小苞从站点 开到站点 ,至少要花多少钱加油?
输入格式
输入的第一行包含两个正整数 和 ,如题所述。
输入的第二行包含 个正整数 ,分别表示站点间的距离。
输入的第三行包含 个正整数 ,分别表示在不同站点加油的价格。
输出格式
输出一行,仅包含一个正整数,表示从站点 开到站点 ,小苞至少要花多少钱加油。
样例 #1
样例输入 #1
5 4
2 2 2 2 2
9 8 9 6 5
样例输出 #1
72
提示
【样例 1 解释】
最优方案下:小苞在站点 买了 升油,在站点 购买了 升油,在站点 购买了 升油,在站点购买了升油。
样例输入 #2
9 8
8 2 7 4 1 6 6 2 4
3 8 2 9 2 8 10 4 4
样例输出 #2
171
样例输入 #3
7 3
2 1 2 3 3 1 3
10 5 3 4 2 6 7
样例输出 #3
73
【数据范围】
对于所有测试数据保证:,,,,。
测试点 | 特殊性质 | ||
---|---|---|---|
无 | |||
A | |||
B | |||
无 |
- 特殊性质 A:保证。
- 特殊性质 B:保证纯随机。