noip2011提高组day2

《noip2011提高组day2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国信息学奥林匹克联赛（NOIP2011）复赛提高组day2全国信息学奥林匹克联赛（NOIP2011）复赛提高组day2（请选手务必仔细阅读本页内容）一．题目概况中文题目名称计算系数聪明的质监员观光公交英文题目与子目录名factorqcbus可执行文件名factorqcbus输入文件名factor.inqc.inbus.in输出文件名factor.outqc.outbus.out每个测试点时限1秒1秒1秒测试点数目102020每个测试点分值1055附加样例文件有有有结果比较方式全文比较（过滤行末空格及文末回车）题目类型传统传统传统二．提交源程序

2、文件名对于C++语言factor.cppqc.cppbus.cpp对于C语言factor.cqc.cbus.c对于pascal语言factor.pasqc.Pasbus.pas三．编译命令（不包含任何优化开关）对于C++语言g++-ofactorg++-oqcqc.cppg++-obusbus.cppfactor.cpp-lm–lm-lm对于C语言gcc-ofactorfactor.cgcc-oqcqc.c–lmgcc-obusbus.c-lm-lm对于pascal语言fpcfactor.pasfpcqc.pasfpcbus.pas四．运行内存

3、限制内存上限128M128M128M注意事项：1、文件名（程序名和输入输出文件名）必须使用英文小写。2、C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。3、全国统一评测时采用的机器配置为：CPUP43.0GHz，内存1G，上述时限以此配置为准。4、特别提醒：评测在NOILinux下进行。第1页共4页全国信息学奥林匹克联赛（NOIP2011）复赛提高组day21．计算系数(factor.cpp/c/pas)【问题描述】knm给定一个多项式(ax+by)，请求出多项式展开后xy项的系数。【输入】输入文件名为fa

4、ctor.in。共一行，包含5个整数，分别为a，b，k，n，m，每两个整数之间用一个空格隔开。【输出】输出文件名为factor.out。输出共1行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007取模后的结果。【输入输出样例】factor.infactor.out113123【数据范围】对于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是一名质量监

5、督员，最近负责检验一批矿产的质量。这批矿产共有n个矿石，从1到n逐一编号，每个矿石都有自己的重量wi以及价值vi。检验矿产的流程是：1、给定m个区间[Li，Ri]；2、选出一个参数W；3、对于一个区间[Li，Ri]，计算矿石在这个区间上的检验值Yi：Yi=∑1*∑vj，j∈[Li,Ri]且wj≥W，j是矿石编号jjm这批矿产的检验结果Y为各个区间的检验值之和。即：Y=∑Yii=1若这批矿产的检验结果与所给标准值S相差太多，就需要再去检验另一批矿产。小T不想费时间去检验另一批矿产，所以他想通过调整参数W的值，让检验结果尽可能的靠近标准值S，即使得

6、S-Y的绝对值最小。请你帮忙求出这个最小值。【输入】输入文件qc.in。第2页共4页全国信息学奥林匹克联赛（NOIP2011）复赛提高组day2第一行包含三个整数n，m，S，分别表示矿石的个数、区间的个数和标准值。接下来的n行，每行2个整数，中间用空格隔开，第i+1行表示i号矿石的重量wi和价值vi。接下来的m行，表示区间，每行2个整数，中间用空格隔开，第i+n+1行表示区间[Li,Ri]的两个端点Li和Ri。注意：不同区间可能重合或相互重叠。【输出】输出文件名为qc.out。输出只有一行，包含一个整数，表示所求的最小值。【输入输出样例】qc.

7、inqc.out5315101525354555152433【输入输出样例说明】当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；612对于100%的数据，有1≤n，m≤200,000，0

8、市，拥有n个美丽的景点。由于慕名而来的游客越来越多，Y市特意安排了一辆观光公交车，为游客提供更便捷的交通服务。观光公交车在第0分钟出现在1号景点，随后