算法合集之《雜題大拼盤(pán)》.ppt

雜題大拼盤(pán) 清華大學(xué)計(jì)42班金愷 第一題新L游戲 問(wèn)題描述一個(gè)n行m列的棋盤(pán) 里面有一個(gè)或0個(gè)格子已經(jīng)損壞 請(qǐng)?jiān)谄灞P(pán)上放一些L棋子 如下 使每個(gè)未損壞的格子都恰巧被一個(gè)L拼塊覆蓋 例如 輸入有若干行 不超過(guò)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 Noans 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è)方向開(kāi)激光槍 數(shù)據(jù)范圍 4 N M 1000約束 任意兩面鏡子 包括事先放好的和你新添加的 都不能放在同一格上 不能讓任何一個(gè)障礙物爆炸 數(shù)據(jù)保證有解 鏡子越少越好 平地 障礙物 輸出最小需要添加的鏡子數(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) 即不碰到障礙物 則向該方向移動(dòng)一格 否則原地不動(dòng) 要求用不超過(guò)maxint條指令集結(jié)所有機(jī)器人 即讓他們到達(dá)同一位置 數(shù)據(jù)范圍 n m 50 p 20 輸出 一個(gè)ESWN序列 序列長(zhǎng)度不能超過(guò)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ù) 最少的步數(shù) 數(shù)據(jù)規(guī)模更大 別的思路 比如給整體局面打分 每次移動(dòng)都是整體更加靠緊 局面分降到0就恰好使機(jī)器人都集結(jié) 思路而已 第4題正三角形 交互 題目背景 你僅有一個(gè)生銹的圓規(guī) 半徑固定為1 平面上有3個(gè)點(diǎn) O 0 0 A a 0 0 a 1B b 0 請(qǐng)你通過(guò)使用這個(gè)生銹的圓規(guī) 做出另一個(gè)點(diǎn)C 使得ABC為正三角形 交互方法 簡(jiǎn) 最開(kāi)始你能使用3個(gè)操作點(diǎn) O A B 可以進(jìn)行下列操作增加新的可以操作的點(diǎn) 選取2個(gè)已知點(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)國(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ó)都不相鄰 也就是說(shuō)他們不會(huì)共有同一堵墻 但是有可能于某個(gè)烽火臺(tái)相鄰 問(wèn)題 由于時(shí)代久遠(yuǎn) 當(dāng)時(shí)具體有多少個(gè)諸侯國(guó)已無(wú)從考證 所以 歷史學(xué)家們找到了參加信息學(xué)競(jìng)賽的你 請(qǐng)你根據(jù)長(zhǎng)城的遺址計(jì)算最多可能擁有的諸侯