<SCRIPT>detail 1074,"鏡子迷宮"</SCRIPT>
 
　　本題數據范圍很小（這是當然的），所以可以用分層圖BFS解決。<BR>　　分層圖的每一層對應著所有鏡子的一個狀態。不妨用二進制給每個狀態編號：假設共有5個鏡子，其中3、5號鏡子被旋轉了，則可用10100<SUB>2</SUB>=20<SUB>10</SUB>表示這個狀態。于是，我們首先需要求出在每一層中，有哪些位置是不可到達的。這一過程很簡單：在確定每個鏡子的方向后，從每個發射器出發，把不可到達的位置依次做上標記即可。<BR>　　然后，從初始層的起點出發，進行BFS。擴展隊列有兩種方法：一是向四個方向之一前進一步，二是旋轉某個鏡子，即進入另一層。假設原來在第10100<SUB>2</SUB>層，旋轉了第2個鏡子，那么就來到了第10100<SUB>2</SUB> 
xor 00010<SUB>2</SUB>=10110<SUB>2</SUB>層。如果搜到了任一層的終點，則成功。
<SCRIPT>detail 1075,"一道簡單題-版本2"</SCRIPT>
 　　A <B>simple</B> prob isn't usually an <B>easy</B> 
prob.<BR>　　首先提出一個性質：如果某一段開頭一部分的和&lt;=0，那么把這一段刪去后，剩余部分的和不會比原來小。<BR>　　設置兩個指針p和i，p分別指向累加段的左端的前一位置，i指向累加段的右端。再設一個變量s，保存當前的累加和。初始時，p=0，i=l1，s=前l1個數之和。然后將i不斷移直至n。記i-l1=j。對于i的每一個位置，第j個數以后的數是必須取的，而第j個數及以前的數都是可取可不取的（以下稱第j個數及以前的數為<B>自由段</B>）。若自由段開頭某一段的和&lt;=0，那么這一段就可以刪去了。因此可另開一個累加器s0，每次把i后移一個位置，在s上加上第i個數，在s0上加上第j個數。若某時刻s0&lt;=0，則p:=j;dec(s,s0);s0:=0。<BR>　　但我們又遇到了一個問題：我們只有在自由段的開頭有一段的和&lt;=0時才縮短累加段，那么如果累加段的長度已經達到了l2，而自由段開頭任一段的和均為正值怎么辦？當i再后移時，必須刪掉自由段開頭的一部分了！當然，我們還是希望刪掉部分的和越小越好。那么怎么知道加到哪里的和最小呢？<BR>　　我們不再使用累加器s0，而是把它換成兩個隊列a和b。隊列中存儲的是把自由段分成的若干段，a[x]表示一段的和，b[x]表示一段的結束位置。下面用r表示隊尾。i每后移一個位置，就往s上累加第i個數，同時把第j個數連同它的位置一同放到隊尾：inc(r);a[r]:=第j個數;b[r]:=j。若a[r]&lt;=0，那么： 

<UL>
  <LI>若隊列中只有一段，那么這一段就是自由段開頭的一段，因為它的和&lt;=0，故把它刪去即可。 
  <LI>若隊列中不只這一段，那么可以把這一段與上一段合并：inc(a[r-1],a[r]);b[r-1]:=b[r];dec(r)，因為反正這一段的和&lt;=0，若刪掉最后這一段之前的所有段，不如把這一段一起刪掉。重復合并直至隊列中只剩一段或a[r]&gt;0為止。</LI></UL>　　刪除某一段時，令p為這一段的b值，并從s中減去這一段的和。比較i在每個位置時的s值，其中最大值就是答案。<BR>　　這種算法解決了累加段長度達到l2時，自由段開頭沒有和&lt;=0的一段的問題：因為這時隊列中所有段的a值均為正，所以僅刪第一段的損失最小。此算法的時間復雜度為O(n)，優于<A 
