信息學(xué)國家集訓(xùn)隊(duì)作業(yè)0072-superturn_第1頁
信息學(xué)國家集訓(xùn)隊(duì)作業(yè)0072-superturn_第2頁
信息學(xué)國家集訓(xùn)隊(duì)作業(yè)0072-superturn_第3頁
全文預(yù)覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、題目 0072 Superturn(超級(jí)翻轉(zhuǎn))題目來源:New者:一、英文原文二、中文翻譯超級(jí)翻轉(zhuǎn)有一個(gè) N*N 的網(wǎng)格,每一“格”上有一個(gè)可以翻轉(zhuǎn)的方塊,方塊的兩面分別黑、白兩種顏色。另外,有一個(gè)沿著網(wǎng)格線活動(dòng)的東西不妨稱之為“動(dòng)子”。初始時(shí),每個(gè)方塊隨機(jī)地被翻成黑或白色,“動(dòng)子”停在網(wǎng)格線的某個(gè)頂點(diǎn)上。例如如圖一就是一個(gè) 4*4的網(wǎng)格的一種可能的開局情況。動(dòng)子在網(wǎng)格線上運(yùn)動(dòng)時(shí),從一個(gè)頂點(diǎn) A 到相鄰的另一個(gè)頂點(diǎn) B 之后,以網(wǎng)格線 AB 為邊的兩個(gè)或一個(gè)網(wǎng)格上的方塊就會(huì)翻轉(zhuǎn)白變黑,黑變白。例如圖一的“動(dòng)子”向右移動(dòng)一步之后變成圖二,向下移動(dòng)一步之后變成圖三。問題是:給定一個(gè)初始狀態(tài)和一個(gè)目

2、標(biāo)狀態(tài),求“動(dòng)子”的一種運(yùn)動(dòng)軌跡,可以把初始狀態(tài)翻轉(zhuǎn)成目標(biāo)狀態(tài),最后“動(dòng)子”停在哪里是無所謂的。三、初步情況搜索吧。求可行解怎么使用解模方程組的方法,我只嘗試用搜索解決,在小數(shù)據(jù)的情況應(yīng)該沒有問題,但是璟求可行解時(shí)怎么用解方程組的方法解決呢?沒想到有效算法,不過也以通過解方程來進(jìn)行初始化。可行解似乎可以通過解方程+構(gòu)造但最優(yōu)解不會(huì)雖然可以用設(shè)未知數(shù)解方程的方式,求出每一條邊應(yīng)經(jīng)過次數(shù)的奇偶性。但是要使這些連續(xù),有得是最少,確實(shí)不容易。目前的想法:可以先考慮解方程,若方程無解,則問題無解,也可能有多組解,檢驗(yàn)一組解的方法:如果度為奇數(shù)的點(diǎn)的個(gè)數(shù)小于等于 2 且為 2 時(shí)起點(diǎn)的度為奇數(shù),則該組解能

3、構(gòu)成路徑。于是分度為奇數(shù)的點(diǎn)的個(gè)數(shù)為 0 和 2 的情況:為 0 時(shí),加上一些方程;為 2 時(shí)只要枚舉終點(diǎn),并令此點(diǎn)度數(shù)為奇數(shù),解方程即可。最優(yōu)解算法正在研究之中。最優(yōu)解沒什么辦法。可行解倒是可以。給每條邊設(shè)一個(gè)未知數(shù),取 0 或者 1,表示經(jīng)過或者不經(jīng)過。枚舉終點(diǎn)和起點(diǎn)。然后列一些同余方程:1、 可以確定每個(gè)格子周圍 4 條邊的和的奇偶性。2、 除起點(diǎn)和終點(diǎn)外每個(gè)點(diǎn)相連的 4 條邊(或 3 條邊)的和為偶數(shù)。3、 起點(diǎn)終點(diǎn)相連的 4 條邊(或 3 條邊)的和為奇數(shù)。即可。看似正確的做法:枚舉終點(diǎn)(假設(shè)它和起點(diǎn)不同),對于每條(有向的)邊 i,設(shè)它的經(jīng)過次數(shù)為 Xi,這樣就需要滿足每個(gè)頂點(diǎn)出去

