tioj 1497 喝醉的宿主

這是一題基礎的suffix array，會後綴陣列的話就簡單簡單，不會就悲劇＝＝

想法很簡單，想要得到2^k長度的字串的排名，只要知道2^(k-1)的排名就可以了。

而一開始你可以直接知道長度1的排名，所以就可以推廣出其他的長度了。

Code 有點醜，因為一直想要比shik的code短XD

http://codepad.org/kQJJW39g

tioj 1712 Tentacle Tree

昨天想了半天想不出來，早早睡覺，一早起來突然頓悟了XD

題目就是給你一棵有權重的樹（單向，只能向葉子走），然後給定每一點的K值，代表可以走的距離，問哪個點可以被最多點走到。（節點數 <= 200000 ）

原本一直在想要怎麼把前面的K值全部扣掉當前距離，結果發現根本不需要這樣，因為直接反過來用加的就可以了XD。

原本：K1-d1-d2, K2-d2, K3
                     等價於
後來：K1 , K2+d1, K3+ d1+ d2

其實就這樣啦，那時候本來想要用 HEAP ，只是不會判斷如果有些點被丟掉之類的要怎麼辦，所以就直接離散化，寫BIT。

http://codepad.org/vohf3pqv

tioj 1616 快樂植樹遊戲

其實這是一題痛苦的質數遊戲
一看之下就覺得是game theory的題目
好像是先找到斷點，再用NP規則回推就可以知道了
但想了想，發現會找不到斷點OoO
怎麼辦勒！？這時妁豔神出現把我捏爆了XD

重新敘述一下題目，第一個戳 0 ，接下來輪流戳一個比前一個數大的質數，但是之間的差不能大於K，問不能再戳下一個點的是先手還是後手。（理想情況下）

其實這題要換一個想法，因為先手一定要戳 0 ，所以一點先手的優惠都沒有，其實後手比較像先手，這時我們就來假設在很遙遠的某個點是斷點，種在那裡的人就 win 了，但這要是能夠踩在那裡的人才是贏的，這樣我們就來看，會不會在某個數以後，先手根本就踩不到任何一個點（或是說他沒辦法選擇，若某點是win點，後手必定可以先踩到），只能任後手宰割，於是我就記錄，先手可以踩到的範圍（或說先手可以選擇比後手早踩到的範圍），如果到了後面發現，先手可以踩到的範圍是零，那就代表先手輸定了，但是其實有些情況你會發現，找不到讓他範圍變零，所以我假設這些情況先手會贏，而這種情況只有十種。所以其實我還是用猜的，只是就剛好也AC了XD

http://codepad.org/55dRfIfj

tioj 1403 超車問題 Extreme

這題分成兩個部分
第一部分：線段樹（BIT）
第二部分：堆

第一部分因為 v 的範圍小小的，直接counting 就可以了
第二部分則蠻麻煩的，必需要把兩台車交換，而且比較的時候（不能用double）會overflow一小點點，害我debug de了很久 T T
不太懂的話看code吧，我很辛苦的打了一堆註解XD

http://codepad.org/xjYeIbaS

Codeforce 168E Wizards and Numbers

煩人數學題。。。
本來直接用NP算他，結果TLE + +
首先，先用 dfs( b, a%b ) 算一下，看會不會贏，
如果dfs( b, a%b )會輸，那就代表這個壯況會贏
如果dfs( b, a%b )會贏，那就知道弄成那個狀況的人就贏了
如果希望自己贏，那麼走的步數必定要是偶數。
a = q*b + a%b;
將 q 轉為 y1*（b^x1） + y2*（b^x2） + y3*（b ^x3） + ... + yn
若 sumof( yi ) 是偶數，則先手贏
若 sumof( yi ) 是奇數，則後手贏

如果 b 是奇數，就輕鬆了，
若含b的多項式係數和是偶數，yn是偶數，那麼 q 為偶數。-> 2 | sumof( yi )
若含b的多項式係數和是奇數，yn是奇數，那麼 q 為偶數。-> 2 | sumof( yi )
若含b的多項式係數和是偶數，yn是奇數，那麼 q 為奇數。-> sumof( yi ) %2 != 0
若含b的多項式係數和是奇數，yn是奇數，那麼 q 為奇數。-> sumof( yi ) %2 != 0
其實很好證，若q是偶數，不是奇（係數和%2=1）加奇，就是偶（係數和%2=0）加偶

