prob "ac",1prob "ac",1prob "ac",0prob "ac",0prob "ac",0prob "ac",1</SCRIPT>
  </TR></TBODY></TABLE>
<SCRIPT>detail 1002,"全排序問題"</SCRIPT>
　　放心大膽地做吧，不會TLE:)
<SCRIPT>detail 1004,"防御導彈"</SCRIPT>
 
　　第一問即經典的最長不上升子序列問題，可以用一般的DP算法，也可以用高效算法，但這個題的數據規模好像不需要。<BR>　　高效算法是這樣的：用a[x]表示原序列中第x個元素，b[x]表示長度為x的不上升子序列的最后一個元素的最大值，b數組初值為0。容易看出，這個數組是遞減的（當然可能有相鄰兩個元素相等）。當處理a[x]時，用二分法查找它可以連接到長度最大為多少的不上升子序列后（即與部分b[x]比較）。假設可以連到長度最大為y的不上升子序列后，則b[y+1]:=max{b[y+1],a[x]}。最后，b數組被賦值的元素最大下標就是第一問的答案。由于利用了二分查找，這種算法的復雜度為O(nlogn)，優于一般的O(n<SUP>2</SUP>)。<BR>　　第二問用貪心法即可。每顆導彈來襲時，使用能攔截這顆導彈的防御系統中上一次攔截導彈高度最低的那一套來攔截。若不存在符合這一條件的系統，則使用一套新系統。<BR>　　<FONT 
color=red><B>注意：</B></FONT>第二問不可以用每次刪除最長不上升序列的方法做。比如，當來襲的導彈共有4顆，高度依次為2 4 1 
3的時候，如果不巧找到的最長不上升序列為4 1，那么剩下的2和3就只能另外啟用兩套系統了。這顯然不是最優解。
<SCRIPT>detail 1005,"母牛生小牛"</SCRIPT>
 　　用a[i]表示第i年牛的總數，則a[i]=a[i-1]+a[i-3]，即3年前所有的牛所生的小牛加上上一年所有的牛。
<SCRIPT>detail 1006,"敲七"</SCRIPT>
 　　挨個檢查即可。
<SCRIPT>detail 1009,"蛇行矩陣"</SCRIPT>
 　　把三角形的下角拖到右面去，便可以編出連數組都不用的程序了:)
<SCRIPT>detail 1010,"數素數"</SCRIPT>
 
　　用篩法求素數即可。關鍵是怎么把求得的素數都保存下來。可以用1個字節保存8個二進制位，即8個數是否為素數。再用count[i]表示i*8以內素數的個數（前綴表示法）。求m到n之間素數個數時，除了用兩個count值相減外（前綴表示法的常用技巧），還要注意處理一下m和n附近的素數。
<SCRIPT>detail 1011,"階乘末尾非零數求和"</SCRIPT>
 　　在乘的過程中，我們只需保留最后一位非零數。這位數在n&gt;1時為偶數。當要乘的數中含有因數5時，我們可以把所有的因數5都當作8來乘，因為： 
<BLOCKQUOTE>...2*5=...10（舍）或...60，最后一位非零數為6。而恰好2*8=16，末位為6。<BR>...4*5=...70（舍）或...20，最后一位非零數為2。而恰好4*8=32，末位為2。<BR>...6*5=...30（舍）或...80，最后一位非零數為8。而恰好6*8=48，末位為8。<BR>...8*5=...90（舍）或...40，最后一位非零數為4。而恰好8*8=64，末位為4。 
</BLOCKQUOTE>
<SCRIPT>detail 1012,"約瑟夫問題"</SCRIPT>
　　用數組模擬鏈表即可。
<SCRIPT>detail 1013,"高精度整數去位取最小問題"</SCRIPT>
 
　　每一個保留的數字都從可取的范圍中取最小的一位即可。用a[i]表示第i個保留的數字在原數中的位置，設a[0]=0，則a[i]的范圍為a[i-1]+1~n-m+i。
<SCRIPT>detail 1014,"階乘結果末尾有多少零？"</SCRIPT>
 　　借用化學術語說，“一個2跟一個5反應生成一個0，因為2過量，所以照5算”。n!末尾零的個數就是1~n這n個數中因數5的個數，即n div 5+n div 
5<SUP>2</SUP>+n div 5<SUP>3</SUP>...直到某項減少至0為止。
<SCRIPT>detail 1016,"請求N!左邊第二位的數字"</SCRIPT>
 　　用實數乘，超過100就除以10，最后取個位即可。
<SCRIPT>detail 1017,"石子歸并"</SCRIPT>
 
