自創(chuàng)試題解題報告-lzx

1、寒假作業(yè)自創(chuàng)試題解題報告K2002_12 李子星【第一題】金鏈【第二題】公路建設(shè)【第三題】迷宮【第四題】Number【第一題】金鏈將這道題的題意看清，就知道題目的意思其實就是要我們求：長度為n的鏈條怎么分段，使得：1. 分出的各個子鏈的長度可以湊成1到n之間的每一個整數(shù)，這樣就可以保證店主在第i天擁有i個金環(huán)，即每一天店主都不會多收或少收房錢2. 分出的子鏈中，長度為1的子鏈的段數(shù)>=子鏈的總段數(shù) div 23. 分出的子鏈盡量的少明確我們的目標(biāo)后，就要向目標(biāo)進(jìn)攻：我們采用構(gòu)造法。構(gòu)造“關(guān)卡數(shù)”當(dāng)n<8的時候，我們都可以用枚舉知道：只要取出一個金環(huán)就可以了。n>8時，看下面：

2、如果我們只取出2個金環(huán)，那么我們最多只能得到5段子鏈假設(shè)長度不限的話，我們使另外的三段子鏈長度分別為；3, 6, 12，那么我們就可以得到123之間的所有整數(shù)：1 2 3 4 5 6 7 8 91011121314151617181920212223111313113616116361361136121121112312131211312612161211612361213612113612好了，光知道這些還沒有用，我們必須要從中找到規(guī)律：2個1可以湊成12，3就不行了，于是我們最多只能增加一段長度為3的子鏈多加一個3可以將“最大可以湊成的數(shù)”從2上升到5，此時我們?nèi)暨€想提升“最大可以湊成的數(shù)

3、”，最多只能增加一段長度為6的子鏈直到我們增加了一段長度為12的子鏈，我們就再也不能提升“最大可以湊成的數(shù)”了（因為我們已經(jīng)增加了3段了）。再看，我們用的子鏈的總長度也只有23，如果我們的金鏈總長還沒有23是不是也只要取出2個金環(huán)就可以了呢？答案是肯定的。比如說金鏈總長為22的時候，我們只要將最后加進(jìn)來的子鏈（長為12的那一段）的長度減去1，就可以了。其實，對于長度大于等于8且小于等于23的金鏈，取出兩個金環(huán)都可以完成任務(wù)。3個金環(huán)可以達(dá)到的“最大可以湊成的數(shù)”等于63。像8，23，63這樣的小于等于它和大于它至少要取出的金環(huán)數(shù)不同的數(shù)，就叫做“關(guān)卡數(shù)”。那么，關(guān)卡數(shù)要怎么求呢？我們又來看取出

4、2個金環(huán)的情況：1，1可以湊成12，這時加一段長度為3的子鏈，1，1，3可以湊成15，這時加一段長度為6的子鏈1，1，3，6可以湊成111，這時加一段長度為12的子鏈.也就是說取出x個金環(huán)的情況一定是：先加一段x+1，在加一段x+(x+1)，在加一段x+(x+1)+(x+(x+1).直到加了x+1次所以取出x個金環(huán)可以達(dá)到的“最大可以湊成的數(shù)”就等于 (x+1)*2(x+1)-1，所以x個金環(huán)的“關(guān)卡數(shù)”就是(x+1)*2(x+1)-1，用Gatex= (x+1)*2(x+1)-1“關(guān)卡數(shù)”出來了，問題的解又是多少呢？不要緊，馬上就出來了。對于長度為n的金鏈，我們只要求出i使得：Gatei&l

5、t;n<=Gatei+1那么，最少要取出的金環(huán)數(shù)就是i。當(dāng)n=1016時，i=46，而Gate47不比1016大很多，因此我們只要求出這47個關(guān)卡數(shù)，然后保存在const里面就可以了，要注意的就是要用comp存?！镜诙}】公路建設(shè)這道題看起來很復(fù)雜，其實就是要求你對一個最小生成樹進(jìn)行動態(tài)維護(hù)。處理的方法如下：讀入一條a到b的邊之后，先不將這一條邊加入圖中，檢查a到b之間是否有路徑相連，>若相連則找到路徑上權(quán)值最大的一條邊e(u,v)>若e(u,v)的權(quán)值比新讀入的這條邊的權(quán)值要小或相等，則去掉新讀入的邊>若e(u,v)的權(quán)值比新讀入的這條邊的權(quán)值要大，則去掉e(u,v)

