沖刺NOIP模擬試題與解析

1、沖刺NOIP2009模擬試題與解析(六)廣東省中山紀(jì)念中學(xué)宋新波(普及組復(fù)賽)題目題目名稱上學(xué)路線遺址郁悶的記者最輕的天平文件名routerui nrankmobile測試點數(shù)5101014分值100100100100時限IS1S1S1S說明：1 文件名(程序名和輸入輸出文件名)必須使用小寫；2 . C/C+沖函數(shù)ma i n()的返回值類型必須是int，程序正常結(jié)束時的返回 值必須是0;3.每道題目都必須建立文件夾。1 .上學(xué)路線(route . pas/ c/ cpp)【題目描述】你所在城市的街道好像一個棋盤，有a條南北方向的街道和b條東西方向的 街道。南北方向的a條街道從西到東依次編號為

2、I到a,而東西方向的b條街道 從南到北依次編號為I到b,南北方向的街道i和東西方向的街道j的交點記為 (i , j)。你住在(1 , 1)處，而學(xué)校在(a , b)處，你騎自行車去上學(xué)，自行車只能沿著 街道走，而且為了縮短時間只允許沿著向東和北的方向行駛?，F(xiàn)在有N個交叉路口在施工(X1 , 丫1)、(X2, Y2),(Xn, Yn),這些路口是 不能通車的。問你上學(xué)一共有多少走法？【輸入格式】第一行包含兩個整數(shù)a和b,并且滿足 Ka, b< 16。第二行包含一個整數(shù)N,表示有N個路口在維修(1 < NK 40)。接下來N行，每行兩個整數(shù)X_i, Y_i，描述路口的位置。【輸出格式】

3、輸出一個整數(shù)表示從(1 , 1)到(a , b)的行車路線總數(shù)。【樣例輸入輸出】Route. inRoute . out5 4532 22 34 2【樣例數(shù)據(jù)解釋】JOI High School（5,4）J網(wǎng)J1 '1J(1,1)Taro' s Home2 .遺址（ruin . pas/c/cpp）【題目描述】很久很久以前有一座寺廟，從上往下看寺廟的形狀正好是一個正方形，由 4 個角上豎立的圓柱搭建而成?，F(xiàn)在圓柱都倒塌了，只在地上留下圓形的痕跡，可 是現(xiàn)在地上有很多這樣的痕跡，專家說一定是最大的那個。寫一個程序，給出圓柱的坐標(biāo)，找出由4個圓柱構(gòu)成的最大的正方形，因為 這就是寺廟

4、的位置，要求計算出最大的面積。注意正方形的邊不一定平行于坐標(biāo) 軸。例如右上圖有10根柱子，其中（4，2），（5，2），（5，3），（4，3）可以形成 一個正方形，（1，1），（4，O），（5，3），（2，4）也可以，后者是其中最大的，面 積為10?！据斎敫袷健康谝恍邪粋€N（1W NK 3 0 0 0），表示柱子的數(shù)量。接下來N行，每行有兩個空格隔開的整數(shù)表示柱子的坐標(biāo)（坐標(biāo)值在0到 5000之間），柱子的位置互不相同?！据敵龈袷健咳绻嬖谡叫?，輸出最大的面積，否則輸出 0【樣例輸入輸出】Ruin. inRuin . out10M09 44 31 14 22 45 84 05 30 55

5、2【數(shù)據(jù)范圍】30%滿足：K NK 10060%滿足：K NK 500。3 .郁悶的記者(rank . pa s /c/cpp)【題目描述】你是一個體育報社的記者，你接受到一個艱難的任務(wù)：有N支足球隊參加足 球比賽，現(xiàn)在給你一些比賽的結(jié)果，需要你給出各支球隊的排名，從1到No以下是給你的一些信息：沒有平局；(2) 不同的球隊排名不能相同；(3) 對于所有滿足I <a<b<n,第a名的球隊一定可以打敗第b名的球隊。 給你部分比賽結(jié)果，要求給出排名，并且判斷是否存在另一種排名方法滿足 給你的比賽結(jié)果。【輸入格式】第一行輸入N(1W NK 5000),表示球隊的數(shù)量，編號為I到N。

6、第二行輸入 M(1< M 100,000),表示給出的比賽場數(shù)。接下來M行，每行兩個整數(shù)X，丫, 表示X_i能打敗Y_i。【輸出格式】輸出包含N+1行，前N行描述球隊的排名，第i個數(shù)表示第i名的球隊， 第N+1行包含一個整數(shù)，如果為0表示不存在其他的排名方法，如果為1表示還 有其他的排名方法。【樣例輸入輸出】Rank, inRank. out435412131232O413221213231【數(shù)據(jù)范圍】30%的數(shù)據(jù)滿足：I < N< 7，K M 1560 % 的數(shù)據(jù) 滿足：I < N< 100，K MK 20004 .最輕的天平(mobile . pas/c/cp

7、p)【題目描述】天平的兩邊有時不一定只能掛物品， 還可以繼續(xù)掛著另一個天平，現(xiàn)在給你 一些天平的情況和它們之間的連接關(guān)系，要求使得所有天平都能平衡所需物品的 總重量最輕，一個天平平衡當(dāng)且僅當(dāng)“左端點的重量*左端點到支點的距離二右端 點的重量*右端點到支點的距離”。注意題目中的輸入保證這些天平構(gòu)成一個整 體。【輸入格式】第一行包含一個N(N< 100)，表示天平的數(shù)量，天平編號為l到N,接下來 包含N行描述天平的情況，每行4個整數(shù)P、Q R、B, P和Q表示橫桿上支點到 左邊的長度與到右邊的距離的比例為P: Q, R表示左邊懸掛的情況，如果 R=0說明懸掛的是物品，否則表示左邊懸掛的是天平 R; B表示右邊的懸掛情況，如 果B=O表示右邊懸掛的是物品，否則右邊懸掛著天平 Bo對于所有的輸入，保證 W*L<2A31,其中w為