第十七届信息技术奥赛提高组复赛试题第二天

全国信息学奥林匹克联赛（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) 【问题描述】 给定一个多项式 kbyax )( + ，请求出多项式展开后 mn yx 项的系数。 【输入】 输入文件名为 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 ： ∑∑= j j j i vY *1 ， ],[ ii RLj∈ 且 Wwj ≥ ，j是矿石编号 这批矿产的检验结果 Y为各个区间的检验值之和。即： ∑ = = m i iYY 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