<TD>9
    <TD>13
    <TD>17
    <TD>25
    <TD>33
    <TD>41
    <TD>49
    <TD>65 
</TR></TBODY></TABLE>　　觀察這個表，我們可以大膽地猜想g[i]的規律：<B>從1開始，加2次2，再加3次4，再加4次8，再加5次16……</B>這個猜想的證明過程過于瑣碎，詳細、嚴謹的步驟反而會妨礙理解，我只說一下大概思路：顯然g[2]是用g[1]和f[1]算出來的。假設g[i]=g[j]*2+f[i-j]，那么g[i+1]=min{g[j+1]*2+f[i-j],g[j]*2+f[i-j+1]}，即把f或g的下標增加1。為什么呢？因為f和g兩個數列都是增長的，而且增長得越來越快。如果在最優解的基礎上讓f的下標變大、g的下標變小，或是相反，結果不是不變就是變大。親手模擬一下g的計算過程，就會發現，<B>g數列加2<SUP>k</SUP>的次數等于g數列加2<SUP>k-1</SUP>的次數與f數列加2<SUP>k</SUP>的次數之和。</B>由此可以得出上面的猜想。<BR>　　這個問題可以推廣到m塔的情況。用a[i]表示m柱i盤時所需的移動次數，則a數列有這樣一個規律：a[1]=1，以后依次有<IMG 
src="vol1.files/1034_1.gif">項比前一項大2<SUP>k</SUP>，其中k從1開始取整數值。
<SCRIPT>detail 1035,"撕郵票"</SCRIPT>
 
　　搜索、判重。判重時若保存整個圖象比較每個格子則嫌慢，其實有一點小技巧：把每個圖象看作一串二進制數，用一個數來存儲這個圖象每個格子的信息，再加上一個寬度就可以唯一地表示一個圖象了。由于一個圖象經翻轉、旋轉可得到8種形態，我們需要按某種規則只存儲一個（如寬度取較長邊，寬度一定時使二進制數最小）。這樣既節省了時間，又節省了空間。
<SCRIPT>detail 1036,"序列函數"</SCRIPT>
 
　　用一個隊列q來存儲序列，初始時設q[0]=1。設三個頭指針f1,f2,f3，分別對應于三個質數p1,p2,p3（假設p1&lt;p2&lt;p3）。頭指針的初值均為0。每次取q[f1]*p1,q[f2]*p2,q[f3]*p3中的最小值，如果當前隊列為空或它與當前隊尾元素不同，則將其放進隊列。無論是否放進隊列，都將產生最小值的頭指針加1。當隊列達到所需的長度時，輸出隊尾元素。
<SCRIPT>detail 1037,"最短網絡"</SCRIPT>
 　　赤裸裸的最小生成樹模型。
<SCRIPT>detail 1038,"化學方程式"</SCRIPT>
 
　　思路極清晰：列多元一次方程組，用高斯消元法解。所謂高斯消元法，就是用一個含x<SUB>i</SUB>的方程（記為E<SUB>i</SUB>）與其它所有方程加減，消去其它方程中的x<SUB>i</SUB>，待解出x<SUB>1</SUB>至x<SUB>i-1</SUB>后，代入E<SUB>i</SUB>求x<SUB>i</SUB>。但編程極麻煩，具體來說，有下面幾點提示或注意事項： 

<UL>
  <LI>跟<A 
  href="http://purety.jp/akisame/oi/TJU/vol2.htm#1117">1117</A>一樣，列方程時最好在整個反應式最左邊加個'+'，倒著進行。 

  <LI>消元時若待消的未知數已不存在，則No solution。 
  <LI>消元時若未知數比方程多兩個或兩個以上，即方程過少，則No solution。 
  <LI>消到只剩一個未知數時，方程應當一個也不剩，否則，剩下的方程中均只含最后一個未知數，它只能等于0，這是不合題意的。簡言之，方程過多時也是No 
  solution。 
  <LI>兩個方程加減后不要忘了及時約掉各系數的最大公約數，以免過程中系數過大。 
  <LI>消元結束后，令x<SUB>1</SUB>=1，利用各E<SUB>i</SUB>依次推出各x<SUB>i</SUB>。若碰到某個x<SUB>i</SUB>為分數，則將x<SUB>1</SUB>至x<SUB>i-1</SUB>均乘以x<SUB>i</SUB>的分母。若碰到某個x<SUB>i</SUB>&lt;=0，則No 
  solution。</LI></UL>
