<SCRIPT>detail 1255,"RAR or ZIP"</SCRIPT>
   
  　　由于給出了排序后方陣的最右一列，我們把這些字母排序（桶排即可）后自然可以得出方陣的最左一列。顯然，方陣每一行的最后一個字母與第一個字母在原文中是相鄰的（如果認為原文中最后一個字母與第一個字母也相鄰的話）。我們自然產生了一種美好的設想：根據第一個字母就可以找到第二個字母，再根據第二個字母找到第三個字母……就這樣按圖索驥，就可以恢復出原文了！<BR>　　對樣例進行試驗，成功。但這樣做沒有問題嗎？有！看totoro這個單詞：<BR>
  <TABLE align=center>
    <TBODY>
    <TR>
      <TD align=middle><FONT 
        color=blue>構造字符串：</FONT><BR>totoro<BR>otorot<BR>toroto<BR>orotot<BR>rototo<BR>ototor 

      <TD align=middle><FONT 
        color=blue>將字符串排序：</FONT><BR>otorot<BR>orotot<BR>ototor<BR>rototo<BR>totoro<BR>toroto 

      <TD><FONT color=blue>壓縮結果：</FONT><BR>S'=ttrooo<BR>p=1 
  </TD></TR></TBODY></TABLE>　　因為第一個字母是第一行末尾的t，所以第二個字母是o。但是，這個o是第四行末尾的o，還是第五行或者第六行末尾的o？這個問題難以解決，因為三個o在最右一列中的順序是由<B>它們的下一個字母</B>決定的，而下一個字母并不已知。因此上述算法對重復字母無能為力。<BR>　　讓我們來一下逆向思維：順推不行，逆推行嗎？答案是肯定的。所謂逆推，就是指當我們知道原文中某個字母在方陣中某一行的開頭時，這一行末尾的字母就是原文中當前字母的上一個字母（把原文中最后一個字母看作第一個字母的上一個字母）。還以totoro為例：第一個字母是t。由于最左一列中相同字母是按<B>它們本身</B>在原文中的位置排列的，因此這個t必定是最左一列中最上面的t，即第五行的t。因此原文的最后一個字母是o。這個o自然應該是最左一列中最下面的o，即第三行的o。所以原文第五個字母是r，第四個字母是o，這個o在方陣中位于第二行第一列……哈，問題圓滿解決。由于排序時運用了桶排，所以復雜度僅為O(n)。
  <SCRIPT>detail 1256,"奇怪的電梯"</SCRIPT>
   　　寬搜求最短路。
  <SCRIPT>detail 1257,"鑄鐵模具"</SCRIPT>
   
  　　開一個大小與模具相等的數組，存儲每個位置被挖去的深度。然后一步一步地模擬刀片的運動，刀片每到一個在模具范圍內的位置，就檢查一下刀片的深度是否大于已挖去的深度。<BR>　　輸入中的中括號是完全沒有用的。本題的一個模塊是讀入數字。由于分號的結束符作用，我們不必開設緩沖區存儲數字后的下一個字符。哈哈，知道Pascal中為什么每條語句后面都要有分號了:)
  <SCRIPT>detail 1258,"九數碼問題"</SCRIPT>
   
  　　由目標狀態開始，逆用移動規則，用BFS求出變換到每個狀態所需的步數，然后問哪個狀態就答哪個好了。為了存儲每個狀態的步數，需要給每個狀態編一個號。我們不妨把0至8這九個數的所有排列按字典序排序，然后從0開始編號。求一個排列的編號可以如下進行：（為簡便起見，以五個數的排列24103為例）<BR>　　2 
  4 1 0 3 //第一個數比2小的5個數的排列共有2*4!=24個<BR>　　　3 1 0 2 
  //把2去掉，剩下的數中比2大的都減小1，就成了一個0~3的排列。第一個數比3小的4個數的排列共有3*3!=18個<BR>　　　　1 0 2 
  //第一個數比1小的3個數的排列共有1*2!=2個<BR>　　　　　0 1 
  //第一個數比0小的2個數的排列共有0*1!=0個<BR>　　所以，排列24103的編號為24+18+2+0=44。
  <P>　　另外獻上一點溫馨提示：UNSOLVABLE的布局是不存在的。
  <SCRIPT>detail 1261,"數列拆分"</SCRIPT>
   
  　　本題沒有什么統一的公式，所以還是要老老實實地分情況討論。<BR>　　首先枚舉項數n。項數的最小值為3。那么最大值呢？我們來看極端情況：各項和一定時，欲使項數盡可能大，應使每項盡可能小。那么數列就應該是1,2,3……因此，若設各項和為n，應有n*(n+1)/2=s。把n=sqrt(s*2)代入，左邊大于右邊，因此方程的正根小于sqrt(s*2)，故可用trunc(sqrt(s*2))作為n的最大值。<BR>　　在項數確定了的情況下，我們可以求出數列每項的平均數m=s*2/n以及最大的公差d=trunc((m-1)/((n-1)/2))（公差最大時首項為1，且m與1的差是(n-1)/2個公差）。下面還要對n分奇偶討論： 

  <UL>
    <LI>當n為奇數時，m就是數列的中間一項，故m必須為整數。這時，滿足條件的數列個數為d。 
    <LI>當n為偶數時，m為數列中間兩項的平均值，它可以是整數，也可以是整數點五的形式。 
    <UL>
      <LI>若m是整數，則公差必為偶數。此時滿足條件的數列個數為d div 2。 
      <LI>若m是整數點五，則公差必為奇數。此時滿足條件數列個數為(d+1) div 2。</LI></UL></LI></UL>
  <SCRIPT>detail 1262,"空間站"</SCRIPT>
  　　本題我做得很麻煩，應該有優化的余地。
  <P>　　此題的模型就是：給定一棵帶權無根樹，求把它的任一條邊的權改為0后，樹中的最長路的最小長度。<BR>　　10<SUP>5</SUP>的數據規模啟示我們使用DP算法。為了DP方便，我們以1號頂點為根，把無根樹轉化為有根樹。我對每個頂點x定義了如下函數（哇，好多啊@:(）： 

  <UL>
    <LI>down1[x],down2[x],down3[x]：在以x為根的子樹中，從x出發的最長路長度、次長路長度、第三長路長度。要求這三條路無公共邊。 

    <LI>below[x]：在以x為根的子樹中的最長路長度。注意這條最長路不一定經過x。 
    <LI>cbelow1[x],cbelow2[x]：x的孩子的below值中最大的一個和次大的一個。 
    <LI>up[x]：在原樹中去掉以x為根的子樹（但保留x結點）后，從x出發的最長路長度。 
    <LI>above[x]：在原樹中去掉以x為根的子樹及x與它父親結點之間的邊后，剩余部分的最長路長度。</LI></UL>　　上述所有函數在所對應的路徑不存在時值均為0。<BR>　　DP總共進行兩次。第一次自底向上進行，求出每個頂點的down1,down2,down3,below,cbelow1和cbelow2函數值；第二次自頂向下進行，求出每個頂點的up和above函數值，順便算出答案。<BR>　　在第一次DP中，當處理到頂點x時，可以按如下方法求出x的一些函數值： 

  <UL>
    <LI>對于x的每一個孩子y，求出x,y之間邊的長度與down1[y]之和。這些和中最大的三個就是<FONT 
    color=blue>down1[x],down2[x]和down3[x]</FONT>。 
    <LI>由于DP是自底向上進行的，x的所有孩子的below值中最大的兩個就是<FONT 
    color=blue>cbelow1[x]和cbelow2[x]</FONT>。 
    <LI><FONT 
    color=blue>below[x]</FONT>為cbelow1[x]與down1[x]+down2[x]中的較大值。前者表示以x為根的子樹中的最長路不經過x，后者表示經過x。</LI></UL>　　第二次DP則是這樣：當處理到頂點x和它的孩子y時，可以按如下方法求出y的一些函數值： 

  <UL>
    <LI>求<FONT color=blue>up[y]</FONT>。up[y]對應的路徑的第一條邊必然是(x,y)（長度記為L），然后有兩種可能：
    <UL>
      <LI>一種是繼續往上走，這時up[y]=L+up[x]；
      <LI>還有一種是往下走。如果往下走，則不可以沿著(x,y)再回來，于是若down1[x]=L+down1[y]，則up[y]應等于L+down2[x]，否則就等于L+down1[x]。</LI></UL>
    <LI>求<FONT color=blue>above[y]</FONT>。有兩種情況：
    <UL>
      <LI>一種情況是above[y]對應的路徑不經過x。這時，它的長度可能是above[x]，也可能是cbelow1[x]（當cbelow1[x]&lt;&gt;below[y]時）或cbelow2[x]（當cbelow1[x]=below[y]時）。
      <LI>另一種情況是above[y]對應的路徑經過x。這時，可以把由x出發的最長的兩條路連起來。候選的路徑長度有：up[x],down1[x],down2[x]。當然，如果down1[x]或down2[x]中有一個等于L+down1[y]，那么它就沒有資格了，而用down3[x]來替代。取候選路長中的最大值和次大值相加，即得above[y]。</LI></UL>
    <LI>求<FONT color=blue>把(x,y)的權修改為0后整棵樹中的最長路長度</FONT>。有三種情況：
    <OL>
      <LI>這條路經過(x,y)，這時路長為up[y]-L+down1[y]（注意up[y]-L不可以用up[x]代替，因為從x開始可以往下走）；
      <LI>這條路在(x,y)上方，這時路長為above[y]；
      <LI>這條路在(x,y)下方，這時路長為below[y]。</LI></OL>取這三者中的最大值，若這個最大值比當前最優解小，則更新最優解。</LI></UL>
  <SCRIPT>detail 1264,"河床"</SCRIPT>
  　　從左到右掃描，依次把每個深度加入“當前段”中。當“當前段”中的最大值與最小值的差超過限制時，就在“當前段”開頭截去盡可能短的一段，使最大值與最小值的差重新滿足要求。那么，本題的關鍵就在于在最大值（或最小值）被截去后，如何快速地找到新的最大值（或最小值）。<BR>　　用線段樹等樹形結構，可以輕松地在1M內存以內解決問題，但它的時間復雜度為O(nlogd)，經測試，運行完所有數據需要將近2s。而實際上本題的內存限制是很松的。所以我們采用時空復雜度均為O(n)的隊列解決本題。<BR>　　開兩個隊列，一個叫做<B>大隊</B>，一個叫做<B>小隊</B>。如果一個深度滿足它是從它所在位置到“當前段”末尾的最大值（最小值），那么它就屬于大隊（小隊）。另外附加一條規則：如果大隊或小隊中有若干個深度相同，那么僅保留位置最靠前的那一個。容易看出，大隊中深度是遞減的，小隊中的深度是遞增的。<BR>　　當“當前段”向右延伸一個位置的時候，就把這個新的深度加到兩個隊列末尾。這時，大隊或小隊的單調性可能被破壞。如果發生了這種情況，就把單調性被破壞的隊列的倒數第二個元素刪除，直至單調性重新成立為止。現在檢查一下“當前段”是否滿足要求。若大隊隊首元素（就是“當前段”中的最大深度）與“當前段”尾的深度之差超過限制，那么就不斷地刪除大隊隊首元素直至滿足要求，同時把“當前段”首指針移到最后刪除的那個深度所在位置的下一個位置。若小隊隊首元素與“當前段”尾的深度之差超過限制，則可用類似的辦法進行處理。計算“當前段”的長度，與最優解比較。
  <SCRIPT>detail 1265,"批次計劃管理"</SCRIPT>
   　　DP，并用斜率優化法優化到O(n)。有關斜率優化法的原理請參看<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1171">1171</A>，在此只對本題進行數學推導。
  <P>　　逆推。用T[i]表示第i項工作以后的工作所需的總時間，F[i]表示第i項工作以后的工作的總處理成本因素。設<B>從0時間開始</B>做第i項工作以后的工作所需的總成本為cost[i]，則有狀態轉移方程：<BR>　　cost[n]=0<BR>　　cost[i]=min{(S+T[i]-T[j])*F[i]+cost[j]}(i&lt;j&lt;=n)<BR>　　cost[0]為所求。
  <P>　　決策a比決策b優(a&gt;b)的充要條件是：<BR>　　　　(S+T[i]-T[a])*F[i]+cost[a]&lt;(S+T[i]-T[b])*F[i]+cost[b]<BR>　　&lt;=&gt; 
  cost[a]-cost[b]&lt;(T[a]-T[b])*F[i]<BR>　　&lt;=&gt; 
  (cost[a]-cost[b])/(T[a]-T[b])&gt;F[i] (∵T[a]&lt;T[b])
  <P>　　定義(cost[a]-cost[b])/(T[a]-T[b])為決策a、b間的<B>斜率</B>。維護一個決策隊列，使它滿足相鄰元素間的斜率遞增。當階段為i時，先將決策i+1加入隊尾，通過不斷刪除隊列倒數第二個元素來維護它斜率的單調性。然后若隊首兩元素間的斜率小于F[i]，則說明隊首決策現在不是、將來也不會是最優決策，故將其刪除。當隊首兩元素間斜率大于等于F[i]時，隊首元素就是當前的最優決策了。
  <SCRIPT>detail 1266,"最小生成樹"</SCRIPT>
   
  　　下文中，把輸入的圖稱作G，選定的生成樹稱作S，S中的邊叫做<B>樹邊</B>，其余的邊叫做<B>非樹邊</B>。<BR>　　為什么要修改某些邊的權值呢？這是因為，把一條非樹邊Y加入S后，S中會出現一個環，而這個環上的某一條樹邊X的權值(w[X])可能比Y的權值(w[Y])大。為了使S成為最小生成樹，就必須減小X的權值，增大Y的權值，以使w[X]&lt;=W[Y]。如果把w[X]的變化量（當然是減小量）記作d[X]，把w[Y]的變化量（當然是增加量）記作d[Y]，那么我們可以列出不等式：w[X]-d[X]&lt;=w[Y]+d[Y]，即d[X]+d[Y]&gt;=w[X]+w[Y]。<BR>　　對于什么樣的邊對(X,Y)，需要列這樣的不等式呢？這樣的邊需要滿足的條件是：把Y加入S后，X在形成的環上。也就是說，X在S中Y的兩個頂點間的路徑上。對于任一條非樹邊Y，為了找出需要與它列不等式的所有樹邊X，我們需要把S看成一棵有根樹，求出Y的兩個端點u、v的最近公共祖先a。分別從u和v向上走到a，對路上滿足w[X]&gt;w[Y]的邊X都列出一個不等式。這一步求最近公共祖先，由于數據規模很小，樸素算法就可以，當然也可以用效率更高的Tarjan算法，詳見<A 
  href="http://purety.jp/akisame/oi/TJU/vol1.htm#1068">1068</A>題。<BR>　　現在我們得到了一個不等式組，我們需要求出使所有變化量之和最小的一組解。觀察這組不等式，發現它們與求<B>二分圖最大權匹配</B>（參見<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1148">1148</A>題）時頂標所滿足的條件形式完全相同。而求出最大權匹配后，頂標之和確實達到了最小。因此我們建立一個二分圖B，把每條樹邊看成一個X頂點，每條非樹邊看成一個Y點。如果一個X點與一個Y點之間列了不等式，那么B中它們之間的邊權就是不等式的右邊，即它們在G中的權值之差；如果沒有列，那么B中它們之間的邊權為0。如果X點數與Y點數不相等，則補齊，并讓它與所有異種點之間的邊權全為0。然后用KM算法求出B的最大權匹配，這時匹配邊的總權值（也就是所有頂點的頂標和）就是最小代價。同時，我們還求出了一種修改權值的方案：每個點的頂標就是它對應的G中的邊的權值的變化量。<BR>　　其實，上面“補齊”的頂點若是X頂點（一般情況下非樹邊比樹邊多得多），則它們根本不必考慮，因為它們即使匹配上了，對權和的貢獻也只是0。因此，匹配完原有的X頂點就可以停止了。
  <P>　　長郡中學的王俊提出了一種更簡單的算法。他把求最大權匹配的問題轉化為求最大匹配。他的思路是：題目中只要求求出最小代價，并沒有要求求出修改方案，因此把邊上的權值轉移到點上。他建立了一個新的二分圖B'，以所有的樹邊為X頂點，所有邊（包括樹邊與非樹邊）為Y頂點。X頂點及邊均無權值，Y頂點的權值為G中的邊權。B'中的邊是這樣連的：B中每一條權不為0的邊在B'中都有對應的邊，另外每個代表樹邊的Y頂點都與代表同一樹邊的X頂點之間連一條邊。這樣做以后，B的完備匹配與B'的最大匹配之間就建立了一一對應的關系，且對應的兩個匹配的權和之和為原圖中所有樹邊的權值之和： 

  <UL>
    <LI>如果B的匹配中與某個X頂點相連的邊權為0，那么B'中這個X頂點就匹配與自己代表同一樹邊的Y頂點。B中這條邊的權值為0，B'中這條邊的權值為這個頂點代表的樹邊本身的權值，其和為樹邊本身的權值。 

    <LI>如果B的匹配中與某個X頂點相連的邊權不為0，那么B'中這個X頂點仍匹配B中X匹配的Y頂點。B中這條邊的權值為w[X]-w[Y]，B'中這條邊的權值為w[Y]，和仍為w[X]，即樹邊的權值。</LI></UL>　　因此，B和B'中對應匹配的權和之和為原圖中所有樹邊的權值之和。欲求B的最大權匹配，只需求B'的最小權最大匹配。而G'的權值都在Y頂點上，因此把所有Y頂點按權值遞增的順序排序，依次匹配即可。<BR>　　（注：我的程序用的是王俊的算法，但X頂點和Y頂點被交換了過來。）
  <SCRIPT>detail 1267,"小店購物"</SCRIPT>