國(guó)家集訓(xùn)隊(duì)2005論文集 金愷

《國(guó)家集訓(xùn)隊(duì)2005論文集 金愷》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、雜題大拼盤清華大學(xué)計(jì)42班金愷第一題新L游戲問題描述一個(gè)n行m列的棋盤，里面有一個(gè)或0個(gè)格子已經(jīng)損壞。請(qǐng)?jiān)谄灞P上放一些L棋子(如下)，使每個(gè)未損壞的格子都恰巧被一個(gè)L拼塊覆蓋。例如輸入有若干行(不超過100)，每行為一組數(shù)據(jù)：每行四個(gè)整數(shù)n,m,x,y；若x=0,y=0則表示所有格子都未損壞，否則表示第x行第y列的格子已損壞。如果有解輸出“Iknow!”否則輸“Noans!”數(shù)據(jù)范圍1≤n,m≤10100輸入樣例：551156009300100001000050004000輸出樣例：Iknow!Iknow!Noan

2、s!Iknow!第二題消滅魔鬼有N×M的格柵，每個(gè)格子不是平地就是障礙物（邊界為障礙物）。光線能水平或豎直的在平地上行進(jìn)，但是遇到障礙物就會(huì)引發(fā)爆炸。某些平地上已經(jīng)事先安放上了鏡子，有兩種方向的鏡子（都是雙面的）光線射在鏡子上就會(huì)反射，滿足反射角=入射角。鏡子#1鏡子#2戰(zhàn)士手拿激光槍站在A格的中心，魔鬼站在B格中心（A、B格都是平地且A≠B），請(qǐng)幫助戰(zhàn)士消滅魔鬼：在某些平地上添加一些鏡子，然后告訴戰(zhàn)士往哪個(gè)方向開激光槍。數(shù)據(jù)范圍：4≤N,M≤1000約束：任意兩面鏡子（包括事先放好的和你新添加的）都不能放在同一格

3、上；不能讓任何一個(gè)障礙物爆炸；數(shù)據(jù)保證有解；鏡子越少越好。AB平地障礙物AB輸出最小需要添加的鏡子數(shù)此例輸出2進(jìn)一步思考擴(kuò)展用最小費(fèi)用消滅魔鬼刪除原有鏡子，費(fèi)用f1，改變鏡子的方向，費(fèi)用f2，添加新的鏡子，費(fèi)用f3，移除障礙物，費(fèi)用f4。第三題機(jī)器人迷宮有一個(gè)n×m的迷宮，每個(gè)格子不是平地就是障礙物（邊界都是障礙物）。有p個(gè)機(jī)器人，全都站在平地上。某一時(shí)刻，你可以向所有機(jī)器人發(fā)布相同的指令，指令有N、S、W、E，告訴機(jī)器人向某個(gè)方向前進(jìn)。N表示向上，S表示向下，W表示向左，E表示向右。如果某個(gè)機(jī)器人能夠往該方向前進(jìn)

4、（即不碰到障礙物）則向該方向移動(dòng)一格，否則原地不動(dòng)。要求用不超過maxint條指令集結(jié)所有機(jī)器人——即讓他們到達(dá)同一位置。數(shù)據(jù)范圍：n,m≤50,p≤20。輸出：一個(gè)ESWN序列。序列長(zhǎng)度不能超過maxint；要求所有機(jī)器人按著這個(gè)序列執(zhí)行后到達(dá)同一格。思路2個(gè)機(jī)器人若在某個(gè)時(shí)刻T在同一位置，那么T時(shí)刻以后永遠(yuǎn)處在同一位置；先處理P=2，即兩個(gè)機(jī)器人然后每次選擇兩個(gè)位置不同的機(jī)器人，把他們合并，直到所有機(jī)器人都在同一個(gè)位置。如何集結(jié)指定的2個(gè)機(jī)器人？追趕法……思考合并兩個(gè)機(jī)器人的時(shí)間復(fù)雜度更低的方法？用盡量少的步數(shù)

5、？最少的步數(shù)？數(shù)據(jù)規(guī)模更大？別的思路？比如給整體局面打分，每次移動(dòng)都是整體更加靠緊，局面分降到0就恰好使機(jī)器人都集結(jié)（思路而已）。第4題正三角形（交互）題目背景：你僅有一個(gè)生銹的圓規(guī)，半徑固定為1。平面上有3個(gè)點(diǎn)：O(0,0)A(a,0)0

6、都為新的可操作的點(diǎn)。目標(biāo)，使得點(diǎn)C可操作,其中ABC構(gòu)成正三角形。第五題戰(zhàn)國(guó)長(zhǎng)城戰(zhàn)國(guó)時(shí)期，各諸侯國(guó)為了保護(hù)領(lǐng)土，建造了大量的長(zhǎng)城。長(zhǎng)城是由烽火臺(tái)和城墻組成的。烽火臺(tái)用一個(gè)平面上的點(diǎn)表示，而長(zhǎng)城則是連接兩個(gè)烽火臺(tái)的一堵筆直的墻，任意兩堵墻不會(huì)在非烽火臺(tái)處相交。任意一個(gè)烽火臺(tái)都有偶數(shù)堵城墻與它相連，每?jī)蓚€(gè)諸侯國(guó)都不相鄰，也就是說他們不會(huì)共有同一堵墻，但是有可能于某個(gè)烽火臺(tái)相鄰。問題：由于時(shí)代久遠(yuǎn)，當(dāng)時(shí)具體有多少個(gè)諸侯國(guó)已無從考證。所以，歷史學(xué)家們找到了參加信息學(xué)競(jìng)賽的你，請(qǐng)你根據(jù)長(zhǎng)城的遺址計(jì)算最多可能擁有的諸侯國(guó)數(shù)。x

7、y第六題傳輸奶牛平面上n個(gè)已知點(diǎn)。請(qǐng)你找出一個(gè)寬為L(zhǎng)en，長(zhǎng)為正無窮的矩形長(zhǎng)條；使得長(zhǎng)條中包含的已知點(diǎn)盡量多。N<=1000，坐標(biāo)都是絕對(duì)值不超過1000的整數(shù)。