<SCRIPT>detail 1039,"核電站問題"</SCRIPT>
　　DP。用f[n]表示n個坑時的放法數，則有<BR>　　f[0]=1<BR>　　f[n]=f[n-1]*2 
(1&lt;=n&lt;m)<BR>　　f[n]=<IMG src="vol1.files/1039_1.gif" align=absMiddle> 
(n&gt;=m)<BR>　　注意到f[n-1]=<IMG src="vol1.files/1039_2.gif" align=absMiddle> 
(n&gt;m)，兩式相減得f[n]-f[n-1]=f[n-1]-f[n-m-1] 
(n&gt;m)。于是可以化簡最后一個方程：<BR>　　f[m]=f[n-1]*2-1<BR>　　f[n]=f[n-1]*2-f[n-m-1] (n&gt;m)
<SCRIPT>detail 1040,"N的倍數"</SCRIPT>
 
　　妙極了的算法：最短路。<BR>　　把自然數除以N的每個可能余數，即0~N-1，分別看成一個結點。若一個數字d是可用的，那么對任一頂點x，連一條從x到(x*10+d) 
mod 
N的有向邊，邊上標有數字d。然后把結點0看成兩個結點0和0'，用簡單的BFS找一條從0到0'的最短路，路徑上所有邊上標的數字連起來就是答案。<BR>　　用BFS似乎只能保證答案的位數最少而不能保證值最小，其實不然。只要在擴展結點時按邊上所標數字從小到大的順序進行，答案的值也一定是最小的。
<SCRIPT>detail 1041,"戰略游戲"</SCRIPT>
 
<UL>
  <LI><FONT 
  color=blue><B>樹型DP</B></FONT>（我的算法）：首先建樹，任選一個結點為根。設要看守住以x為根的子樹中所有邊，x處有士兵時需要的最少士兵數為yes[x]，x處無士兵時需要的最少士兵數為no[x]。自下而上地計算每個結點的yes值和no值：一個結點的yes值等于它所有子樹的yes值與no值的較小值之和再加1；no值等于它所有子樹的yes值之和。根結點的yes值和no值中的較小值即為答案。 

  <LI><FONT 
  color=blue><B>貪心</B></FONT>：找出所有度為1的結點，把與它們相連的結點上都放上士兵，然后把這些度為1的結點及已放上士兵的結點都去掉。重復上述過程直至樹空為止。 

  <LI><FONT color=blue><B>二分圖最小覆蓋</B></FONT>（by 
  HybridTheory）：把樹看成一個二分圖，奇數層的結點放到一邊，偶數層的結點放到一邊，然后求這個二分圖的最小覆蓋數（等于最大匹配數）。</LI></UL>
<SCRIPT>detail 1042,"替換問題"</SCRIPT>
　　好奇異的算法，不知<B>Cocoran</B>大牛是怎么想出來的。<BR>　　用S<SUB>i</SUB>表示a<SUB>1</SUB>至a<SUB>i</SUB>的和，S'<SUB>i</SUB>表示b<SUB>1</SUB>至b<SUB>i</SUB>的和。下面研究三種操作對各S<SUB>i</SUB>的影響： 

<UL>
  <LI>對a<SUB>i-1</SUB>、a<SUB>i</SUB>、a<SUB>i+1</SUB>(1&lt;i&lt;n)進行操作，相當于交換了S<SUB>i-1</SUB>和S<SUB>i</SUB>。 

  <LI>對a<SUB>n</SUB>、a<SUB>1</SUB>、a<SUB>2</SUB>進行操作，相當于把所有的S<SUB>i</SUB>都減去a<SUB>1</SUB>，再交換S<SUB>1</SUB>與S<SUB>n</SUB>。 

  <LI>對a<SUB>n-1</SUB>、a<SUB>n</SUB>、a<SUB>1</SUB>進行操作，相當于把所有的S<SUB>i</SUB>都加上a<SUB>n</SUB>，再交換S<SUB>n-1</SUB>與S<SUB>n</SUB>。</LI></UL>　　于是我們看出，無論進行多少次怎樣的操作，結果只是把所有的S<SUB>i</SUB>都加上或減去了某一數值，然后進行了若干次交換。于是把a<SUB>1</SUB>至a<SUB>n</SUB>、b<SUB>1</SUB>至b<SUB>n</SUB>分別排序，若所有的S<SUB>i</SUB>-S'<SUB>i</SUB>均相等，則YES，否則NO。
