彩色項(xiàng)鏈解題報(bào)告

1、彩色項(xiàng)鏈解題報(bào)告上海市復(fù)旦附中 張寧題目描述程序文件：necklace.cpp/necklace.c/necklace.pas輸入/輸出文件：necklace.in/necklace.out【問題描述】一條項(xiàng)鏈由N個(gè)珠子連接而成，編號(hào)依次為0, 1, 2, , N-1。每個(gè)珠子的顏色用09之間的一位數(shù)字來表示（因此，可用的顏色一共有10種）。一條長(zhǎng)度為4的項(xiàng)鏈如下圖所示：（圓圈中的數(shù)字表示顏色，圓圈旁邊的數(shù)字為珠子的編號(hào)）圖1 一條長(zhǎng)度為4的項(xiàng)鏈需要注意的是，如圖1所示，編號(hào)為0, 1, 2, , N-1的珠子大小是依次遞增的，設(shè)編號(hào)為i的珠子的顏色值為ai，則數(shù)字序列a0a1an-1可以唯一

2、的表示一種項(xiàng)鏈。例如，圖1所示的項(xiàng)鏈表示為“1337”?，F(xiàn)在有一臺(tái)自動(dòng)生產(chǎn)項(xiàng)鏈的機(jī)器，它的結(jié)構(gòu)和工作方式如下所述：機(jī)器的核心控制部件主要包括：一個(gè)CPU、一個(gè)整數(shù)寄存器START、和存儲(chǔ)器S。機(jī)器內(nèi)部固化有一段程序，由CPU解釋執(zhí)行。該程序的輸入是長(zhǎng)度為N的十進(jìn)制數(shù)字序列A，輸出是另一個(gè)長(zhǎng)度為N的十進(jìn)制數(shù)字序列B。每次執(zhí)行程序前將S初始化為輸入序列A；程序結(jié)束后把S作為輸出串B。START初始化為0。程序包含M條指令，順序編號(hào)為1M。指令共有5種，以下是指令的格式和功能：（尖括號(hào)表示指令參數(shù)，都是整數(shù)）編號(hào)功能格式說明1設(shè)置寄存器SETSTART 設(shè)置START的值：從S的第a位開始取連續(xù)b位

3、得到的十進(jìn)制整數(shù)（可能大于N-1）。0=a=N-1，1=b=min(8, N)2循環(huán)移位SHIFT 把S從第START位開始的連續(xù)L 位，循環(huán)移位|x|位。x0時(shí)右移，x0時(shí)左移。2=L=min(10, N)，1=|x|=L-13乘法MUL 把S從第START位開始的連續(xù)L位當(dāng)做原始串（L位十進(jìn)制整數(shù)），將其乘以x以后保留結(jié)果的最低L位，替換原始串。1=x=9，1=L=min(10, N)4條件ONDIGIT 如果S的第x位等于y，則跳轉(zhuǎn)到第z條指令。0=x=N-1，0=y=9，1=z=M。z大于當(dāng)前指令序號(hào), 即不會(huì)往回跳轉(zhuǎn)。5終止END僅作為最后一條語句出現(xiàn)，程序終止。由于項(xiàng)鏈?zhǔn)黔h(huán)型的，因

4、此第i位和第i+kN位（k為整數(shù)）代表數(shù)字序列的同一位置。例如當(dāng)N=4時(shí)，第6位和第2位是等價(jià)的。下面是一個(gè)程序的例子：MUL 3 2SETSTART 2 1ONDIGIT 0 4 1SHIFT 3 2END機(jī)器啟動(dòng)的時(shí)候，輸入一個(gè)數(shù)字串S0，執(zhí)行程序得到一個(gè)新的數(shù)字序列S1并生產(chǎn)出S1代表的項(xiàng)鏈來，以后機(jī)器每生產(chǎn)出一條新項(xiàng)鏈Sn，就把Sn對(duì)應(yīng)的數(shù)字序列作為輸入重新執(zhí)行一遍程序，得到一個(gè)新的數(shù)字序列Sn+1并生產(chǎn)出新的項(xiàng)鏈。由于長(zhǎng)度為N的項(xiàng)鏈種類數(shù)目是有限的（至多10N種不同的項(xiàng)鏈），因此如果讓機(jī)器一直工作下去，某些種類的項(xiàng)鏈會(huì)被生產(chǎn)出無限多條。編程計(jì)算出這些將被無限生產(chǎn)出的項(xiàng)鏈有多少種。在本