6、，加入新讀入的邊>若不相連則直接將新讀入的邊這樣，每次讀入一條邊后，仍能使圖保持為最小樹形圖。這個算法的時空復(fù)雜度是多少呢？>時間復(fù)雜度每次讀入一條邊e(a,b)，要檢查a, b之間是否有路徑相連，我們需要一個深搜的過程>如果我們用鏈表的話，深搜的時間復(fù)雜為O(e)，而最小樹形圖中最多只有n-1條邊，所以這個過程為O(n)級的然后我們要去邊與加邊，這都是小于O(n)級的，所以維護(hù)的時間復(fù)雜的是O(n)級的。因為有m要增加，我們總共要維護(hù)m次，所以總的時間復(fù)雜度為O(n*m)級的，這是可以承受的。>空間復(fù)雜度我們采用鏈表，只要存儲邊就可以了，最小樹形圖中最多只有n-1條邊

7、，所以空間復(fù)雜度為O(n)?！镜谌}】迷宮這道題其實跟歐拉回路有關(guān)。因為我們可以傳送，所以我們其實可以忽略圖的連通性的問題。我們要注意下面幾點：1. 我們的目的是殺掉所有的敵人（最多的就是所有的），對于沒有敵人的道路，我們完全沒有必要考慮。2. 對于有敵人的道路，我們最好是一次遍歷，一條路不需要走兩次（我們可以傳送，而傳送的時間一定小于走過去的時間）。3. 我們必須從起點走到終點。于是問題就是：通過“傳送”在頂點之間連最少的邊，構(gòu)造一個歐拉回路。所以：1. 將不是起點和終點的點稱為“中間點”，起點和終點稱為“非中間點”。若要構(gòu)造一條起點出發(fā)，終點結(jié)束的歐拉回路，就一定要使：“非中間點”的度為奇

8、數(shù)，“中間點”的度為偶數(shù)2. 由1可知，對于每一個節(jié)點，我們只需要統(tǒng)計它的度的奇偶性，而不要知道他與其他哪個節(jié)點連了邊，然后統(tǒng)計奇偶性不正常的點的個數(shù)x。而奇偶性不正常的點的個數(shù)一定是偶數(shù)（看證明點擊這里），所以一定可以配成x/2對，所以x/2就是要傳送的次數(shù)3. 對于有敵人的道路，我們都要走且僅走一次，我們只需要知道有敵人的道路的總長就可以了4. 每個敵人都只會也必須被我們殺掉一次，所以我們只要知道迷宮中敵人的總數(shù)乘以TK的結(jié)果，而不要管他們分布在哪里于是，看似復(fù)雜的題就變成簡單的統(tǒng)計題了。時間復(fù)雜度為O(m)，空間只需要存10000個boolean（每個點的奇偶性）就可以了。前面說到，圖中

9、奇偶性不正常的點的個數(shù)一定是偶數(shù)，證明如下：因為所有點的度的總和一定為偶數(shù)，所以奇點的個數(shù)一定是偶數(shù)。奇數(shù)+奇數(shù)=偶數(shù)>當(dāng)這偶數(shù)個奇點有奇數(shù)個是“非中間點”時，奇偶性不正常的點就有：奇數(shù)個偶度的“非中間點”它也是奇偶性不正常的奇數(shù)個奇點為“中間點”，這些點都是奇偶性不正常的偶數(shù)+偶數(shù)=偶數(shù)>當(dāng)這偶數(shù)個奇點有偶數(shù)個是“非中間點”時，奇偶性不正常的點就有：奇數(shù)個偶度的“非中間點”它也是奇偶性不正常的奇數(shù)個奇點為“中間點”，這些點都是奇偶性不正常的所以奇偶性不正常的點總有偶數(shù)個?！镜谒念}】Number這是一道簡單的遞推題。用fi表示i位K進(jìn)制數(shù)的總數(shù)，那么就有：fi=(fi-1+fi-2)*(K-1)怎么解釋這個方程呢？fi也就是i位K進(jìn)制數(shù)的總數(shù)應(yīng)該等于：第i-1位為0與第i-1位不為0的情況的和乘以第i位的情況數(shù)(1.k-1)&g