4、的邊和進(jìn)入的邊總數(shù)相等,特例是起點(diǎn)出度比入度大一,終點(diǎn)入度比出度大一。這樣可以列出方程,就可以把方案解出來。但是實(shí)際上這樣沒有辦法保證這個(gè)圖是連通的。不知怎樣改進(jìn)?如果終點(diǎn)和起點(diǎn)相同,也有類似的麻煩??梢韵韧ㄟ^解模線性方程組求得“動(dòng)子”經(jīng)過每條網(wǎng)格邊次數(shù)的奇偶性,而后通過 bfs求出最短路徑。但 bfs 的效率到底如何好像很難確定。解模線性方程組,每條邊是一個(gè)未知數(shù),對于每個(gè)格子可以列出一個(gè)方程,而且還有隱含的條件,就是題目要求移動(dòng)出一條路來,這樣的話,與每個(gè)點(diǎn)(除頂點(diǎn)和終點(diǎn)外)相連的被選的邊只能是偶數(shù)條,而起點(diǎn)終點(diǎn)則必須是奇數(shù)條,只是所選的邊可以形成一條路的必要充分條件,那這樣就可以對每個(gè)點(diǎn)

5、都可列出一個(gè)方程了。解出模線性方程組就可以找到一組可行解了,但是最優(yōu)解好像要枚舉所有的解。此題的時(shí)間復(fù)雜度為 O(B4),(B 為邊數(shù))但多數(shù)情況下達(dá)不到。能夠用如下算法構(gòu)造出可行解,但并不知如何求最優(yōu)解。解奇偶方程組:1.已知了起點(diǎn),枚舉一個(gè)終點(diǎn);2.設(shè)每條邊經(jīng)過的次數(shù)依次為 ai(一共有 2N(N+1)條邊),則可以根據(jù)點(diǎn)的度數(shù)(除了起點(diǎn)、終點(diǎn)的任意點(diǎn) i, i 的度數(shù)為偶數(shù))列出 (N+1)22 個(gè)奇偶方程(若干未知數(shù)之和的為奇或?yàn)榕嫉姆匠蹋└鶕?jù)每個(gè)格子的初狀態(tài)和末狀態(tài)類似的列出 N 2(初末狀態(tài)相同則相鄰 4 邊之和為偶,否則為奇),一共有 2N 2+2N 個(gè)未知數(shù),2N 2+2N1

6、個(gè)方程,求出這個(gè)方程的任意一組解就可相應(yīng)的構(gòu)造出案(構(gòu)造方法極其簡單,這里不再羅嗦,但有一點(diǎn)值得注意的是:求方程組時(shí)可設(shè)所有的未知數(shù)都等于 0 或 1)。我連構(gòu)造可行解的方法都不會(huì)。聽說能用解模線性方程組做,是不是這樣的:假設(shè)一個(gè)單元格 I,如果它的顏色原來都是黑的,則 Ci=1;否則為 Ci=0。單元格的上、下、左、右 4 邊經(jīng)過的次數(shù)分別為 x1,x2,x3,x4。則可以得到以下這個(gè)方程:x1 + x2 + x3 + x4 abs(Ci-Ci)。對于其他的方格,還可以列出同樣的方程。因此就了一個(gè)模線性方程組。但我覺得這個(gè)方法是有問題的,就是說,可能求出了一組符合條件的 x,但是根據(jù)這些x 卻無法得到一個(gè)符合條件的解。假如用模線性方程組解出了這樣的解,該如何產(chǎn)生可行解呢?如圖 0072-1,紅線為解模線性方程組解出的需要經(jīng)過的路徑。圖 72-1以每條邊被經(jīng)過的次數(shù)為未知數(shù)構(gòu)造方程組。解模方程組,若方程組無解則問題無解;否則驗(yàn)證一組解,轉(zhuǎn)化為路徑判定問題。考慮度數(shù)為奇數(shù)的點(diǎn)的個(gè)數(shù)。要

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論