但如果 b 是偶數，就麻煩了，
所以就把b改成奇數（OoO）也就是改成 (b+1)（怕改太多會壞掉）
將 q 轉為 z1*（ (b+1)^x1 ） + z2*（ (b+1)^x2 ） + z3*（ (b+1) ^x3 ） + ... + zn
若且為若含b+1的多項式係數和是偶數，zn是偶數，那麼 q 為偶數。
若且為若含b+1的多項式係數和是奇數，zn是奇數，那麼 q 為偶數。
若且為若含b+1的多項式係數和是偶數，zn是奇數，那麼 q 為奇數。
若且為若含b+1的多項式係數和是奇數，zn是偶數，那麼 q 為奇數。
但要怎麼推出 sumof( yi ) 呢？
其實重點只在於 zn，因為前面的係數和一定是偶數（b+1的任意次方係數和為偶數）。

http://codepad.org/EvH8mbUS

tioj 1684 圓桌武士

題目：給你一個無向圖，尋找不存在奇環中點的數量

想到環就想到BCC，你可以確定找到若兩個點不在同一BCC中，則他們不會在同一個環裡
但是這題比較麻煩，因為這題是邊的BCC，你必須找到AP，並得到這個BCC的邊集合。
 找BCC很簡單，DFS出去，如果往下走不能走到比自己高的點，這個點就是一個AP，

但比較麻煩的是要怎麼找BCC的邊集合，我查網路看到的方法是開一個Stack
把走了的邊加進去，如果碰到一個割點，就開始拿出裡面的邊，直到那個邊還有這個割點。

不太確定為什麼這樣是對的，但是大概有點理由，因為這是顆DFS樹，你一個邊一個邊加
這樣邊就會是待在裡面，除非已經被拿出來了，而被拿出來就代表找到了一個AP
那麼那些被拿出的邊也不可能會在後來的BCC當中，所以感覺上合情合理～

至於為什麼存點是不行的？（我原本就是寫找點集合）那是因為有些割點是不能拔掉的
但有些卻必須要拔掉，你不知道要拔還是不要拔，所以那樣寫是不好的。

當你找的一個BCC 後，你就要來判斷他裡頭有沒有人在奇環裡，這裡有個神祕的關係：
 如果這整個BCC是一個大奇環，這裡頭所有的點都在奇環當中。
但若這整個BCC是一個大偶環，若其中有一個小奇環，則其餘的點必定為奇數點，且仍形成環，故若其中有一奇環，則BCC的所有點都位於奇環中。

 最後就是要怎麼判斷他是否在奇環在裡頭，有一個很不錯的辦法，就是把點染色，每個有相互連接的點要連成不同的顏色，如果找到有一已著過色，相連且顏色與己相同的點，則這BCC中便有奇環。

 http://codepad.org/1Jnw5MbT

Codeforce 168D Wizards and the Huge Prize

這題題目好難懂＝＝
本來看都看不懂，比賽的時候也沒寫出來
重新翻譯一下題目好了～

給定 N, L, K 代表，要拿的數量，至少要獲得幾個值，初始值
給你 N 個數，代表獲得這數字的機率
再給你 N 個數，代表獲得的數字Ai

問，得到至少 L 個，且 sum( Ai ) 加上 K 不小於零，的機率為多少？
（ N, L, K, Ai <= 200 ）

由於數字小，而且每個數字都要拿
所以可以直接用O( N^3 ) 的DP就可以了
三維的DP，分別為：拿幾個，獲得幾個，目前的數字和

http://codepad.org/V5oSOnzv

tioj 1573 15-puzzle

IDA*
我從以前就不大會寫= =
今天終於比較會了一點點
有兩種寫法：
第一個是limit一加一的遞增，這樣的寫法跑起來較慢，但是寫起來很快
另一個是得到limit應該增為多少，這樣可以跑的較快，但不太直觀，不好寫
而這一提有兩個癥結：
第一個要知道怎麼判無解（google一下）
另一個就是 h 函數要寫的有效率一點（而且不能寫錯阿）
-> 看除了空格以外，到達該到的地方的曼哈頓距離和
（我一直以為連空格也要算，答案雖然會是對的（如果寫第二種寫法的話），但會跑超級久，徹底 TLE，改成第一種的時候，才發現原來我的啟發式函數寫錯了= =）

