冲刺noip2010模拟试题与解析(一)

《冲刺noip2010模拟试题与解析(一)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、冲刺NOIP2010模拟试题与解析（一）题目（提高组时间：3个小时）难易指数：★★★题目名称淘汰赛制种树方程的解物流运输题目程序名elimination.pas/c/cpptrees.pas/c/cppequation.pas/c/cpptrans.pas/c/cpp输入文件名elimination.intreesmequation.intrans.in输出文件名elimination.outtrees.outequation.outtrans.out测试点时限1s1s1s1s测试点个数1010lO10测试点分值101010lo内存限制256MB256MB256MB256MB1、

2、淘汰赛制(elimination.pas/c/cpp)【问题描述】淘汰赛制是一种极其残酷的比赛制度。2n名选手分别标号1，2，3，…，2n-1，2n，他们将要参加n轮的激烈角逐。每一轮中，将所有参加该轮的选手按标号从小到大排序后，第1位与第2位比赛，第3位与第4位比赛，第5位与第6位比赛……只有每场比赛的胜者才有机会参加下一轮的比赛（不会有平局）。这样，每轮将淘汰一半的选手。n轮过后，只剩下一名选手，该选手即为最终的冠军。现在已知每位选手分别与其他选手比赛获胜的概率，请你预测一下谁夺冠的概率最大。【输入文件】输入文件elimination.in。第一行是一个整数n(l≤n≤l0)

3、，表示总轮数。接下来2n行，每行2n个整数，第i行第j个是pij(0≤pij≤100，pii=0，pij+pji=100)，表示第i号选手与第j号选手比赛获胜的概率。【输出文件】输出文件elimination.out。只有一个整数c，表示夺冠概率最大的选手编号（若有多位选手，输出编号最小者）。【样例输入】20905050100101050900505090500【样例输出】1【数据规模】30%的数据满足n≤3；100%的数据满足n≤10。2、种树（trees.pas/c/cpp）【问题描述】一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为

4、l…n。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b，e，t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b≤e，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t≤e-b+1，允许居民想种树的各自区域可以交叉。出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。【文件输入】第一行为n，表示区域的个数；第二行为h，表示房子的数目；下面h行描述居民的需要：bet（0

5、892352【样例输出】5【数据规模】30%的数据满足0

6、有且只有一行，为用空格隔开的两个正整数，依次为k，x。【文件输出】输出文件equation.out有且只有一行，为方程的正整数解组数。【样例输入】32【样例输出】3【数据范围】对于40%的数据，ans≤1016；对于100%的数据，k≤100，x≤231-1，k≤g(x)。4、物流运输（trans.pas/c/cpp）【问题描述】物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须

7、修改运输路线，让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。【文件输入】第一行是四个整数n(l≤n≤100)、m(l≤m≤20)、K和e。n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度(>0)。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下