nbhkdz.com冰点文库

SDOI2015


2012 年全国青少年信息学奥林匹克竞赛 山东省省队选拔赛第二试(第一天)

SDTSC 2012
DAY 1
竞赛时间:2012 年 5 月 19 日上午 8:00-13:00
题目名称 目录 可执行文件名 输入文件名 输出文件名 每个测试点时限 空间限制 测试点数目 每个测试点分值 是否有部分分 题目类型 吊灯 divide

divide divide divide.in divide.out
2秒

体育课 line line line line.in line.out
9秒

基站建设 wifi wifi wifi wifi.in wifi.out
13 秒

128MB 10 10 无 传统

128MB 10 10 无 传统

512MB 10 10 无 传统

提交源程序须加后缀 对于 Pascal 语言 divide.pas 对于 C 语言 divide.c 对于 C++ 语言 divide.cpp

line.pas line.c line.cpp

wifi.pas wifi.c wifi.cpp

注意:最终测试时,所有编译命令均不打开任何优化开关

吊灯(divide)
题目描述
Alice 家里有一盏很大的吊灯。所谓吊灯,就是由很多个灯泡组成。只有一个灯泡是挂在天花板上 的,剩下的灯泡都是挂在其他的灯泡上的。也就是说,整个吊灯实际上类似于一棵树。其中编号为 1 的灯泡是挂在天花板上的,剩下的灯泡都是挂在编号小于自己的灯泡上的。 现在,Alice 想要办一场派对,她想改造一下这盏吊灯,将灯泡换成不同的颜色。她希望相同颜色 的灯泡都是相连的,并且每一种颜色的灯泡个数都是相同的。 Alice 希望你能告诉她,总共有哪些方案呢? Alice 是一个贪心的孩子,如果她发现方案不够多,或者太多了,就会很不高兴,于是她会尝试调 整。对于编号为 x(x≠1)的灯泡,如果原来是挂在编号为 f[x]的灯泡上,那么 Alice 会把第 x 个灯泡挂 到第 ( f[x] + 19940105 ) mod (x-1) + 1 个灯泡上。 由于九在古汉语中表示极大的数,于是,Alice 决定只调整 9 次。对于原始状态和每一次调整过的 状态,Alice 希望你依次告诉她每种状态下有哪些方案。 输入说明 第一行一个整数 n,表示灯泡的数量。 接下来一行,有 n-1 个整数 Ui,第 i 个数字表示第 i+1 个灯泡挂在了 Ui 个的下面。保证编号为 1 的灯泡是挂在天花板上的。数字之间用逗号‘, ’隔开且最后一个数字后面没有逗号。 输出说明 对于 10 种状态下的方案,需要按照顺序依次输出。 对于每一种状态,需要先输出单独的一行,表示状态编号,如样例所示。 之后若干行,每行 1 个整数,表示划分方案中每种颜色的灯泡个数。 按升序输出。 样例输入 6 1,2,3,4,5 样例输出 Case #1: 1 2 3 6 Case #2: 1 2 6 Case #3: 1 3 6 Case #4: 1

3 6 Case #5: 1 3 6 Case #6: 1 2 6 Case #7: 1 2 3 6 Case #8: 1 6 Case #9: 1 2 6 Case #10: 1 3 6 数据规模 对于 20%的数据,n<=3*103。 对于 40%的数据,n<=5*104。 对于 50%的数据,n<=1*105。 对于 60%的数据,n<=3*105。 对于 70%的数据,n<=7*105。 对于 100%的数据,n<=1.2*106。

体育课(line)
问题描述:
又是一节体育课的时间了,有 n 个同学排成了一排。他们都很讨厌排在第一个位置的同学,于是 后面的同学中比第一个高的都会产生一个高兴值,这个高兴值等于他的身高减去第一个同学的身高。 当然比第一个同学矮的同学产生兴奋值为 0。 现在体育老师来了,他拥有神奇的魔法,现在他能做如下的三件事: 1:询问某段区间高兴值最大的那个是多少。 2:把某两个同学交换一下位置。 3:选取一段区间的人,把第一个人身高加上 t,第二个加上 2t,第三个加上 3t 以此类推。 但是体育老师不会数数,于是他找到你了,对于每一个询问,他要你帮他求出那个值。 输入说明: 第一行两个整数 n,m 表示有 n 个人,有 m 个操作。 第二行 n 个整数,顺序输入每个人的身高。 (身高<=10^8) 接下来 m 行,每行第一个数位一个 type 表示是做哪一件事情。 如果 type=1,那么接下来有两个整数 l,r,表示询问这段区间的最大的高兴值 如果 Type=2,接下来两个整数 a,b,表示交换这两个位置的人 如果 type=3,接下来三个整数 l,r,t,表示把 l 个人的升高增加 t,l+1 个人增加 2t…第 r 个人增加 (r-l+1)t, (0<=t<= 10000) 输出说明: 对于每个询问按照顺序输出每个操作 1 的答案。 样例输入: 68 109 827 100 530 10 826 3161 226 124 123 226 126 125 样例输出: 431 0 817 431 719 数据范围: 有 20%的数据:n,m<=5000 另有 10%的数据:没有第三种操作. 另有 20%的数据: 没有第二种操作 对于 100 的数据:n,m<=100000

基站建设(wifi)
题目描述:
Up 主家终于买电脑了,但是接下来有各种问题要处理。首要解决的问题就是网络问题。他要从移 动公司开始,通过一些基站来传递网络到他家。 为了简化问题,我们假设移动公司,所有的基站,up 主家位于同一条直线上,他们都位于这一条 直线上的某一点 x,这些点不会重合。每个基站发射和接收的范围都是一个切于地面的圆,发射的半径 r1 是固定的,接收半径 r2 是可调的的。如下图:

一个点 i 如果能从另一个点 j 接收到信号(当且仅当 x[j] < x[i]),必须满足 i 的接收范围与 j 的发射 范围相切,并且需要付 sqrt(r2[i])的额外费用。同时启动每一个点 i 都需要费用 v[i]. 当然一个点如果能够发射的 up 主家只需要这个点的发射范围与 up 主家所在的竖线相切或相交即 可,如下图:

当然费用越少就越好咯,于是 up 主想要请你帮他的忙。

输入说明:
第一行两个整数 n,m.表示基站个数(包括移动公司),up 主家的坐标。(保证大等于所以基站的坐标) 记下来 n 行,每行三个整数 x[i],r1[i],v[i],表示每个基站的坐标,发射范围以及费用。 X[i]是按照坐标从小到大输入的,移动公司位于最小的那个坐标。 R 为 1..n 的排列。

输出说明:
一个实数,保留小数点后三位。

样例输入:

10 33 5 4 660 10 2 2040 11 6 3207 14 5 2006 18 3 6130 19 9 3363 22 1 1265 25 8 2836 27 10 7961 29 7 9075

样例输出:
3501.000

数据范围:
对于 20%的数据 n<=2000 对于 60%的数据 n<=100000 对于 100%的数据 n<=5*1000000,x[i],m <= 10^12,v[i] <= 10000


《游戏发展国》攻略(2015年1月5日晚上23点更新)

《游戏发展国》攻略(2015年1月5日晚上23点更新)_互联网_IT/计算机_专业资料...文档贡献者 fdasdoiw 贡献于2015-03-23 1/2 相关文档推荐 游戏发展国完整全...

初二期末模拟

2015国考行测模拟试题及历年真题 2015国考申论押密试卷及答案 2015国考面试通关...文档贡献者 kljasdoi 贡献于2013-02-02 1/2 专题推荐 人教版七年级语文上册...