第一種：http://codepad.org/h1kyWM7c
第二種：http://codepad.org/ZUSDRPFw

tioj 1402 淹水問題

這題其實不難啦（比起樹分治）XD
可是我還是想了很久，一開始一直在想用DFS來解這題
亂想一通，本來的想法是，用heap存目前最低的地方
並從其開始，往外找最低的牆壁，然後把有幾塊乘上高度差
一直這樣做下去，結果發現這樣是O( (nm)^2 ) 徹底TLE（nm＝10^5）
被捏了一下（從邊界做），才了解 _ _
慨念就是從邊界開始，（用heap存邊界）
由最低的邊界開始（因為水會從最低的流出去）
不斷的把邊界向『內』擴展(?!)
碰到比較低的就把高度差加進ANS，並將其填滿
一直做到邊界內沒有任何其他的地為止

http://codepad.org/pYMZpj1l

tioj 1696 J122園保衛戰

又是一個樹分治XD
分治好難好難好難好難寫
我決定要很久不要碰他XDDD
這一題跟前一題差不多
只是我卡了很久很久（也是跟前一題差不多）
重心真的要好好的去找阿～T T
還有邪惡的組語優化（選訓營中的神人教我的）
這題長得跟前一題幾乎一樣（我寫了一整天，可恥X{）
做法唯一的差別是這題沒有用雙指針
有人寫BIT，但直接用像counting sort那樣就可以了
跑過去之後，加上漫長的debug，就AC了XD

http://codepad.org/ebDR0P6n

POJ 1741-TREE

樓教主的男人八題其中一題!!!!!
是一題樹分治（據說是樹分治中的最簡單題）
但對我來說還是極難阿～～～～寫了好久

來說說什麼是樹分治好了
平常碰到的分治題，都是把它切切切切切切切
變得小小軟軟，就可以快速的解決（最差情況是切一次變兩塊）
樹分治也是一樣的，重點在於你要切的好
所以就要選擇切那棵樹的重心，這樣剩下的子樹會長得最平均
也就不會因為人品過低，出現很糟糕的情況了（拔了一個點，仍然剩下一棵樹）
而重心是啥勒？就是『把一個點拔掉後，讓剩下的最大的子樹，節點數最小的那個點』
這樣就可以較為平均的分成一些更小的樹，而使一切變得更簡單～

有了樹分治的概念後，就可以快樂的進入這題了
首先要先想想為什麼會用到分治的概念？
如果樹長得一副星狀樣，重心連出去的所有子樹都只有一個節點，
就可以 O(n) 快速求出（先dfs求距離，然後使用爬行法）
但重點就是他不是星狀樣阿！怎麼辦勒？？？
首先，先假設他是星狀樣，求一次答案，這個答案當然是錯的
因為他少算了『一些』子樹自己跟自己的配對（不然我就不用再這編寫解題報告了XP）
所以我的分治就是再去算一下子樹中的配對然後把它加回來
但這樣還是錯的，因為他只有少算『一些』配對（不是全部都少算）
所以要再把那些多算了的扣掉。由於有點複雜，下面會重寫一次流程

任務：尋找一棵樹中的配對數量
1. 找出重心
2. 假裝是個星狀圖，找出配對數量
3. for 所有的子樹
    1) 加上子樹的配對數量
    2) 把原本就算過的數量扣掉

有點麻煩，但是這樣就AC了XD

http://codepad.org/id4GK8qM

tioj 1514 橫掃射擊場

看到小包寫我才去寫的，這真的是一題好題
我終於把歐拉跟費馬這兩個人做的一大堆事中的一小部分弄懂了

PHI函數：

定義：phi(n)=1~n與n互質的個數
特性：
1. p為質數，phi(p)=p-1;
pf: 1~n-1都跟p互質

2. p為質數，phi(p^k)=p^(k-1) * (p-1);
pf:  有p^(k-1)個數是p的倍數，但其餘的(p-1)*p^(k-1)個數都不是，所以都跟他互質

3. p為質數，phi(p^(k+1))=phi(p^k)*p
pf: 因，phi(p^k)=p^(k-1)*(p-1); 且，phi(p^(k+1))=p^k*(p-1);  故，phi(p^(k+1))=phi(p^k)*p;

4. 若(a,b)=1，phi(a*b)=phi(a)*phi(b);
pf: 好難證...