　　開一個最小下標為0，最大下標為最大總質量的一半(maxw)的布爾數組b，初始時僅b[0]為true。依次讀入每一個石子的質量。設當前石子的質量為m，則對于原來的任一個值為true的b[i](0&lt;=i&lt;=maxw-m)，令b[i+m]為true。處理完每個石子后，設值為true的b值中最大下標為x，則x就是把石子按質量盡可能平均地分為兩堆后較輕的那一堆的質量。
<SCRIPT>detail 1018,"編制一個乘法運算的程序"</SCRIPT>
 　　垃圾題。不要按照一般的乘法豎式輸出，而要觀察樣例程序的輸出，然后照葫蘆畫瓢……SPOJ上有一道Simple 
Arithmetics，比這個題好得多，推薦做一下。
<SCRIPT>detail 1021,"麻將游戲"</SCRIPT>
 
　　說是麻將游戲，其實就是連連看嘛。好像有不少人看不懂題意，可以Google一個連連看玩一下。<BR>　　這個題的解法就是簡單BFS。從起點出發，每次擴展就是沿上下左右四個方向闖下去，直到碰到一張牌或邊界為止。這里的“邊界”應是原棋盤再往外的一圈，因為連線可以超出棋盤。如果碰到的牌正好是終點，那么BFS成功。<BR>　　另外還要注意，輸出的應是路徑上線段的條數，而不是拐的彎數。
<SCRIPT>detail 1022,"數制轉換"</SCRIPT>
 
