教案雜題大拼盤

1、雜題大拼盤清華大學 計42班 金愷第一題 新L游戲問題描述一個n行m列的棋盤，里面有一個或0個格子已經損壞。請在棋盤上放一些L棋子(如下)，使每個未損壞的格子都恰巧被一個L拼塊覆蓋。 例如輸入有若干行(不超過100)，每行為一組數(shù)據(jù)：每行四個整數(shù)n,m,x,y；若x=0,y=0則表示所有格子都未損壞，否則表示第x行第y列的格子已損壞。 如果有解輸出“I know!” 否則輸 “No ans!”數(shù)據(jù)范圍 1n,m10100 輸入樣例：5 5 1 15 6 0 09 3 0 010000 10000 5000 4000輸出樣例：I know!I know!No ans!I know!第二題 消滅魔

2、鬼有NM的格柵，每個格子不是平地就是障礙物（邊界為障礙物）。光線能水平或豎直的在平地上行進，但是遇到障礙物就會引發(fā)爆炸。某些平地上已經事先安放上了鏡子，有兩種方向的鏡子（都是雙面的）光線射在鏡子上就會反射，滿足反射角=入射角。鏡子#1鏡子#2戰(zhàn)士手拿激光槍站在A格的中心，魔鬼站在B格中心（A、B格都是平地且AB），請幫助戰(zhàn)士消滅魔鬼：在某些平地上添加一些鏡子，然后告訴戰(zhàn)士往哪個方向開激光槍。數(shù)據(jù)范圍： 4N,M1000約束：任意兩面鏡子（包括事先放好的和你新添加的）都不能放在同一格上；不能讓任何一個障礙物爆炸；數(shù)據(jù)保證有解；鏡子越少越好。AB平地障礙物AB輸出最小需要添加的鏡子數(shù)此例輸出2進一

3、步思考擴展用最小費用消滅魔鬼刪除原有鏡子，費用f1，改變鏡子的方向，費用f2，添加新的鏡子，費用f3，移除障礙物，費用f4。第三題 機器人迷宮有一個nm的迷宮，每個格子不是平地就是障礙物（邊界都是障礙物）。有p個機器人，全都站在平地上。某一時刻，你可以向所有機器人發(fā)布相同的指令，指令有N、S、W、E，告訴機器人向某個方向前進。N表示向上，S表示向下，W表示向左，E表示向右。如果某個機器人能夠往該方向前進（即不碰到障礙物）則向該方向移動一格，否則原地不動。要求用不超過maxint條指令集結所有機器人即讓他們到達同一位置。數(shù)據(jù)范圍：n,m50 , p20 。輸出：一個ESWN序列。序列長度不能超過

4、maxint；要求所有機器人按著這個序列執(zhí)行后到達同一格。 思路2個機器人若在某個時刻T在同一位置，那么T時刻以后永遠處在同一位置；先處理P=2，即兩個機器人然后每次選擇兩個位置不同的機器人，把他們合并，直到所有機器人都在同一個位置。如何集結指定的2個機器人？追趕法思考合并兩個機器人的時間復雜度更低的方法？用盡量少的步數(shù)？最少的步數(shù)？數(shù)據(jù)規(guī)模更大？別的思路？比如給整體局面打分，每次移動都是整體更加靠緊，局面分降到0就恰好使機器人都集結（思路而已）。第4題 正三角形（交互）題目背景：你僅有一個生銹的圓規(guī)，半徑固定為1。平面上有3個點：O(0,0)A(a,0) 0a1B(b,0)請你通過使用這個生

5、銹的圓規(guī)，做出另一個點C，使得ABC為正三角形。交互方法（簡）最開始你能使用3個操作點，O,A,B?？梢赃M行下列操作增加新的可以操作的點。選取2個已知點X,Y；分別以X,Y為圓心，1為半徑作圓；2圓相交于Z1,Z2或相切于Z；則Z1,Z2或Z都為新的可操作的點。目標，使得點C可操作,其中ABC構成正三角形。第五題 戰(zhàn)國長城戰(zhàn)國時期，各諸侯國為了保護領土，建造了大量的長城。長城是由烽火臺和城墻組成的。烽火臺用一個平面上的點表示，而長城則是連接兩個烽火臺的一堵筆直的墻，任意兩堵墻不會在非烽火臺處相交。任意一個烽火臺都有偶數(shù)堵城墻與它相連，每兩個諸侯國都不相鄰，也就是說他們不會共有同一堵墻，但是有可能于某個烽火臺相鄰。問題：由于時代久遠，當時具體有多少個諸侯國已無從考證。所以，歷史學家們找到了參加信息學競賽的你，請你根據(jù)長城的遺址計算最多可能擁有的諸侯國數(shù)。