冲刺CCF NOIP2012模拟试题与解析(普及组).docVIP

冲刺CCF NOIP2012模拟试题与解析(普及组) 题目 说明： 1．文件名(程序名和输入输出文件名)必须使用小写； 2．C／C++中函数ma i n()的返回值类型必须是int，程序正常结束时的返回值必须是0； 3. 每道题目都必须建立文件夹。 1．上学路线(route．pas／c／cpp) 【题目描述】 你所在城市的街道好像一个棋盘，有a条南北方向的街道和 b条东西方向的街道。南北方向的a条街道从西到东依次编号为l到a，而东西方向的b条街道从南到北依次编号为l到b，南北方向的街道i和东西方向的街道j的交点记为(i，j)。 你住在(1，1)处，而学校在(a，b)处，你骑自行车去上学，自行车只能沿着街道走，而且为了缩短时间只允许沿着向东和北的方向行驶。 现在有N个交叉路口在施工(X1，Yl)、(X2，Y2)??，(Xn，Yn)，这些路口是不能通车的。 问你上学一共有多少走法? 【输入格式】 第一行包含两个整数a和b，并且满足1≤a，b≤16。 第二行包含一个整数N，表示有N个路口在维修(1≤N≤40)。 接下来N行，每行两个整数X_i，Y_i，描述路口的位置。 【输出格式】 输出一个整数表示从(1，1)到(a，b)的行车路线总数。 1 【样例数据解释】 JOI High School (5,4) (1,1) Taro’s Home 2．遗址(ruin．pas／c／cpp) 【题目描述】 很久很久以前有一座寺庙，从上往下看寺庙的形状正好是一个正方形，由4个角上竖立的圆柱搭建而成。现在圆柱都倒塌了，只在地上留下圆形的痕迹，可是现在地上有很多这样的痕迹，专家说一定是最大的那个。 写一个程序，给出圆柱的坐标，找出由4个圆柱构成的最大的正方形，因为这就是寺庙的位置，要求计算出最大的面积。注意正方形的边不一定平行于坐标轴。 例如右上图有l0根柱子，其中(4，2)，(5，2)，(5，3)，(4，3)可以形成一个正方形，(1，1)，(4，O)，(5，3)，(2，4)也可以，后者是其中最大的，面积为l0。 【输入格式】 第一行包含一个N(1≤N≤3 0 0 0)，表示柱子的数量。 接下来N行，每行有两个空格隔开的整数表示柱子的坐标(坐标值在0到5000之间)，柱子的位置互不相同。 【输出格式】 如果存在正方形，输出最大的面积，否则输出0。 2 【样例输入输出】 【数据范围】 30％满足：1≤N≤100 60％满足：1≤N≤500。 3．郁闷的记者(rank．pa s／c／cpp) 【题目描述】 你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。 以下是给你的一些信息： (1)没有平局； (2)不同的球队排名不能相同； (3)对于所有满足l≤alt;b≤n，第a名的球队一定可以打败第b名的球队。 给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足 3 给你的比赛结果。 【输入格式】 第一行输入N(1≤N≤5000)，表示球队的数量，编号为l到N。第二行输入M(1≤M≤100,000)，表示给出的比赛场数。接下来M行，每行两个整数X_i，Y_i，表示X_i能打败Y_i。 【输出格式】 输出包含N+1行，前N行描述球队的排名，第i个数表示第i名的球队，第N+1行包含一个整数，如果为0表示不存在其他的排名方法，如果为1表示还有其他的排名方法。 【数据范围】 30％的数据满足：l≤N≤7，1≤M≤15 60％的数据满足：l≤N≤100，1≤M≤2000 4．最轻的天平(mobile．pas／c／cpp) 【题目描述】 天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和它们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻，一个天平平衡当且仅当“左端点的重量*左端点到支点的距离=右端点的重量*右端点到支点的距离”。注意题目中的输入保证这些天平构成一个整体。 【输入格式】 第一行包含一个N(N≤100)，表示天平的数量，天平编号为l到N，接下来包含N行描述天平的情况，每行4个整数P、Q、R、B，P和Q表示横杆上支点到左边的长度与到右边的距