注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

fanhq666的博客

Fan-Fun

 
 
 

日志

 
 

NOIP2011Day2试题及算法  

2011-11-14 22:24:19|  分类: 程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一.题目概况 
中文题目名称 计算系数 聪明的质监员 观光公交 
英文题目与子目录名 factor qc bus 
可执行文件名 factor qc bus 
输入文件名 factor.in qc.in bus.in 
输出文件名 factor.out qc.out bus.out 
每个测试点时限 1 秒 1 秒 1 秒 
测试点数目 10 20 20 
每个测试点分值 10 5
附加样例文件   有   有 
结果比较方式   全文比较(过滤行末空格及文末回车) 
题目类型   传统   传统   传统 
 
二.提交源程序文件名 
对于 C++语言 factor.cpp qc.cpp bus.cpp 
对于 C 语言 factor.c qc.c bus.c 
对于 pascal语言 factor.pas qc. Pas bus. pas 
 
三.编译命令(不包含任何优化开关) 
对于 C++语言  g++ -o factor factor.cpp -lm g++ -o qc qc.cpp –lm g++ -o bus bus.cpp -lm 
对于 C 语言  gcc -o factor factor.c -lm gcc -o qc qc.c –lm gcc -o bus bus.c -lm 
对于 pascal语言  fpc factor.pas fpc qc.pas fpc bus.pas 
 
四.运行内存限制 
内存上限   128M 128M 128M 
 
 
注意事项: 
1、文件名(程序名和输入输出文件名)必须使用英文小写。 
2、C/C++中函数 main()的返回值类型必须是 int,程序正常结束时的返回值必须是 0。 
3、全国统一评测时采用的机器配置为:CPU P4 3.0GHz,内存 1G,上述时限以此配置为准。  
4、特别提醒:评测在 NOI Linux 下进行。 

1.计算系数 
(factor.cpp/c/pas) 
【问题描述】 
  给定一个多项式 k
by ax ) ( + ,请求出多项式展开后 m n
y x 项的系数。 
【输入】 
输入文件名为 factor.in。 
共一行,包含 5 个整数,分别为 a,b,k,n,m,每两个整数之间用一个空格隔开。 
【输出】 
输出文件名为 factor.out。 
输出共 1 行,包含一个整数,表示所求的系数,这个系数可能很大,输出对 10007 取
模后的结果。 
 
【输入输出样例】 
factor.in 
1 1 3 1 2 
factor.out 
 
【数据范围】 
对于 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。 
 
 
2.聪明的质监员 
(qc.cpp/c/pas) 
【问题描述】 
小 T 是一名质量监督员,最近负责检验一批矿产的质量。这批矿产共有 n 个矿石,从 1
到 n 逐一编号,每个矿石都有自己的重量 wi 以及价值 vi。检验矿产的流程是: 
1、给定 m个区间[Li,Ri]; 
2、选出一个参数 W; 
3、对于一个区间[Li,Ri],计算矿石在这个区间上的检验值 Yi  : 
这段区间上重量大于等于W的矿石个数乘以这些(重量大于等于W的)矿石的价值和。
这批矿产的检验结果 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。 
输出只有一行,包含一个整数,表示所求的最小值。 
 
【输入输出样例】 
qc.in 
5 3 15 
1 5 
2 5 
3 5 
4 5 
5 5 
1 5 
2 4 
3 3 
qc.out 
10 
 
【输入输出样例说明】 
当 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≤106
,0 < S≤1012
,1≤Li≤Ri≤n。  
 
 
3.观光公交 
(bus.cpp/c/pas) 
【问题描述】 
  风景迷人的小城 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。共一行,包含一个整数,表示最小的总旅行时间。 
 
【输入输出样例】  
bus.in 
3 3 2 
1 4 
0 1 3 
1 1 2 
5 2 3 
bus.out  
10 
【输入输出样例说明】 
对 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。 


说说算法吧:今天的题没有恶心题。
第一题:送分,就是要计算a^n*b^m*C(n+m,n)%10007。使用dp来计算组合数以避免除法(C(a,b)=C(a-1,b)+C(a-1,b-1))。
值得说说这题的对拍程序,有的同学(像我)毫不犹豫写了python,有的同学使用linux自带的高精度计算器dc,还有的同学使用linux自带的高精度计算脚本bc,真是各显神通。
第二题:二分查找。
二分W,计算检验值(每次计算需要进行前缀和的预处理以进行O(1)的区间和查询)。不用多说吧?
第三题:贪心
这题还是有点技术含量的,北京的同学这题做的不好,想出100%算法的同学很少,真的是不应该。
我们考察这样一个序列:F[i],表示到车第i站的时刻与最晚到这站的乘客到达时刻的差。如果F[i]>0,表示人等车,否则表示车等人。
原问题可以转换为最小化sum([F[i]*W[i] for i in range(0,N)]),其中W[i]表示第i站有多少人下车。
考虑减小D[i]减一的后果:F[i+1]--,并且如果原来F[i+1]>0,还会导致F[i+2]--,如果原来F[i+2]>0,还会继续导致F[i+3]--,依次类推。
于是问题转换为:给一个数列,每次可以使连续的一段除了最后一个数以外都是正数的数减少1,问最后这个数列的加权和最小是多少。由于D[i]>=0,所以每个数被减少是有次数限制的。
这个显然用贪心:每次选取权值和最大的一段进行减少,直到它因出现负数而分裂成两个区间或因D[i]=0而退化成另一个区间。用一个堆来维护当前能够减少的区间,每次挑最大的进行减少,直到使用完配额。使用rmq来计算一个区间从哪里分裂。
时间复杂度:O(nlogn+m)
实际上,可以暴力一点,直接O(n^2+m)的暴力优先队列+暴力rmq。
  评论这张
 
阅读(2480)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017