<SCRIPT>detail 1043,"黑白棋"</SCRIPT>
 　　簡單深搜。只是面對某一個棋局時，若輪到的一方無處下子，要妥善處理pass的情況。
<SCRIPT>detail 1046,"立方餡餅"</SCRIPT>
 
　　把x+y+z的為奇數的格子染成黑色，x+y+z為偶數的格子染成白色。若n為奇數，則Yes的充要條件是起點與終點均為黑色；若n為偶數，則Yes的充要條件是起點與終點異色。
<SCRIPT>detail 1047,"自然數序列"</SCRIPT>
 
　　每次取數列的后四項，讓兩頭兩項為正，中間兩項為負（當然反過來也行），這樣這四項的和就是0了，將這四項刪去。這樣做到最后最多只剩3項。若剩3項或一項也不剩（即n 
mod 4=3或0），則答案為0，否則答案為1（因為添加負號不改變和的奇偶性，而這時所有數的和為奇數，故答案無法達到0）。
<SCRIPT>detail 1048,"Tom的煩惱"</SCRIPT>
 
　　用best[t]表示在時間t以前Tom得到的最大加工費。按時間遞增的順序計算best數組。對每個best[t]，首先令其為上一個時間的best值，然后對于每一個在時間t結束的工作（設其開始時間為s，加工費為m），比較best[s]+m與best[t]的值，取大者。<BR>　　由于時間的數值可能遠遠大于工作的數量，因此最好首先對時間進行離散化。
<SCRIPT>detail 1049,"砝碼問題"</SCRIPT>
 　　思路參看<A href="http://purety.jp/akisame/oi/TJU/vol1.htm#1017">1017 
石子歸并</A>問題。本題的大數據規模版本就是<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#1166">1166 背包問題</A>。
<SCRIPT>detail 1057,"辦公室失竊案"</SCRIPT>
 　　把每個時間段看成一條線段，用掃描線法找到被n條線段同時覆蓋的區間，輸出。當然要注意輸入輸出的細節。
<SCRIPT>detail 1058,"地板覆蓋問題"</SCRIPT>
 
　　老老實實地按題目說的順序判斷，即先判斷所有磚中是否有交叉，再判斷所有磚中是否有越界情況，最后判斷地板是否全被覆蓋。切不可看到第一塊磚越界了就下結論，因為第二塊和第三塊可能交叉。兩塊磚(x1,y1)-(x2,y2)與(x3,y3)-(x4,y4)交叉的充要條件是(x1&lt;x4) 
and (x3&lt;x2) and (y1&lt;y4) and 
(y3&lt;y2)。第三步判斷磚是否蓋滿地板時，可以累加所有磚的面積，若這個和與地板的面積相等，則蓋滿。
<SCRIPT>detail 1059,"數的計數"</SCRIPT>
 　　用f[n]表示最后一個數是n時，可以構造出的數的總數。規定f[0]=1，則顯然有f[n]=f[0]+f[1]+...+f[n div 
2]。<BR>　　但若直接使用這個方程，則會既TLE又MLE。注意到右邊其實是f數組開頭若干個元素的和，因此可開一個s數組，用s[n]來存儲f[0]至f[n]的和。這樣時間上顯然沒有問題。實際上，現在f數組已經不必要了，因為用s數組可寫出如下狀態轉移方程：s[n]=s[n-1]+f[n]=s[n-1]+s[n 
div 2]。當讀入n時，輸出s[n div 
2]即可。<BR>　　結果很大，高精度是當然的。可以用3個int64來存儲一個數。這里我們看到用s數組代替f數組同樣解決了MLE的問題，因為s數組的大小只有f數組的一半，題目允許的內存不能容納f數組，卻恰好可以容納s數組。
<SCRIPT>detail 1060,"方程的解數"</SCRIPT>
 　　查了一下NOI的原題，發現有一個重要條件，題目中落掉了：<B><FONT 
