NOIP2013普及組模擬試題2

1、全國(guó)信息學(xué)奧林匹克聯(lián)賽（NOIP2013）復(fù)賽模擬普及組.題目概覽中文題目名稱mirrors刷墻算周長(zhǎng)饑餓的奶牛英文題目名稱mirrorspainttruthhunger可執(zhí)行文件名mirrorspainttruthhunger輸入文件名ruth.inhunger.in輸出文件名mirrors.outpaint.outtruth.outhunger.out每個(gè)測(cè)試點(diǎn)時(shí)限1秒1秒1秒1秒測(cè)試點(diǎn)數(shù)目10101010每個(gè)測(cè)試點(diǎn)分值10101010比較方式全文比較全文比較全文比較全文比較題目類型傳統(tǒng)傳統(tǒng)傳統(tǒng)傳統(tǒng).提交源程序文件名對(duì)于pascal語(yǔ)百mirrors.

2、paspaint.pastruth.pashunger.pas對(duì)于C語(yǔ)言mirrors.cpaint.ctruth.chunger.c對(duì)于C+語(yǔ)言mirrors.cpppaint.cpptruth.cpphunger.cpp三.編譯命令（不包含任何優(yōu)化開(kāi)關(guān)）對(duì)于pascal語(yǔ)言fpcqueue.pasfpcwindows.pasfpcs4.pasfpcbook.pas對(duì)于C語(yǔ)言gcc-oqueuequeue.cgccpwindowswindows.cgcc-os4s4.cgcc-obookbook.c對(duì)于C+語(yǔ)言g+-oqueuequeue.cppg+-owindowswindows.cppg

3、+-os4s4.cppg+-obookbook.cpp四.運(yùn)行內(nèi)存限制運(yùn)行內(nèi)存上限50M50M50M50M注意事項(xiàng)：1、文件名（程序名和輸入輸出文件名）必須使用小寫(xiě)。2、C/C+中函數(shù)main（）的返回值類型必須是int,程序正常結(jié)束時(shí)的返回值必須是0。mirrors（mirrors.pas/c/cpp）【問(wèn)題描述】FarmerJohn的奶牛在農(nóng)場(chǎng)周圍制造了很多麻煩，所以他想要更加密切地關(guān)注它們。通過(guò)在農(nóng)場(chǎng)的不同位置安裝N塊反光柵欄（1<=N<=200）,他希望能夠從他的房間（在（0,0）位置）看得到谷倉(cāng)中（a,b）的位置。在Farmerjohn農(nóng)場(chǎng)的2D地圖上，柵欄i用一條短線段

4、表示，這條線段的中心在整型數(shù)位置（x_i,y_i）并且傾斜45度，如/'和'例如，一根形如'/'在（3,5）的柵欄可以被表示成一根從（2.9,4.9）到（3.1,5.1）線段。每根柵欄（也包括整個(gè)谷倉(cāng)的位置）都在不同的整數(shù)坐標(biāo)范圍內(nèi)-1,000,000.1,000,000。沒(méi)有一根柵欄在（0,0）或者（a,b）。FarmerJohn計(jì)劃坐在他的房間（0,0）里，直接向右看（在+x方向）。當(dāng)他的目光從農(nóng)場(chǎng)上一些反光柵欄上掠過(guò)，他希望能看到點(diǎn)（a,b）o不幸的是，F(xiàn)armerJohn認(rèn)為他將一根柵欄的方向安裝得不正確（例如，是，而不是/'）。請(qǐng)輸出在Farm

5、erJohn列表上需要更改的第一根柵欄的序號(hào)，修改它的方向后（在/'和'之間修改，或反之亦然），F(xiàn)armerJohn能夠看見(jiàn)點(diǎn)（a,b）。如果FarmerJohn不改變?nèi)魏螙艡诘姆较蚓涂梢钥匆?jiàn)點(diǎn)（a,b）,請(qǐng)輸出0。如果在改變了一個(gè)柵欄后仍然看不見(jiàn)（a,b）,則輸出-1?！据斎敫袷健?第1行：三個(gè)空格隔開(kāi)的整型數(shù)，N,a和b。*第2.1+N行：第i+1行描述了第i根柵欄，表示為"x_iy_i/"或者"x_iy_i"其中，（x_i,y_i）是該柵欄中心的位置，/或''表明它的方向。【輸出格式】56230/02/12/321

6、3H表示Farmer John的房子和 B表示谷倉(cāng)）輸入詳情：農(nóng)場(chǎng)的地圖如下（3.2/.B1 .0H./.0123456。【輸入樣例】56230/輸入詳情：農(nóng)場(chǎng)的地圖如下（H表示FarmerJohn的房子和B表示谷倉(cāng)）3 .4 /.B1.0H./0123456【輸出樣例】輸出詳情：通過(guò)改變?cè)冢?,2）位置的柵欄，F(xiàn)armerJohn可以看見(jiàn)點(diǎn)（a,b）。地圖上顯示為:3.2./-B1|0H-/0123456刷墻（paint.pas/c/c+）【問(wèn)題描述】FarmerJohn已經(jīng)設(shè)計(jì)了一種方法來(lái)裝飾谷倉(cāng)旁邊的長(zhǎng)柵欄（把柵欄認(rèn)為是一根一維的線）。他把一只畫(huà)刷綁在他最喜愛(ài)的奶牛Bessie身上，之后