href="http://purety.jp/akisame/oi/TJU/vol1.htm#1071">版本1</A>中所述。<BR>　　然而現在內存上還有一個嚴峻的問題：每個隊列的大小最大可能為n，開兩個大小為n的longint數組就要耗用4*300000*2=2400KB的內存，MLE了。也許你會想：b數組存放的是位置，它的大小不會超過n，因此存儲每個數用3個字節就夠了；而題目中說中間結果及最后結果絕對值都不超過100000，a數組每個數用3個字節似乎也行。但實際上本題可以只開一個數組的：對隊列中的每一段，若它的長度為1，那么它的b值不必存儲，可利用上一段的b值加1間接得出（“第一段的上一段的b值”就是p），因此隊列中只存它的a值；若它的長度&gt;1，則只能把a、b兩值都存下（我的程序中把b值放在前面）。那么怎么區分隊列中的值哪些是a值，哪些是b值呢？注意到所有的a值都是正的（除非隊列中只有一段），因此把所有的b值存為它的相反數即可。這樣做以后，長度為1的段在隊列中占用一個longint，更長的段占用2個longint，也就是說總共只需n個longint。盡管這樣做隊列的操作會麻煩一些。程序請見ac1075a.pas。
<P>　　P.S.樓天城大牛有不用數組的算法，程序運行的時間也只有我的1/3——25ms左右。他是怎樣做的我就不知道了(-_-b)
<P>　　<FONT 
color=blue><B>一種更簡單的O(n)算法：</B></FONT><BR>　　考慮前i個數的和——部分和s[i]。把s[i]-s[j]中的i看作階段，j看作決策。開一個決策隊列，使隊列中的決策具有部分和遞增的性質。當處理到第i個數時，把過時(i-j&gt;l2)的決策從隊首刪除，并把新產生的決策(j=i-l1)放到隊尾。若決策部分和的遞增性被破壞，即倒數第二個決策優于最后一個決策，則倒數第二個決策永遠不會最優。不斷刪除倒數第二個決策直至部分和遞增性成立。這時隊首決策為當前最優決策。<BR>　　ac1075b.pas存放了這個算法的程序。空間問題我是采用以3個字節表示一個數的方法解決的，因為這樣編程復雜度較低。
<SCRIPT>detail 1077,"挑戰"</SCRIPT>
 
　　首先算出彩虹可以挨打的次數a和貓老大可以挨打的次數b。<BR>　　比較容易想到的算法是DP：設f[a,b]為貓老大的勝率，則f[a,b]=(f[a,b-1]+f[a-1,b])/2，邊界情況為f[0,x]=1，f[x,0]=0（x為正整數）。但是，a和b的最大值均為32767，在極端情況下DP會超時。<BR>　　然后想到組合的方法。貓老大若想取勝，則在前a+b-1個回合中，他至少要進攻a次。那么貓老大的勝率=<IMG 
src="vol1.files/1077_1.gif">。之所以化成第二種形式是為了方便計算，是因為第二種形式中和式的每一項的計算過程中只用了乘除法，可以用對數計算，而結果不超過1，可以直接相加。另外，不必每個組合數都重新計算，計算一個組合數時，在上一個的基礎上乘以一個數再除以一個數即可。這樣設計出的算法是線性的，雖然每次運算慢了點。
<SCRIPT>detail 1079,"賭博游戲"</SCRIPT>
 
　　典型的博弈問題，尋找貓的必敗態。顯然，0是必敗態。觀察每次可以拿的黃金的塊數，發現它們都不能被3整除，因此，3的倍數都是必敗態。因此，如果開始時黃金塊數是3的倍數，則王勝，否則貓勝，第一次拿走黃金塊數除以3的余數即可。因為10 
mod 3=1，所以求一個數除以3的余數只要把所有數位相加，這個和除以3的余數就是原數除以3的余數。
<SCRIPT>detail 1080,"禮物"</SCRIPT>
 