5. 若x=p1^k1*p2^k2*...，則 phi(n)=n[ (p1-1)*(p2-1)*(p3-1)*... ] / [ p1*p2*p3*... ]
pf:用三跟四，就可以容易的證出來，但有點長...

定理：
1. 歐拉費馬定理：a^(phi(m))%m=1（麻麻煩煩）
2. 費馬小定理：a^(p-1)%m=1（用歐拉費馬證）

介紹完可愛的phi，就來講解這題
這題其實就是要用我剛剛提到的東西歐～（（不然我提屁阿＋＋
題目好像很複雜，但稍稍想一下，就可以轉變成求1~n中有幾組數字互質
（因為，當某組（x,y）互質時，他們就不能約分成另一組整數的（x', y'））
所以其實就是求phi(1)~phi(n)的總和嘛～easy，但重點是要怎麼很快的求＝＝
你很快就會發現，因為他有phi(x)= x*[ (p1-1)*(p2-1)*(p3-1)*... ] / [ p1*p2*p3*... ]的性質
這時你就可以用偏廢的質數篩法，去建出phi(1)~phi(n)的值，約O( n^(3/2) )或小一點吧？！＠＠
其實這樣寫在加上一些簡陋的加速，就可以過了，差不多會是排名的最後一名XD
但是由於最後一名看起來過廢， 所以你決定要加速。你想把普通的篩法改成更快的線性篩法。
而這時，你就會開始想線性篩法怎麼寫...
a. 若是質數，就把它放進質數箱子裡。
b. 跑過所有質數箱裡有的東西，乘上當下數字
    1) 若超過上限就break
    2) 把那個數字打勾 <- 意味著不管如何都要打勾那個數字，如除4*2，無其他方式乘出8
    3) 若當下數字是當下質數的倍數就break（4*2後, 4*3是多餘的，因之後的6*2就會做到）
想完了後，你就發現這根本就是你要的阿！！因為每一個數字都會被做出一次，剛剛好O(n)這樣就可以超迅速跑完了！你開始動手把『線性篩法』變成『線性產phi法』
a. 若是質數，把它放進質數箱子中，順便用特性一求得他的phi值
b. 跑過所有質數箱裡有的東西，乘上當下數字
    1) 若超過上限就break
    2) 若當下數字是當下質數的倍數，用特性三與四，得到數字phi值，並break
    3) 把那個數字打勾，並順便用特性四得到phi值
再加一些瑣碎小東西，於是你便AC了

http://codepad.org/hJvP6x3d

UPRC 1151 宴會問題

題目換個說法：A+B+C=m, A>=ai&&B>=bi&&C>=ci, 的數量為MAX
PROCEDURE:
1. 枚舉A（本應枚舉0~10000，但若ai+1>A>ai，則A=ai會更好）-> O(n)
       1) 跑過所有的，把合格的加進來（合格就是A>=ai而且A+bi+ci<=m，第一個很合理，而第二個勒，是因為之後會有m-A-bi要大於ci不然加了也沒有意義，純屬加快用的）
       2) 把合格的進行排序，照b的大小，越大越前面
       3) 接下來，照著b一個一個用BIT查『小於等於m-A-bi』的ci的數量，而且換下一個的時候，就要先刪除這一個，因為儘管那個ci可能很小，但他相連的bi一定會大於之後的bj（由大到小排序）所以不能算進去。
2. 印出解答，然後就AC了，耶XD

ps. bit加一是為了讓他不會壞掉，因為如果是零就會炸掉 boom

http://codepad.org/vUuQP5ai

卡特蘭數

卡特蘭數：他是一串數列

來歷：只能往右走或往上走，從左下走到右上（正方形），不能超過對角線的種類數。 

遞迴式：CAT n+1 = SUM ( i = from 0 to n ) CAT i * CAT n-i

一般式：CAT n = 1/(n+1) * (C 2n取n)

帥氣遞迴式：CAT n+1 = (4n+2)/(n+2) * CAT n

要說的是他的應用和廣義的卡特蘭數：（這完全是我胡亂思想出來的，有錯請跟我說）

1.n*n正方形，不超過對角線的走法種類（基本）

2. n對括號可以產生的正確匹配方式種類數（簡單）

『解說：（ 是往右走，）是往上走，其他跟 (1) 一模一樣』