size=4>Σ</FONT>Ki*M<SUP>Pi</SUP>&lt;=maxlongint</B>。這個條件告訴我們，無論每個x取什么值，結果不會超過longint范圍，因此不必考慮int64或是高精度之類的問題。另外，由于150<SUP>5</SUP>&gt;maxlongint，所以P不會超過4。<BR>　　這道題只能用枚舉法，其瓶頸顯然在于計算速度。注意到乘冪運算需屢次進行，因此很自然地想到用預處理先計算出所有的乘冪值（只有150*4=600個而已）。然而這畢竟只是細節上的優化，本質的還在于找一個高效的算法。<BR>　　把方程的半數項移到右邊。得到的新方程與原方程是相似的，只是右邊不再為0。但是，每一邊的項數不超過3，也就是說枚舉量不超過150<SUP>3</SUP>=3375000，這個復雜度是完全可以承受的。我們可以枚舉左邊，用一個表將所有可能的結果及其出現次數存儲起來，然后枚舉右邊，在表中查找右邊結果的相反數，累加表中存儲的出現次數即得到答案。現在的問題是：用什么表來存儲結果呢？<BR>　　如果用有序表和二分查找的話，那么對300多萬個數進行排序就需要好幾秒，對同樣多的數進行二分查找又需要同樣多的時間，顯然不可取。本題適用的數據結構是：<B>哈希表</B>。哈希函數很好找：設x為結果，那么hash(x)=abs(x) 
mod 
bigprime，其中bigprime為一個取定的大質數。這樣，存儲和查找就幾乎都是線性的了。這樣處理以后，算法的時間復雜度為O(M<SUP>3</SUP>)，帶一個適中的常數系數。<BR>　　然而本題的內存限制是很緊的，哈希表這種耗內存的數據結構一不小心就會MLE。我的經驗是： 

<UL>
  <LI>不要用指針，而用數組來模擬，因為指針本身就耗內存，而且分配、回收操作也浪費不少時間。至于處理沖突的問題，可以建立公共溢出區，即把沖突的元素統統放到公共溢出區中。 

  <LI>哈希表中無需存儲原始的元素。假設原始元素為x，那么在hash表中只需存儲x div 
  bigprime+ord(x&gt;0)。之所以要加入ord(x&gt;0)一項，是因為如果不加，-1和1就會變成同一個數0。經過這一變換，x的范圍就由原來的longint變為integer（我的bigprime取的是999983），又省了大量內存。</LI></UL>
<SCRIPT>detail 1061,"堆棧計算"</SCRIPT>
　　題目中的表達式是一個樹型結構，因此想到用樹型DP解決這個問題。<BR>　　把在表達式中位置為i的字符代表的結點稱作結點i。首先用遞歸的方法找到每個B結點的左孩子的位置。結點i的左孩子用child[i]表示，顯然結點i的右孩子為i-1。<BR>　　用space[i]表示計算以i為根的子樹所需的最少堆棧空間，swap[j,i]表示如果有大小為j的堆棧空間可用，計算以i為根的子樹所需的最少交換次數。堆棧大小不同時，這個次數是不同的，例如...BB在堆棧空間為2時需要交換1次，而在堆棧空間為3時則一次也不需要。<BR>　　按堆棧空間的大小j劃分階段，j的初值為1，這時對每個.結點i，有space[i]=1，swap[1,i]=0；對每個B結點i，有space[i]=無窮大，swap[1,i]=無窮大，這里的無窮大表示還沒有算出來。<BR>　　設表達式長為l，則當space[l]=無窮大時，j加1，進行下面的狀態轉移。從左到右依次處理每一個結點的space值和swap值。 

<UL>
  <LI><B>space值的計算</B>：如果一個B結點(i)的space值為無窮大，而它的兩個孩子（a、b）的space值都已算出，且有一個小于j（不妨設space[a]&lt;j），那么令space[i]為j。這是因為可先利用大小為j的堆棧空間計算以b為根的子樹，1個單位的堆棧空間被用來存儲結果，而剩下的j-1個單位的堆棧空間足以計算以a為根的子樹。 

  <LI><B>swap值的計算</B>：對于.結點，swap[j,i]顯然為0。對于B結點(i，左右孩子分別為a、b)，則swap[j,i]=min{swap[j-1,i],swap[j,a]+swap[j-1,b],swap[j,b]+swap[j-1,a]+1}。注意最后一個元素，若先計算右子樹，后計算左子樹，則最后需交換兩個結果，因此要加1。</LI></UL>　　注意到在計算swap數組的第j行時只用到了第j-1行，因此swap數組可用滾動數組來實現。
<SCRIPT>detail 1068,"商務旅行"</SCRIPT>
 
