Noip2009四校联考模拟试题2.pdf

备战 Noip2009 四校联考模拟试题 2009 年四校联考模拟试题 （时间：11 月 1 日 上午 8:30—11:30） 题目名称 淘汰赛制 种树 方程的解 物流运输 题目程序名 elimination.pas/c/cpp trees.pas/c/cpp equation.pas/c/cpp trans.pas/c/cpp 输入文件名 elimination.in trees.in equation .in trans.in 输出文件名 elimination.out trees.out equation.out trans.out 测试点时限 1s 1s 1s 1s 测试点个数 10 10 10 10 测试点分值 10 10 10 10 内存限制 256MB 256MB 256MB 256MB 【注意事项】：请自行完成题目，切勿讨论。 1.淘汰赛制 (elimination.pas/c/cpp) 【问题描述】 n n-1 n 淘汰赛制是一种极其残酷的比赛制度。2 名选手分别标号 1，2，3，……2 ，2 ，他们 将要参加n轮的激烈角逐。每一轮中，将所有参加该轮的选手按标号从小到大排序后，第 1 位与第 2 位比赛，第 3 位与第 4 位比赛，第 5 位与第 6 位比赛……只有每场比赛的胜者才有 机会参加下一轮的比赛（不会有平局）。这样，每轮将淘汰一半的选手。n轮过后，只剩下一 名选手，该选手即为最终的冠军。 现在已知每位选手分别与其他选手比赛获胜的概率，请你预测一下谁夺冠的概率最大。 【输入文件】 输入文件elimination.in。第一行是一个整数n（1=n=10），表示总轮数。接下来 2n行， 每行 2n个整数，第i行第j个是p （0=p=100，p =0，p +p =100），表示第i号选手与第j ij ij ii ij ji 号选手比赛获胜的概率。 【输出文件】 输出文件 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 备战 Noip2009 四校联考模拟试题 2. 种树 （trees.pas/c/cpp） 【问题描述】 一条街的一边有几座房子。因为环保原因居民想要在路边种些树。路边的地区被分割成 块，并被编号为 1..n。每个块的大小为一个单位尺寸并最多可种一棵树。每个居民想在门 前种些树并指定了三个号码 b，e，t。这三个数表示该居民