3. n個節點產生的二元樹種類數（困難，請大神不要嗆我X{）

『解說：首先要先知道n個節點完整的二元樹會有n+1個空位（空位定義：上方有節點但此地無節點），pf: n=1，有兩個空位，每增一個節點，會多一個空位，故得證。接下來要靠想像力了，我有解說啦，可是沒有圖，真可惜～』

詳細講解：

        有一個空圖。放一個節點＝往右走，放一個空位＝往上走。

        pf: 如果放的空位比節點多，這個圖就會是一個『完整』（ != 完全 ）的二元樹，也就是無法在繼續放點了（看我前面的pf吧），所以不能超過對角線，這樣就對應到 (1) 啦～開心XDDDD

好，再來就要說今天比賽中的三元樹了，其實網路上真的沒什麼廣義卡特蘭數的講解，所以一切都是從我小小的大腦胡亂思考而成的，請不要把我嗆爆XD

廣義卡特蘭數：原本是『向上走的<=向右走的』，但這裡乘上一個可愛的常數 k （好啦，他不可愛）變成『向上走的<=向右走的*k』，所以本來的正方形也變成矩形了，很棒吧～XD

一般式：CAT n (k) = 1/( (k-1)n+1 ) C kn 取 n

神奇遞迴式：自己不會算喔！

應用：n個節點可產生的k元樹個數。

『解說：跟剛剛的二元樹情況其實很像，只是節點數 n 的k元樹，空位數為 kn+1，證明方式依然相同，而且想法其實也是一模一樣的（事實上，我是為了想這題，才會想剛剛那樣的解釋方式）』

tioj 1396 線段覆蓋

我被騙了OO
我居然寫了一棵線段樹，結果還WA＝＝
實在是太愚蠢了T T
據說水水的，其實只要sort一下，greedy就AC了
SORT: 照起點排序
GREEDY: 盡量讓線段終點越遠

http://codepad.org/tkY1DdUa

tioj 1325 倍因道extreme

超級暴力就AC了= =

首先基於某個greedy定理：
從小到大，如果『倍數』比『被打勾的因數』多，就把它打勾～
這樣會是最大值，因為數字越小倍數就越多，所以好像是這樣...
然後就可以用它來DP，據說有很快的作法，但我不會XD
而且亂寫就過了XDDDD( 只是漏打一行WA了一兩次XP )

http://codepad.org/RA7nJfhK

Codeforce 145C Lucky Subsequence

每次寫數學題都寫到快瘋掉，麻煩死了...
可是這題code很短，很可愛XD
但卻包含很多的東西：
1. 模逆元 2. 求nCm 3. 奇怪的dp( "F" reak )
模逆元很好寫，就用簡單的延伸輾轉相除法（ext_gcd）
C的話可以用漸進式縮成一行，看起來很屌
F的話比較酷，前面都很好想，就F很難想。
我想到的就是把全部分成，lucky跟unlucky。
lucky的存每一種有幾個，unlucky就只要存有幾個
而所有的可能，就是
設unlucky有 n 個，lucky有 l 種
for( i=  0~l ) n C k-i ＊ F[ i ] 全加起來＝ANS
F[0]=1
F[1]=ty1+ty2+ty3...
F[2]=ty1*ty2+ty1*ty3+ty2*ty3...
....

http://codepad.org/ADtGgdBQ

tioj1291 N箱M球

考慮用 j 個球『塞滿』 i 個箱子時，假設已知道小於 i 或小於 j 的所有情況
那麼就可以透過新放的那個是要自己在一箱裡，還是跟著別人這 2 種情況
得知當下的種類數

自己在箱子裡：( i-1 , j-1 ) 的種類
和別人在一起：( i , j-1 ) 的種類＊可以放在 j 個地方

http://codepad.org/z4F0C2aW

tioj1483 電腦檢查

BIT。。。。。
重點就是要先排序
因為糟糕度小的不會蓋到糟糕度大的
而且糟糕度一樣的時候要特別判斷：
        曼哈頓距離越遠就要越慢做
至於要怎麼做？
insert( x,y ) 就是找出(1~x)*(1~y)有幾種 +1 （在後面都增加一位）
query( x,y ) 就是得到( 1~x )*( 1~y ) 有幾種

ps. 用排容會用到相減，然後模完會變負的，就爆了～～

http://codepad.org/vbNrFAGa