<TABLE align=right>
  <TBODY>
  <TR>
    <TD><IMG 
      src="vol1.files/1068_1.gif"><BR>處理結點10的時候并查集的情況<BR>（假設結點是按從左到右的順序處理的）<BR>與10的LCA是10的結點集合：{10}<BR>與10的LCA是8結點集合：{8 
      9 11}<BR>與10的LCA是3的結點集合：{3 7}<BR>與10的LCA是1的結點集合：{1 2 5 6}<BR>不屬于任何集合的結點：4 
      12 </TR></TBODY></TABLE>　　<FONT 
color=blue><B>感謝Faint.Wisdom講解求最近公共祖先(LCA)的Tarjan算法！</B></FONT>下面是算法的詳細講解：<BR>　　首先，Tarjan算法是一種離線算法，也就是說，它要首先讀入所有的詢問（求一次LCA叫做一次詢問），然后并不一定按照原來的順序處理這些詢問。而打亂這個順序正是這個算法的巧妙之處。看完下文，你便會發現，如果偏要按原來的順序處理詢問，Tarjan算法將無法進行。<BR>　　Tarjan算法是利用并查集來實現的。它按DFS的順序遍歷整棵樹。對于每個結點x，它進行以下幾步操作： 

<UL>
  <LI>計算當前結點的層號lv[x]，并在并查集中建立僅包含x結點的集合，即root[x]:=x。 
  <LI>依次處理與該結點關聯的詢問。 
  <LI>遞歸處理x的所有孩子。 
  <LI>root[x]:=root[father[x]]（對于根結點來說，它的父結點可以任選一個，反正這是最后一步操作了）。</LI></UL>　　現在我們來觀察正在處理與x結點關聯的詢問時并查集的情況。由于一個結點處理完畢后，它就被歸到其父結點所在的集合，所以在已經處理過的結點中（包括x本身），x結點本身構成了與x的LCA是x的集合，x結點的父結點及以x的所有已處理的兄弟結點為根的子樹構成了與x的LCA是father[x]的集合，x結點的父結點的父結點及以x的父結點的所有已處理的兄弟結點為根的子樹構成了與x的LCA是father[father[x]]的集合……（上面這幾句話如果看著別扭，就分析一下句子成分，也可參照右面的圖）假設有一個詢問(x,y)（y是已處理的結點），在并查集中查到y所屬集合的根是z，那么z就是x和y的LCA，x到y的路徑長度就是lv[x]+lv[y]-lv[z]*2。累加所有經過的路徑長度就得到答案。<BR>　　現在還有一個問題：上面提到的詢問(x,y)中，y是已處理過的結點。那么，如果y尚未處理怎么辦？其實很簡單，只要在詢問列表中加入兩個詢問(x,y)、(y,x)，那么就可以保證這兩個詢問有且僅有一個被處理了（暫時無法處理的那個就pass掉）。而形如(x,x)的詢問則根本不必存儲。<BR>　　如果在并查集的實現中使用路徑壓縮等優化措施，一次查詢的復雜度將可以認為是常數級的，整個算法也就是線性的了。<BR>　　另外，實現上還有一點技巧：樹的邊表和詢問列表的存儲可以用數組模擬的鏈表來實現。<BR>
<SCRIPT>detail 1071,"一道簡單題-版本1"</SCRIPT>
　　用s[i]表示前i個數之和。從1到n枚舉累加段的右端j，當j一定時，我們的問題就是找一個i(j-l2&lt;=i&lt;=j-l1)，使s[j]-s[i]最大，即s[i]最小。于是我們想到了堆。維護一個堆，使堆中任一對父子結點x,y（x為父結點），都有s[x]&lt;=s[y]。在右端枚舉到j時，若j&gt;=l1，那么就把j-l1放到堆里。這時考察堆頂元素（記作i）：若i&lt;j-l2，那么現在i是不合法的，以后也不會合法，把它從堆中刪除。不斷刪除堆頂元素直至i&gt;=j-l2。這時得到累加段右端為j時的最大和s[j]-s[i]，與當前最優解比較，取最大值。<BR>　　這種算法的時間復雜度為O(nlogn)，需要開兩個大小為n的數組。這個空間復雜度對版本2是行不通的。其實，本題還有更優的算法，只是我在做本題時沒有想到。詳見<A 
href="http://purety.jp/akisame/oi/TJU/vol2.htm#1175">版本2</A>。