English
资源说明：NOIP2011）复赛 提高组 day2
1 页 共 4 页 全国信息学奥林匹克联赛（NOIP2011）复赛 提高组 day2 （请选手务必仔细阅读本页内容） 一．题目概况 中文题目名称 计算系数 聪明的质监员 观光公交 英文题目与子目录名 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 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 下进行。
NOIP2011）复赛 提高组 day2
2 页 共 4 页 【问题描述】 1．计算系数 (factor.cpp/c/pas) 给定一个多项式 (ax + by)k ，请求出多项式展开后 x n y m 项的系数。 【输入】 输入文件名为 factor.in。 共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。 【输出】 输出文件名为 factor.out。 输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对 10007 取 模后的结果。 【输入输出样例】 factor.in factor.out 1 1 3 1 2 3 【数据范围】 对于 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 ： Yi = ∑1* ∑v j ， j ∈[Li , Ri ] 且 w j ≥ W ，j 是矿石编号 j j m 这批矿产的检验结果 Y 为各个区间的检验值之和。即：Y = ∑Yi i =1 若这批矿产的检验结果与所给标准值 S 相差太多，就需要再去检验另一批矿产。小 T 不想费时间去检验另一批矿产，所以他想通过调整参数 W 的值，让检验结果尽可能的靠近 标准值 S，即使得 S-Y 的绝对值最小。请你帮忙求出这个最小值。 【输入】 输入文件 qc.in。
NOIP2011）复赛 提高组 day2
3 页 共 4 页 第一行包含三个整数 n，m，S，分别表示矿石的个数、区间的个数和标准值。 接下来的 n 行，每行 2 个整数，中间用空格隔开，第 i+1 行表示 i 号矿石的重量 wi 和价 值 vi 。 接下来的 m 行，表示区间，每行 2 个整数，中间用空格隔开，第 i+n+1 行表示区间[Li, Ri]的两个端点 Li 和 Ri。注意：不同区间可能重合或相互重叠。 【输出】 输出文件名为 qc.out。 输出只有一行，包含一个整数，表示所求的最小值。 【输入输出样例】 qc.in qc.out 5 3 15 1 5 2 5 3 5 4 5 5 5 1 5 2 4 3 3 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
本源码包内暂不包含可直接显示的源代码文件，请下载源码包。