5、題中，可以被生產(chǎn)出來的項(xiàng)鏈種類總數(shù)保證不超過106?！据斎胛募枯斎胛募ecklace.in的第1行包含兩個(gè)整數(shù)N和M (1=N=100,000，2=M=30)，第2行包含一個(gè)有N個(gè)數(shù)字的串S0。第3行到第M+2行為一段程序，每行一條指令，程序保證無錯(cuò)，行末和行首均沒有空格?！据敵鑫募枯敵鑫募ecklace.out僅有一行，包含一個(gè)整數(shù)，是將被無限生產(chǎn)出來的項(xiàng)鏈種類數(shù)目?！据斎胼敵鰳永縩ecklace.innecklace.out4 51234MUL 3 2SETSTART 2 1ONDIGIT 0 4 1SHIFT 3 2END8【樣例說明】該樣例對(duì)應(yīng)于題目描述中給出的示例程序。前2

6、9次生產(chǎn)出來的項(xiàng)鏈?zhǔn)牵?426 4886 6796 8356 0676 4136 6286 6526 4306 0866 6712 2432 4882 2796 8556 0716 6412 2822 4562 2192 2786 6556 0316 6602 0322 4062 2182 4382 2786可以看出，從2786開始機(jī)器陷入了循環(huán)，因此從2786開始的8條項(xiàng)鏈將被無限制的生產(chǎn)出來。解題報(bào)告初看到題目名稱“彩色項(xiàng)鏈”時(shí)，不要誤以為是一道考Plya原理或是考圖論算法的題目，經(jīng)過快速地閱讀題目，可以初步斷定這是一道大數(shù)據(jù)量的統(tǒng)計(jì)問題，需要統(tǒng)計(jì)出總共有多少項(xiàng)鏈將被無限制的生產(chǎn)出來。當(dāng)仔

7、細(xì)閱讀題目的細(xì)節(jié)后，來分析一下樣例中的前幾條項(xiàng)鏈的生產(chǎn)過程：步驟指令編號(hào)程序指令項(xiàng)鏈原形START項(xiàng)鏈新形第一條項(xiàng)鏈11MUL 3 212340246422SETSTART 2 124646(2)246433ONDIGIT 0 4 124646(2)246444SHIFT 3 -224646(2)4426第二條項(xiàng)鏈11MUL 3 244260884622SETSTART 2 188464(0)884633ONDIGIT 0 4 188464(0)884644SHIFT 3 288464(0)4886第三條項(xiàng)鏈11MUL 3 248860976622SETSTART 2 197666(2)976

8、633ONDIGIT 0 4 197666(2)976644SHIFT 3 297666(2)6796進(jìn)一步分析題意，可以得知我們的工作是模擬一臺(tái)機(jī)器的生產(chǎn)，而機(jī)器的生產(chǎn)是與前一次的產(chǎn)品相關(guān)的，而且對(duì)項(xiàng)鏈片斷的改造涉及到局部位移以及局部乘法兩種操作。觀察題目中所給出的限制條件，對(duì)于SHIFT操作2=L=min(10, N)，1=|x|=L-1，而對(duì)于MUL操作1=x=9，1=L460920，這樣的空間復(fù)雜度是不能承受。因此對(duì)于大一些的數(shù)據(jù)就不能通過。而且隨著項(xiàng)鏈的總數(shù)增多，判斷項(xiàng)鏈?zhǔn)欠裣嗤臅r(shí)間復(fù)雜度也越來越高，比較項(xiàng)鏈?zhǔn)欠裣嗤目倳r(shí)間復(fù)雜度為O(N*T2)，同樣也是不能承受的。因此算法需要改

9、進(jìn)。算法2首先為了改善空間問題，我們不能將所有項(xiàng)鏈都一一紀(jì)錄，那么我們是否有方法能夠不紀(jì)錄之前生產(chǎn)的項(xiàng)鏈直接判斷是否生產(chǎn)出相同的項(xiàng)鏈呢？這時(shí)，我們可以考慮采用Floyd判圈算法，用在本題上，就可以這樣考慮：我們有兩條生產(chǎn)項(xiàng)鏈的流水線，一條流水線生產(chǎn)的速度是另一條的兩倍，那么如果有某一時(shí)刻兩條流水線生產(chǎn)出了相同的項(xiàng)鏈，則我們就可以知道兩條流水線已進(jìn)入或正進(jìn)入循環(huán)的生產(chǎn)。那是否對(duì)任何情況都有上述結(jié)果呢？證明是非常容易的。假設(shè)第一條流水線速度慢，第二條流水線速度快。假設(shè)在陷入循環(huán)之前總共生產(chǎn)了X條項(xiàng)鏈，而將有Y條項(xiàng)鏈將被無限制的生產(chǎn)出來。則我們顯然可以找到正整數(shù)Z，使得Y|X+Z，這里1=Z=Y，顯

