冲刺NOIP2010模拟试题与解析（一）
题目
（提高组时间：3个小时） 难易指数：★★★ 题目名称 输入文件名 淘汰赛制 elimination.in 种树 treesm trees.out 1s 10 10 256MB 方程的解 equation.in equation.out 1s lO 10 256MB 物流运输 trans.in trans.out 1s 10 lo 256MB 题目程序名 elimination.pas/c/cpp trees.pas/c/cpp equation.pas/c/cpp trans.pas/c/cpp 输出文件名 elimination.out 测试点时限 测试点个数 测试点分值 内存限制 1s 10 10 256MB 1、淘汰赛制(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)，表示总轮数。接下来2n行，每行2n个整数，第i行第j个是pij(0≤pij≤100，pii=0，pij+pji=100)，表示第i号选手与第j号选手比赛获胜的概率。 【输出文件】
输出文件elimination.out。只有一个整数c，表示夺冠概率最大的选手编号（若有多位选手，输出编号最小者）。 【样例输入】 2
0 90 50 50 10 0 10 10 50 90 0 50 50 90 50 0
【样例输出】 1
【数据规模】
30%的数据满足n≤3；100%的数据满足n≤10。
2、种树（trees.pas/c/cpp）
【问题描述】
一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成块，并被编号为l…n。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门前种些树并指定了三个号码b，e，t。这三个数表示该居民想在b和e之间最少种t棵树。当然，b≤e，居民必须保证在指定地区不能种多于地区被分割成块数的树，即要求t≤e-b+1，允许居民想种树的各自区域可以交叉。出于资金短缺的原因，环保部门请你求出能够满足所有居民的要求，需要种树的最少数量。 【文件输入】
第一行为n，表示区域的个数；第二行为h，表示房子的数目；下面h行描述居民的需要：b e t（0 输出为满足所有要求的最少树的数量。 【样饲输入】 9 4 1 4 2 4 6 2 8 9 2 3 5 2 【样例输出】 5 【数据规模】 30%的数据满足0 3、方程的解(equation.pas/c/cpp) 【问题描述】 佳佳碰到了一个难题，请你来帮忙解决。 对于不定方程a1+a2+…+ak-1+ak=g(x)，其中k≥2且k∈N，x是正整数，g(x)=xx mod 1000(即xx除以1000的余数)，x，k是给定的数。我们要求的是这个不定方程的正整数解组数。 举例来说，当k=3，x=2时，分别为(a1,a2,a3)=(2,1,1)'(1,2,1)，(1,1,2)。 【文件输入】 输入文件equation.in有且只有一行，为用空格隔开的两个正整数，依次为k，x。 【文件输出】 输出文件equation.out有且只有一行，为方程的正整数解组数。 【样例输入】 3 2 【样例输出】 3 【数据范围】 对于40%的数据，ans≤1016；对于100%的数据，k≤100，x≤231-1，k≤g(x)。 4、物流运输（trans.pas/c/cpp） 【问题描述】 物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是—件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。 【文件输入】 第一行是四个整数n(l≤n≤100)、m(l≤m≤20)、K和e。n表示货物运输所需天数，m表示码头总数，K表示每次修改运输路线所需成本。接下来e行每行是一条航线描述，包括了三个整数，依次表示航线连接的两个码头编号以及航线长度(>0)。其中码头A编号为1，码头B编号为m。单位长度的运输费用为1。航线是双向的。再接下来一行是一个整数d，后面的d行每行是三个整数P(1 包括了一个整数表示最小的总成本。总成本=n天运输路线长度之和+K*改变运输路线的次数。 【样例输入】 5 5 10 8 1 2 1 1 3 3 1 4 2 2 3 2 2 4 4 3 4 1 3 5 2 4 5 2 4 2 2 3 3 1 1 3 3 3 4 4 5 【样例输出】 32 【样例输入说明】