　　枚舉左右兩邊（不要忘了整塊布的左右邊界），然后在左右兩邊確定的豎條中用掃描線法找能切出的高度最大的手絹。可在預處理中把所有的上下邊排一下序，做掃描線時直接利用。
<SCRIPT>detail 1081,"貓老大數"</SCRIPT>
 
　　先用預處理求出sqrt(maxlongint)以內的質數表。對一個給定的數n，若n正好是某個質數的平方，那么它是一個貓老大數。以下討論n不是某質數平方的情況： 

<UL>
  <LI>一個貓老大數分解質因數后的形式為n=p*q(p&lt;q)，那么一定有p在2至sqrt(n)的范圍內，而q在此范圍外； 
  <LI>若n不是貓老大數，則： 
  <UL>
    <LI>n可能等于1，這時n在2至sqrt(n)范圍內無質因數； 
    <LI>n可能本身就是質數，這時n在2至sqrt(n)范圍內亦無質因數； 
    <LI>n有多于2個（不是2種）質因數，這時n在2至sqrt(n)范圍內的質因數必然多于1個（不是1種）。這點可由反證法證明：假設n在2至sqrt(n)范圍內的質因數只有1個，那么其余的2個或2個以上質因數就都大于sqrt(n)，其積必大于n，而是這不可能的。</LI></UL></LI></UL>　　由上可以得出不是質數平方的n是貓老大數的充要條件：對所有2至sqrt(n)的質數p，累加n中因數p的個數。若累加和恰為1，那么n是貓老大數，否則不是。
<SCRIPT>detail 1082,"最遠距離點對"</SCRIPT>
 
　　首先，距離最遠的兩個點一定都在輸入的點的凸包上。簡證如下：設距離最遠的兩個點為A和B，旋轉圖形使B點位于A點正上方。如果還有比B點更高的點C，那么AC一定大于AB，這與AB距離最遠矛盾。所以B點一定是最高點，也就一定在凸包上。同理可證A點也一定在凸包上。<BR>　　TJU上的數據很弱，所以求出凸包以后，枚舉凸包上的點對就可以AC了。但是，當輸入的點全部分布在凸包上時，用枚舉法就會超時了。下面介紹一種“對踵點法”，求凸包以后的步驟的時間復雜度僅為O(n)。<BR>　　先給出“<B>對踵點</B>”的定義：如果過凸包上的兩個點可以畫一對平行直線，使凸包上的所有點都夾在兩條平行線之間或落在平行線上，那么這兩個點叫做一對對踵點。下面將證明最遠距離點對一定是一對對踵點。<BR><IMG 
src="vol1.files/1082_1.gif" align=right> 
　　觀察圖1，設∠1+∠2≤180°，∠3+∠4≤180°。那么如果∠1≥∠4，則由于∠1+∠2≤180°，一定可過B、E作兩條平行線使邊AB落在其中一條上；反之，則可過B、E作兩條平行線使DE落在其中一條上。也就是說，當一條線段截凸包所成的兩組“同旁內角”之和均不超過180°時，這條線段的兩個端點是一對對踵點。因此，若一條線段的兩個端點不是對踵點，則必有一組同旁內角之和大于180°。<BR><IMG 
src="vol1.files/1082_2.gif" align=right> 
　　再觀察圖2。因為有一組同旁內角之和大于180°，所以這兩個角中必有一個角大于90°（不妨設∠ABE&gt;90°）。這種情況下顯然有AE&gt;BE，因此BE不是最遠距離點對。也就是說，不是對踵點的點對一定不是最遠距離點對，所以最遠距離點對一定是對踵點。<BR>　　很顯然地，過一對對踵點一定可以作兩條平行線，使凸包的一條邊落在一條直線上。因此，我們設兩個指針，一條指向凸包的某條邊，另一個指針指向離這條邊最遠的點。這條邊的兩個端點與這個點都是對踵點，因此都可能是最遠距離點對。按順序移動邊指針并相應地移動點指針，當兩個指針繞凸包轉了一圈以后，答案就出來了。
<SCRIPT>detail 1084,"n因子最小正整數"</SCRIPT>
 