7、就去喝一杯冰水，而B(niǎo)essie隔著柵欄來(lái)回走，當(dāng)她走過(guò)某個(gè)地方，這里的一段柵欄就被刷上了涂料。Bessie從柵欄上的位置0開(kāi)始，并且遵循著一個(gè)N次移動(dòng)的次序（1<=N<=100,000）。例如“10L”表示Bessie向左移動(dòng)了10個(gè)單位長(zhǎng)度，“15R”表示Bessie向右移動(dòng)了15個(gè)單位長(zhǎng)度?，F(xiàn)給出Bessie所有移動(dòng)的列表，F(xiàn)armerJohn想要知道哪些區(qū)域的柵欄至少涂了兩層涂料（只涂一層涂料的區(qū)域可能在大雨中被洗掉）。Bessie在她的行走中最遠(yuǎn)到達(dá)距起始點(diǎn)1,000,000,000個(gè)單位長(zhǎng)度?！据斎敫袷健康?行：一個(gè)整型數(shù)No第2。1+N行：每行描述了Bessie的N次移

8、動(dòng)中的一次，例如“15L”?！据敵龈袷健?行：被至少涂了兩層涂料的區(qū)域總數(shù)?！据斎霕永?2R6L1R8L1 R2 R輸入詳情：Bessie從位置0開(kāi)始，向右移動(dòng)2個(gè)單位長(zhǎng)度，向左移動(dòng)6個(gè)單位長(zhǎng)度，向右移動(dòng)1個(gè)單位長(zhǎng)度，向左移動(dòng)8個(gè)單位長(zhǎng)度，最后向右移動(dòng)3個(gè)單位長(zhǎng)度?！据敵鰳永?輸出詳情：6個(gè)單位區(qū)域至少被涂了兩層涂料，是-11,-8,-4,-3,0,2這些區(qū)域。LiarsandTruthTellers(truth.pas/c/c+)【問(wèn)題描述】在花了許多時(shí)間陪伴奶牛之后，F(xiàn)armerJohn開(kāi)始理解它們的語(yǔ)言。而且，他注意到在他的N頭奶牛中（2<=N<=1000）,一些總是說(shuō)真

9、話，而一些總是說(shuō)假話。FJ仔細(xì)地聽(tīng)了奶牛們的N段陳述，每段陳述的格式為“xyT”，表示“奶牛x聲稱奶牛y總說(shuō)真話”，或者“xyL”，表示“奶牛x聲稱奶牛y總說(shuō)假話”。每段陳述包括兩頭不同的奶牛，相同對(duì)的奶?？梢猿霈F(xiàn)在不同的陳述里。不幸的是，F(xiàn)J相信他可能在他的列表里寫(xiě)了一些不正確的，所以可能沒(méi)有一個(gè)有效的方法去劃定每頭奶牛是說(shuō)真話還是假話并且與FJ列表上M條陳述都一致。為了幫助FJ搶救盡可能多的列表，請(qǐng)計(jì)算能夠以有效方法劃定每頭奶牛是說(shuō)真話還是假話的陳述的最大值。輸入格式：*第1行：兩個(gè)空格隔開(kāi)的整型數(shù)，N和M*第2。1+M行：每行的格式為“xyL”或者“xyT”，描述奶牛x對(duì)奶牛y的陳述。輸

10、入樣例（文件truth.in）:431 4L2 3T4 1T輸入詳情：現(xiàn)在有4頭奶牛和3段陳述。奶牛1說(shuō)奶牛4說(shuō)假話，奶牛2說(shuō)奶牛3說(shuō)真話，奶牛4說(shuō)奶牛1說(shuō)真話。輸出格式：*第1行：能夠以有效方法劃定每頭奶牛是說(shuō)真話還是假話的陳述的最大值。輸出樣例（文件truth.out）:2輸出詳情：陳述1和陳述3不能同時(shí)滿足，但是陳述1和陳述2可以，此時(shí)我們讓奶牛1,2,3說(shuō)真話，奶牛4說(shuō)假話。饑餓的奶牛(hunger.pas/c/c+)【問(wèn)題描述】牛在飼料槽前排好了隊(duì)。飼料槽依次用1到N(1<=N<=2000)編號(hào)。每天晚上，一頭幸運(yùn)的牛根據(jù)約翰的規(guī)則，吃其中一些槽里的飼料。約翰提供B個(gè)區(qū)間的清單。一個(gè)區(qū)間是一對(duì)整數(shù)start-end,1<=start<=end<=N,表示一些連續(xù)的飼料槽，比如1-3,7-8,3-4等等。?？梢匀我膺x擇區(qū)間，但是牛選擇的區(qū)間不能有重疊。當(dāng)然，牛希望自己能夠吃得越多越好。給出一些區(qū)間，幫助這只牛找一些區(qū)間，使它能吃到