10、然當(dāng)?shù)谝粭l流水線生產(chǎn)第X+Z條項(xiàng)鏈時(shí)，第二條流水線生產(chǎn)第2X+2Z條項(xiàng)鏈，比第一條流水線多生產(chǎn)X+Z條，由于Y|X+Z，因此兩條流水線生產(chǎn)的項(xiàng)鏈相同。這樣我們已經(jīng)能夠確定有一條項(xiàng)鏈將被無限制的生產(chǎn)出來，則我們只需要以這條項(xiàng)鏈為標(biāo)準(zhǔn)，經(jīng)過Y次生產(chǎn)將又生產(chǎn)出了相同的項(xiàng)鏈，則我們就可以確定將被無限制生產(chǎn)出來的項(xiàng)鏈數(shù)為Y。算法2的空間復(fù)雜度為O(2N)，顯然已經(jīng)不存在空間上的問題了。雖然我們?cè)谀M生產(chǎn)上多付出了一定的代價(jià)，算法1只需模擬生產(chǎn)X+Y+1條項(xiàng)鏈，而現(xiàn)在需要模擬3(X+Z)+Y=3X+4Y條項(xiàng)鏈，最壞情況下模擬量為算法1的四倍，但是算法2中比較項(xiàng)鏈?zhǔn)欠裣嗤拇螖?shù)卻大大減少，我們降低了時(shí)間復(fù)雜

11、度的階，算法2中比較項(xiàng)鏈?zhǔn)欠裣嗤臅r(shí)間復(fù)雜度為O(N*(X+Z+Y)=O(N*(T+Z)1 then/若乘1則不需要做改動(dòng) begin u:=0;/進(jìn)位標(biāo)志 for i:=l-1 downto 0 do/分別計(jì)算每一位 begin j:=(i+start) mod n;/計(jì)算當(dāng)前珠子的編號(hào) u:=u+productid.beadj*x;/計(jì)算每一位的乘積 inc(productid.hash,(u mod 10-productid.beadj)*(j+1);/修改hash函數(shù)值 productid.beadj:=u mod 10;/改造第j顆珠子的顏色 u:=u div 10;/進(jìn)位 end;

12、 end; inc(cmd_count);/設(shè)置為下一條語句 end; procedure ondigit(x,y,z:longint); /執(zhí)行ONDIGIT操作 begin if productid.beadx=y then/符合條件則轉(zhuǎn)向第z條語句 cmd_count:=z else/否則執(zhí)行下一條語句 inc(cmd_count); end; begin/模擬的過程 cmd_count:=1;/設(shè)置為第一條語句 start:=0;/START清零 while cmd_countm do/若程序?yàn)榻Y(jié)束 with progcmd_count do/開域語句 case cmdtype of/

13、分情況執(zhí)行操作 1:setstart(data1,data2); 2:shift(data1,data2); 3:mul(data1,data2); 4:ondigit(data1,data2,data3); end; end; function compare(id1,id2:integer):boolean;/比較兩條項(xiàng)鏈?zhǔn)欠裣嗤?var i:longint; begin if productid1.hashproductid2.hash then/先比較兩者的hash函數(shù) begin compare:=false;/兩項(xiàng)鏈不同 exit; end; for i:=0 to n-1 do/

14、逐一比較每顆珠子的顏色 if productid1.beadiproductid2.beadi then begin compare:=false;/兩項(xiàng)鏈不同 exit; end; compare:=true;/兩項(xiàng)鏈相同 end; begin/算法主過程 s:=0; repeat/兩條進(jìn)度不同的流水線 inc(s);/生產(chǎn)次數(shù)加1 produce(1);/第一條流水線生產(chǎn)一次 produce(2);/第二條流水線 produce(2);/生產(chǎn)兩次 until compare(1,2);/若某次兩流水線生產(chǎn)出的項(xiàng)鏈相同 ans:=0;/循環(huán)節(jié)長(zhǎng)度清零 repeat produce(1);/第一條流水線生產(chǎn)一次 inc(ans);/循環(huán)節(jié)長(zhǎng)度加1 if s mod ans0 then continue;/若不可能是循環(huán)節(jié)則無需比較 until compare(1,2);/以第二條流水線生產(chǎn)的最后一條項(xiàng)鏈為標(biāo)志/比較是否已陷入循環(huán) end;procedur