　　謝謝<B>Waterfish</B>指出我貪心算法的錯誤。其實這個題的正宗解法還是搜索。<BR>　　把一個數（大于1）分解質因數：a=p<SUB>1</SUB><SUP>k<SUB>1</SUB></SUP>*p<SUB>2</SUB><SUP>k<SUB>2</SUB></SUP>*...*p<SUB>n</SUB><SUP>k<SUB>n</SUB></SUP>，則a的約數個數為(k<SUB>1</SUB>+1)*(k<SUB>2</SUB>+1)...*(k<SUB>n</SUB>+1)。顯然，在約數個數相同的情況下，要使a最小，應有k<SUB>1</SUB>&gt;=k<SUB>2</SUB>&gt;=...&gt;=k<SUB>n</SUB>。因此，我們可以搜索每個質因數的指數，把上面的不等式當作剪枝條件。質因數只需用前trunc(log<SUB>2</SUB>100000)=16個即可。<BR>　　搜索出n因子最小正整數的質因數分解式后，剩下的就是高精度乘方和乘法了。計算乘方時，不要一個一個地把指數個底數相乘，這樣做太慢。比較快的方法是二分遞歸，比如計算2<SUP>9</SUP>，可以這樣：2<SUP>9</SUP>=(2<SUP>4</SUP>)<SUP>2</SUP>*2，其中2<SUP>4</SUP>=(2<SUP>2</SUP>)<SUP>2</SUP>，而2<SUP>2</SUP>=(2<SUP>1</SUP>)<SUP>2</SUP>，2<SUP>1</SUP>為已知。<BR>
<SCRIPT>detail 1085,"遞增序列"</SCRIPT>
　　記輸入序列為s，其長度為l。用nonzero[i]表示s[i..l]中第一個非零數的位置，規定s[l]=l。<BR>　　既然要求最后一個數最小，那么就從l 
downto 1枚舉最后一個數開始的位置，設當前枚舉到k。左邊的序列用DP解決。next[i]的含義如下：
<UL>
  <LI>如果在第i個數字處開始不是最后一個數，那么next[i]表示下一個數開始的位置；
  <LI>如果在第i個數字處開始的數是最后一個數，則next[i]=l+1；
  <LI>如果自第i個數字起的序列無法劃分，則next[i]=0。</LI></UL>從k-1 downto 
1枚舉i，依次計算next[i]。next[i]應滿足的條件是：
<OL>
  <LI>next[next[i]]&gt;0，即從next[i]開始的序列可以劃分；
  <LI>s[i..next[i]-1]表示的數小于s[next[i]..next[next[i]]-1]表示的數，即嚴格遞增；
  <LI>next[i]盡可能大。</LI></OL>因此可從k downto 
i+1依次枚舉next[i]，一旦有某個next[i]滿足前兩個條件，則next[i]就已算出；若k downto 
i+1的所有值都不滿足前兩個條件，則next[i]=0。若最后next[1]不為0，說明有解，按圖索驥地輸出，否則dec(k)，繼續循環。<BR>　　但若完全按照上述方法來做，程序在遇到3203400999這個數據時會輸出3,203,400,999，而顯然最優解應是320,340,0999。也就是說，此程序在枚舉k時并沒有考慮到前導的0。為解決這個問題，我們在枚舉i時加上一點判斷：如果從s[i]到s[k-1]的序列全為數字0，即nonzero[i]=k，那么直接令next[i]=l+1，否則再按上文所述計算next[i]。而在s[k]='0'時，直接跳過此次循環即可。<BR>　　枚舉計算next[i]時還有一點優化：初值不必一律取k。因為第一個數的位數無論如何不會超過最后一個數的位數，因此初值取k與nonzero[i]+l+1-k的較小值即可。<BR>　　經過這兩點改進，發現對于全0序列程序不會給出任何輸出。這是因為任一s[k]均等于0，循環均被跳過。因此對于全0序列要特殊處理。
<SCRIPT>detail 1087,"垃圾陷阱"</SCRIPT>
 
