算法合集之《雜題大拼盤》.ppt

雜題大拼盤 清華大學(xué)計42班金愷 第一題新L游戲 問題描述一個n行m列的棋盤 里面有一個或0個格子已經(jīng)損壞 請在棋盤上放一些L棋子 如下 使每個未損壞的格子都恰巧被一個L拼塊覆蓋 例如 輸入有若干行 不超過100 每行為一組數(shù)據(jù) 每行四個整數(shù)n m x y 若x 0 y 0則表示所有格子都未損壞 否則表示第x行第y列的格子已損壞 如果有解輸出 Iknow 否則輸 Noans 數(shù)據(jù)范圍1 n m 10100 輸入樣例 551156009300100001000050004000 輸出樣例 Iknow Iknow Noans Iknow 第二題消滅魔鬼 有N M的格柵 每個格子不是平地就是障礙物 邊界為障礙物 光線能水平或豎直的在平地上行進(jìn) 但是遇到障礙物就會引發(fā)爆炸 某些平地上已經(jīng)事先安放上了鏡子 有兩種方向的鏡子 都是雙面的 光線射在鏡子上就會反射 滿足反射角 入射角 鏡子 1 鏡子 2 戰(zhàn)士手拿激光槍站在A格的中心 魔鬼站在B格中心 A B格都是平地且A B 請幫助戰(zhàn)士消滅魔鬼 在某些平地上添加一些鏡子 然后告訴戰(zhàn)士往哪個方向開激光槍 數(shù)據(jù)范圍 4 N M 1000約束 任意兩面鏡子 包括事先放好的和你新添加的 都不能放在同一格上 不能讓任何一個障礙物爆炸 數(shù)據(jù)保證有解 鏡子越少越好 平地 障礙物 輸出最小需要添加的鏡子數(shù)此例輸出2 進(jìn)一步思考 擴(kuò)展用最小費(fèi)用消滅魔鬼刪除原有鏡子 費(fèi)用f1 改變鏡子的方向 費(fèi)用f2 添加新的鏡子 費(fèi)用f3 移除障礙物 費(fèi)用f4 第三題機(jī)器人迷宮 有一個n m的迷宮 每個格子不是平地就是障礙物 邊界都是障礙物 有p個機(jī)器人 全都站在平地上 某一時刻 你可以向所有機(jī)器人發(fā)布相同的指令 指令有N S W E 告訴機(jī)器人向某個方向前進(jìn) N表示向上 S表示向下 W表示向左 E表示向右 如果某個機(jī)器人能夠往該方向前進(jìn) 即不碰到障礙物 則向該方向移動一格 否則原地不動 要求用不超過maxint條指令集結(jié)所有機(jī)器人 即讓他們到達(dá)同一位置 數(shù)據(jù)范圍 n m 50 p 20 輸出 一個ESWN序列 序列長度不能超過maxint 要求所有機(jī)器人按著這個序列執(zhí)行后到達(dá)同一格 思路 2個機(jī)器人若在某個時刻T在同一位置 那么T時刻以后永遠(yuǎn)處在同一位置 先處理P 2 即兩個機(jī)器人然后每次選擇兩個位置不同的機(jī)器人 把他們合并 直到所有機(jī)器人都在同一個位置 如何集結(jié)指定的2個機(jī)器人 追趕法 思考 合并兩個機(jī)器人的時間復(fù)雜度更低的方法 用盡量少的步數(shù) 最少的步數(shù) 數(shù)據(jù)規(guī)模更大 別的思路 比如給整體局面打分 每次移動都是整體更加靠緊 局面分降到0就恰好使機(jī)器人都集結(jié) 思路而已 第4題正三角形 交互 題目背景 你僅有一個生銹的圓規(guī) 半徑固定為1 平面上有3個點(diǎn) O 0 0 A a 0 0 a 1B b 0 請你通過使用這個生銹的圓規(guī) 做出另一個點(diǎn)C 使得ABC為正三角形 交互方法 簡 最開始你能使用3個操作點(diǎn) O A B 可以進(jìn)行下列操作增加新的可以操作的點(diǎn) 選取2個已知點(diǎn)X Y 分別以X Y為圓心 1為半徑作圓 2圓相交于Z1 Z2或相切于Z 則Z1 Z2或Z都為新的可操作的點(diǎn) 目標(biāo) 使得點(diǎn)C可操作 其中ABC構(gòu)成正三角形 第五題戰(zhàn)國長城 戰(zhàn)國時期 各諸侯國為了保護(hù)領(lǐng)土 建造了大量的長城 長城是由烽火臺和城墻組成的 烽火臺用一個平面上的點(diǎn)表示 而長城則是連接兩個烽火臺的一堵筆直的墻 任意兩堵墻不會在非烽火臺處相交 任意一個烽火臺都有偶數(shù)堵城墻與它相連 每兩個諸侯國都不相鄰 也就是說他們不會共有同一堵墻 但是有可能于某個烽火臺相鄰 問題 由于時代久遠(yuǎn) 當(dāng)時具體有多少個諸侯國已無從考證 所以 歷史學(xué)家們找到了參加信息學(xué)競賽的你 請你根據(jù)長城的遺址計算最多可能擁有的諸侯