　　初學者的基礎題，我就不講算法了。要說的是題目敘述的第一行不應是“A$='mp'”，而應是“A$='m&lt;n&gt;p'”，&lt;n&gt;被當成HTML標簽吃掉了。看一下樣例你就不會迷茫了:)
<SCRIPT>detail 1024,"特殊三角形"</SCRIPT>
 　　這個題是TJU上一道極垃圾的題。雖然是Special Judge，但實際上能AC的只有按升序排列在最前面的那一個三角形。這樣看來，連樣例輸出都是錯的:(
<SCRIPT>detail 1025,"N*N的棋盤"</SCRIPT>
 　　深搜。為了加快速度，可以不用布爾數組記錄一個數是否用過，而用數組模擬的鏈表。
<SCRIPT>detail 1026,"整除65的多項式"</SCRIPT>
 　　注意到k,a,x的范圍其實都只是0~64，于是枚舉即可。
<SCRIPT>detail 1027,"洗牌問題"</SCRIPT>
 
<UL>
  <LI><FONT 
  color=blue><B>Maigo的原始算法：</B></FONT><BR>　　我們把每個數逛來逛去最后又回家的過程叫做一個<B>循環</B>，循環中經過的位置個數叫做循環的<B>長度</B>。如N=4時，有兩個循環：1-2-4-8-7-5-1，長度為6；3-6-3，長度為2。答案就是所有循環長度的最小公倍數。顯然算法時空復雜度均為O(n)（因為需要記錄一個數是否已被某個循環經過）。<BR>
  <LI><FONT 
  color=blue><B>Wasltone的高效算法：</B></FONT><BR>　　1所在的循環長度就是答案。時間復雜度小于O(n)，空間復雜度為O(1)，編程復雜度也遠低于原始算法。這個算法是建立在如下結論之上的：“1所在的循環長度是其它任一循環長度的倍數”，或者表述為“1回家時，其它任一數字也一定回了家”。Wasltone本人沒有給出這個結論的證明。 

  <LI><FONT 
  color=blue><B>Ahyangyi給出的證明：</B></FONT><BR>　　題目中的移動規則，其實就是每次把在第x個位置的數移動到位置x*2 
  mod (2*n+1)。這個式子是十分巧妙的，請用心領悟。由這個式子可以得出任一數字x在p步之后的位置：x*2<SUP>p</SUP> mod 
  (2*n+1)。假設1經過p步回了家，那么可得1*2<SUP>p</SUP> mod 
  (2*n+1)=1。由此可得對任一數字x，均有x*2<SUP>p</SUP> mod (2*n+1)=x，即1回家時任一數字都回了家。 </LI></UL>
<SCRIPT>detail 1029,"埃及分數"</SCRIPT>
　　本題若用BFS，則每個結點可擴展的子結點數會巨大，空間復雜度無法承受。因此采用DFS-ID，即先假設解的深度（單位分數的個數）為1，進行DFS，若不成功，再假設解的深度為2，DFS……直到找到解為止。<BR>　　DFS-ID解決了空間問題，但還有一個問題就是每個結點擴展子結點的范圍，因為單位分數的分母沒有限制，必須人為找一個限制條件。 

<UL>
  <LI>對于<B>非葉子結點</B>：當前待確定分母的最小值就是max{上一個分母加1，當前剩余分數的倒數的整數部分加1}。第2項之所以加1，是因為當前分母必須小于以后的分母。它的最大值則是min{當前剩余分數除以尚未確定的分數個數的商的倒數的整數部分，當前最優解的最后一個分母減1}。前一項可以這樣理解：如果當前待確定分母大于這一項，那么以后的分母都會大于這一項，當前待確定的及以后的分數加起來肯定小于當前剩余分數。后一項則是顯然的：如果當前分母都大于等于當前最優解的最大分母了，那么當前結點一定不會擴展出更優解。 

  <LI>對于<B>葉子結點</B>：這里就無需討論什么范圍了。若當前剩余分數的分子恰好為1，且分母大于上一個分數的分母，且分母小于最優解的最大分母，則更新解，否則退出。</LI></UL>　　上述過程中，為計算準確及在葉子結點處獲得剩余分數的分母方便，剩余分數不要采用實數類型計算，而是設兩個整型變量分別表示分子和分母。
<P>　　<B>注：</B>本題的題目描述不甚清楚。在多解的情況下，題目只說要分數個數最少，分數個數相同的情況下最大的分母最小。但是，若最大的分母還相同怎么辦呢？比如8/27，是分解成1/4+1/36+1/54，還是分解成1/6+1/9+1/54？對此，我的程序輸出的是找到的第一個解4 
36 54，亦即認為在最大的分母還相同的情況下，取字典順序最小的一個。這可能不是出題者的原意，但用這種標準，我AC了。
<SCRIPT>detail 1030,"字符串的序號"</SCRIPT>
 
　　假設我們要求kensta的序號，那么我們只要求出以a開頭的、以e開頭的、以ka開頭的……字符串各有多少，累加就行了。剩下的任務就是已知一些字符，求它們可以組成多少個不同的字符串。這是一個重排列問題。假設共有n種字符，其中字符c<SUB>i</SUB>有a<SUB>i</SUB>個，那么求這些字符可以組成的不同字符串數的公式為<IMG 
src="vol1.files/1030_1.gif" align=absMiddle>。
<SCRIPT>detail 1031,"貓和老鼠"</SCRIPT>
 　　寬搜即可，因為總狀態數只有(10*10*4)<SUP>2</SUP>=160000。
<SCRIPT>detail 1032,"等式問題"</SCRIPT>
 　　先用預處理算出符號的所有填法對應的結果，然后問哪個輸出哪個就行。
<SCRIPT>detail 1033,"線型網絡"</SCRIPT>
 
　　此題的確定算法，不是TLE就是MLE。這時，隨機算法就大顯神通了。<BR>　　首先隨機生成一條路徑，然后對其進行優化。用dist[a,b]表示路徑上第a個點與第b個點之間的距離。假設存在某一對a,b使得dist[a-1,a]+dist[b,b+1]&gt;dist[a-1,b]+dist[a,b+1]（規定dist[0,*]=dist[*,N+1]=0），那么把第a個點至第b個點這一段路反向，得到的新路徑會更短。不斷把某一段路反向直至無法再優化為止。<BR>　　這樣做并不能保證得到的解最優，因為有時“退一步海闊天空”，而這種本質是貪心的隨機算法卻“退”不下這一步。然而，這種情況畢竟是少見的。因為N的范圍并不大，所以把上一段所述的過程重復一定次數（我的程序中為99次），就基本可以保證得到最優解了。
<SCRIPT>detail 1034,"四塔問題"</SCRIPT>
 　　我們把利用三個、四個柱子移動i個盤子所需的移動次數分別記為f[i]、g[i]。為了推出g[i]的表達式，把用四個柱子移動i個盤子的過程分為三步：
<OL>
  <LI>把上面j個盤子移到某一工作柱上。這一步可以用四個柱子，所需移動次數為g[j]。
  <LI>把下面i-j個盤子移到目的柱上。因為上一步占用的工作柱在此步中不能使用，因此此步所需移動次數為f[i-j]。
  <LI>再把工作柱上的j個盤子移到目的柱上，所需移動次數為g[j]。</LI></OL>因此得到遞推式：
<BLOCKQUOTE>g[1]=1<BR>g[i]=min{g[j]*2+f[i-j]}(1&lt;=j&lt;i,i&gt;1)</BLOCKQUOTE>　　然而僅僅利用這個式子，算法復雜度是O(n<SUP>2</SUP>)的，對于n&lt;=50000的數據范圍，顯然無法承受。因此，我們列出i值較小時的f[i]和g[i]，以期發現某種規律。<BR>
<TABLE cellSpacing=0 width="40%" align=center>
  <TBODY>
  <TR align=middle>
    <TH>i
    <TD>1
    <TD>2
    <TD>3
    <TD>4
    <TD>5
    <TD>6
    <TD>7
    <TD>8
    <TD>9
    <TD>10
    <TD>11 
  <TR align=middle>
    <TH>f[i]
    <TD>1
    <TD>3
    <TD>7
    <TD>15
    <TD>31
    <TD>63
    <TD>127
    <TD>255
    <TD>511
    <TD>1023
    <TD>2047 
  <TR align=middle>
    <TH>g[i]
    <TD>1
    <TD>3
    <TD>5