　　在以下的敘述中，g[i].time、g[i].life、g[i].height分別表示第i個垃圾下落的時間、吃下后可以增加的壽命、墊高的高度；update(a,b)表示if 
b&gt;a then 
a:=b。<BR>　　這道題可以用DP解決。用l[i,j]表示掉下來i個垃圾后，卡門爬上的高度為j時她最長的壽命。顯然l[0,0]=10。對于任一個狀態l[i-1,j]，若l[i-1,j]&gt;=g[i].time，說明這個狀態的卡門能夠堅持到下一個垃圾下落。在這種情況下，按以下兩種方法處理第i個垃圾，即進行狀態轉移：
<OL>
  <LI><B>吃掉第i個垃圾</B>，即update(l[i,j],l[i-1,j]+g[i].life)；
  <LI><B>用第i個垃圾來墊高</B>。令t=j+g[i].height，即把第i個垃圾用來墊高后卡門爬上的總高度。如果t&gt;=d，則卡門于g[i].time時爬了出來，否則update(l[i,t],l[i-1,j])。</LI></OL>　　若首次遇到某一個l[i,0]一次也沒有賦值，說明卡門不可能堅持到第i個垃圾下落，則她最多可以存活的時間為l[i-1,0]（即把前i-1個垃圾全吃掉后的壽命）。<BR>　　注意到在計算l數組的第i行時只用到了第i-1行，因此l數組可用滾動數組來實現。
<SCRIPT>detail 1090,"Symbol樹"</SCRIPT>
 　　首先澄清一下多叉樹的概念：多叉樹的子樹是有順序的。<BR>　　用f[n]表示有n個結點的多叉樹的數目，規定f[0]=1，則<IMG 
src="vol1.files/1090_1.gif" align=absMiddle>，其中i表示第一棵子樹中結點的數目。
<SCRIPT>detail 1094,"統計三角形個數"</SCRIPT>
 
　　首先看到題目中頂點的編號方式不利于解題，故將其轉換為坐標表示法，如原來的頂點8轉換為第4行第2列，即(4,2)。轉換方法如下：設頂點x的上方有t行，則t是方程t*(t+1)/2=x-1的正數解的整數部分（體會一下方程右邊-1的巧妙性）。于是，頂點x便轉換為(t+1,x-t*(t+1) 
div 
2)。<BR>　　下面進入正題。讀入被刪邊的時候，把這些邊分為兩類：水平的和斜的。在以下的敘述中，把朝上的三角形的上頂點及朝下的三角形的下頂點叫做三角形的<B>頂點</B>。依次統計頂點為(x,y)(1&lt;=y&lt;=x&lt;=n)的三角形。<BR>　　在統計頂點為(x,y)的三角形時，設兩個變量u、d，分別表示三角形頂點的對邊所在行號的最小值和最大值，初始時u=min{y-1,x-y}，d=n。然后根據被刪邊來確定以(x,y)為頂點的三角形中哪些仍然完整： 

