信息學(xué)集訓(xùn)隊(duì)作業(yè)

1、三臂起重機(jī)（TRO）三臂起重機(jī)用來為貨車裝載貨物。假設(shè)車廂已經(jīng)按照1，2，3，編號(hào)，每一節(jié)車廂上僅可以放入一集裝箱的貨物。三臂起重機(jī)的工作方法很簡單。它每次可以從倉庫中吊出三箱貨物，把它們放到編號(hào)為（i，i+p，i+p+q），或者編號(hào)為（i，i+q，i+p+q）的三節(jié)車廂中。p,q已知，且p,q1。現(xiàn)在我們的目的是把編號(hào)為1，2，n的車廂全部裝滿貨物，且已知貨車恰有n+p+q節(jié)車廂。為了完成這個(gè)任務(wù)，我們必須為起重機(jī)安排一個(gè)裝運(yùn)程序，程序中包含若干行，每一行含有三個(gè)數(shù)字x、y、z，滿足1xyzn+p+q,表示此次吊起的三件貨物分別放到了編號(hào)為x、y、z的車廂中。你的程序輸出正確當(dāng)且僅當(dāng)按照輸出

2、安排的吊運(yùn)方法可以把編號(hào)為1，2，n的n節(jié)車廂全部裝滿，且每一節(jié)車廂至多裝載了一箱貨物。輸入輸入文件TRO.IN僅包含一行，這一行有三個(gè)數(shù)字p，q，n，分別是三臂起重機(jī)運(yùn)貨的兩個(gè)參數(shù)以及需要裝貨的車廂數(shù)。1n300000,2p+q60000。輸出輸出文件TRO.OUT包含若干行，第一行為一個(gè)數(shù)字m，表示三臂起重機(jī)的裝箱次數(shù)。其后有m行，每一行包含三個(gè)數(shù)字x、y、z，即為每次吊起的三間貨物裝入的車廂編號(hào)。容易知道，yx+p，x+q，z=x+p+q。輸入樣例2 3 10輸出樣例41 3 62 4 75 8 109 11 14TRO解題報(bào)告問題描述這是Poi2000 stage 2的一道題目。題目的

3、大意是給出了三個(gè)數(shù)p、q、n，要構(gòu)造若干個(gè)三元組，要符合以下四個(gè)要求：（1）三元組必須具備形式（i，i+p，i+p+q）（i，i+q，i+p+q）之一。（2）所有三元組中的元素不得超過n+p+q。（3）1，2，n+p+q這n+p+q個(gè)數(shù)每個(gè)至多出現(xiàn)一次。（4）這些三元組必須涵蓋1，2，n這n個(gè)自然數(shù)。n=300000，p+q=60000。算法分析初看此題，感覺數(shù)學(xué)味頗濃。題目雖然以“起重機(jī)”“裝載”作為背景，但是剝?nèi)ミ@層偽裝后，我們就可以用熟悉的數(shù)學(xué)語言來加以描述了。由于n，p+q的范圍比較大，我們想到用效率較高、復(fù)雜度低的構(gòu)造法來解決。假設(shè)我們已經(jīng)構(gòu)造了若干個(gè)符合條件的三元組，如果1，2，n

4、都已經(jīng)出現(xiàn)過則終止，否則下一步我們?nèi)〕鑫闯霈F(xiàn)過的最小的自然數(shù)x，顯然xn。由于前面所有的三元組的第一個(gè)數(shù)都小于x（由構(gòu)造方法易知），所以這些三元組中的元素都不超過x-1+p+q，那么x+p+q肯定沒有出現(xiàn)過。我們的問題轉(zhuǎn)化成為決定（x，?，x+p+q）中的？。一個(gè)最簡單的想法是：首先嘗試x+p，若沒有出現(xiàn)過則取？=x+p，否則??？=x+q。這樣做的疑點(diǎn)在于：是否會(huì)出現(xiàn)x+p、x+q都出現(xiàn)過無法選擇的情形呢？看下面這個(gè)例子：p=3，q=2首先取沒有出現(xiàn)過的最小自然數(shù)1，構(gòu)造出三元組（1，4，6），接下來又構(gòu)造出（2，5，7），這是沒有出現(xiàn)過的最小數(shù)為3，但是3+3=6，3+2=5均已出現(xiàn)在前面三

5、元組中，無法選擇了。這樣構(gòu)造宣告失敗。換一個(gè)角度。P與q的地位是對(duì)稱的，我們不妨假設(shè)p=q，則交換它們，不影響結(jié)果。在上面的例子中，我們會(huì)取p=2，q=3。則構(gòu)造的過程為（1，3，6），（2，4，7），（5，8，10），（9，11，14）嘗試了很多次，我們發(fā)現(xiàn)：這樣做就沒有反例了。于是猜想：當(dāng)p=q時(shí)，上面的構(gòu)造方法是正確的。下面我們來證明這一點(diǎn)。假設(shè)已經(jīng)構(gòu)造了s個(gè)三元組，分別為（），（，。我們?nèi)∵@些三元組中沒有出現(xiàn)過的最小元素r，證明r+p，r+q不可能同時(shí)被使用過。采用反證法。若它們均出現(xiàn)過，則有如下兩種情況：r+q=+p（1=i=p，則p-q=0，r=+p-q=，由于每次取的都是未出現(xiàn)過的最小自然數(shù)，矛盾！r+q=+p+q(1=i=s)，推出r=+p，若=+p，則r=已經(jīng)出現(xiàn)過，矛盾。故=+q，由我們選取的規(guī)則可知，+p已經(jīng)出現(xiàn)過（否則會(huì)選擇+p而不是+q）,這又與r=+p沒有出現(xiàn)過矛盾。綜上，我們可知，r+q一定沒有出現(xiàn)過，即不會(huì)有兩種選擇都違反規(guī)則的情形出現(xiàn)。至此，算法得證。小結(jié)本題采用的構(gòu)造法在近年來的競賽中并不多見，它的優(yōu)點(diǎn)是