<OL>
  <LI>假若某一條斜的被刪邊正好處于從(x,y)出發的兩條斜直線上，那么頂點的對邊在這條被刪邊以上（如果它在(x,y)的上方）或以下（如果它在(x,y)的下方）的三角形都不復存在了。因此，使用斜的被刪邊來縮小u~d的范圍。 

  <LI>現在，u~x-1和x+1~d的每一個值都對應著一個以(x,y)為頂點的三角形。下面就檢查一下這些三角形是否被水平的被刪邊破壞掉。最后剩下的三角形就是圖中存在的三角形，累計即可。
  <UL></UL>
  <SCRIPT>detail 1095,"Feli的生日禮物"</SCRIPT>
  　　再用一遍<A 
  href="http://purety.jp/akisame/oi/TJU/vol1.htm#1014">1014</A>中的化學術語：“一個2跟一個5反應生成一個0，因為2過量，所以照5算”。也就是說，因數5應是我們關注的對象。<BR>　　舉個例子來說明我的算法：假設要計算33!，首先把1至33的不是5的倍數的數的末位數相乘，取末位數。而剩下沒有乘的就是5,10,15,20,25,30，共6個（33 
  div 
  5=6）。把6個約數5提出來留到最后一起乘，剩下的又是計算6!，于是便看出這是一個遞歸過程，這也就是算法的框架。<BR>　　具體實現中有以下幾個小竅門： 
  <UL>
    <LI>計算1至n的不是5的倍數的數之積的末位數可以const，因為n的末位數與積的末位數之間存在對應關系。當然，n=0和n=1的情況例外。 
    <LI>因為乘以5之前和之后的末位數都是偶數，所以乘以5的效果與乘以8相同，即：2*5-&gt;6，4*5-&gt;2，6*5-&gt;8，8*5-&gt;4。 

    <LI>顯然這道題需要用高精度。不要圖省事而用字符串，因為字符串與數組相比，delete(s,1,1)這個操作太費時間。而且，我的經驗表明，用字符串會莫名其妙地WA掉。</LI></UL>
  <SCRIPT>detail 1099,"破解平方數"</SCRIPT>
  　　子集中元素之積為平方數，也就是對于任一質數p，子集中每一個數包含p的個數之和為偶數。用布爾變量b[i]表示子集是否包含第i個數，布爾變量a[x,i]表示第i個數是否含有奇數個第x個質數。可以列出以下布爾方程組： 

  <BLOCKQUOTE>a[1,1] and b[1] xor a[1,2] and b[2] xor ... xor a[1,m] and b[m] 
    = false<BR>a[2,1] and b[1] xor a[2,2] and b[2] xor ... xor a[2,m] and b[m] = 
    false<BR>... ...<BR>a[t,1] and b[1] xor a[t,2] and b[2] xor ... xor a[t,m] 
    and b[m] = false 
  </BLOCKQUOTE>其中b[i]是未知數。本題的答案，就是上述方程組的解的組數減1（空集不符合題意）。注意到所有方程的右邊均為false，因此這個方程組不會無解。<BR>　　那么如何求得這個方程組的解的組數呢？可以用高斯消元法。依次消去每一個未知數。消未知數b[i]時，若它的所有系數均為false，那么它是一個<B>自由變量</B>，也就是說，它是取true還是取false都可以，同時它已經不存在了，不必消去；否則找一個b[i]的系數不為false的方程，用它與其它每一個方程進行異或運算，再把這個方程本身刪除，這樣就消去了b[i]。因為當自由變量取特定值時，每個非自由變量都可由自由變量根據消去這個非自由變量時與其它方程異或的方程算出，所以方程組的解的組數就是2^自由變量個數。 
<!-- START HOME FREE FOOTER CODE --></OBJECT></LAYER>
  <DIV></DIV></SPAN></STYLE></NOSCRIPT></TABLE></SCRIPT></APPLET>
  <CENTER></CENTER>
  <DIV class=ad_text align=center>
  <SCRIPT type=text/javascript><!--google_ad_client = "pub-7093259457636557";google_ad_width = 234;google_ad_height = 60;google_ad_format = "234x60_as";google_ad_type = "text_image";//2007-10-01: 2style(2style.net)google_ad_channel = "5598176498";google_color_border = "191919";google_color_bg = "FFFFFF";google_color_link = "0000FF";google_color_text = "000000";google_color_url = "008000";google_ui_features = "rc:6";//--></SCRIPT>

  <SCRIPT src="vol1.files/show_ads.js" type=text/javascript></SCRIPT>
  <A href="http://2style.net/" target=_blank><IMG height=1 alt=2style.net 
  src="vol1.files/fstats.htm" width=1 border=0></A> </DIV><!-- END HOME FREE FOOTER CODE --></LI></OL></BODY></HTML>