這是一題基礎的suffix array，會後綴陣列的話就簡單簡單，不會就悲劇＝＝
想法很簡單，想要得到2^k長度的字串的排名，只要知道2^(k-1)的排名就可以了。
而一開始你可以直接知道長度1的排名，所以就可以推廣出其他的長度了。
Code 有點醜，因為一直想要比shik的code短XD
http://codepad.org/kQJJW39g
2012年3月31日 星期六
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
題目就是給你一棵有權重的樹（單向，只能向葉子走），然後給定每一點的K值，代表可以走的距離，問哪個點可以被最多點走到。（節點數 <= 200000 ）
原本一直在想要怎麼把前面的K值全部扣掉當前距離，結果發現根本不需要這樣，因為直接反過來用加的就可以了XD。
原本：K1-d1-d2, K2-d2, K3
等價於
後來：K1 , K2+d1, K3+ d1+ d2
其實就這樣啦，那時候本來想要用 HEAP ，只是不會判斷如果有些點被丟掉之類的要怎麼辦，所以就直接離散化，寫BIT。
http://codepad.org/vohf3pqv
2012年3月30日 星期五
tioj 1616 快樂植樹遊戲
其實這是一題痛苦的質數遊戲
一看之下就覺得是game theory的題目
好像是先找到斷點，再用NP規則回推就可以知道了
但想了想，發現會找不到斷點OoO
怎麼辦勒！？這時妁豔神出現把我捏爆了XD
重新敘述一下題目，第一個戳 0 ，接下來輪流戳一個比前一個數大的質數，但是之間的差不能大於K，問不能再戳下一個點的是先手還是後手。（理想情況下）
其實這題要換一個想法，因為先手一定要戳 0 ，所以一點先手的優惠都沒有，其實後手比較像先手，這時我們就來假設在很遙遠的某個點是斷點，種在那裡的人就 win 了，但這要是能夠踩在那裡的人才是贏的，這樣我們就來看，會不會在某個數以後，先手根本就踩不到任何一個點（或是說他沒辦法選擇，若某點是win點，後手必定可以先踩到），只能任後手宰割，於是我就記錄，先手可以踩到的範圍（或說先手可以選擇比後手早踩到的範圍），如果到了後面發現，先手可以踩到的範圍是零，那就代表先手輸定了，但是其實有些情況你會發現，找不到讓他範圍變零，所以我假設這些情況先手會贏，而這種情況只有十種。所以其實我還是用猜的，只是就剛好也AC了XD
http://codepad.org/55dRfIfj
一看之下就覺得是game theory的題目
好像是先找到斷點，再用NP規則回推就可以知道了
但想了想，發現會找不到斷點OoO
怎麼辦勒！？這時妁豔神出現把我捏爆了XD
重新敘述一下題目，第一個戳 0 ，接下來輪流戳一個比前一個數大的質數，但是之間的差不能大於K，問不能再戳下一個點的是先手還是後手。（理想情況下）
其實這題要換一個想法，因為先手一定要戳 0 ，所以一點先手的優惠都沒有，其實後手比較像先手，這時我們就來假設在很遙遠的某個點是斷點，種在那裡的人就 win 了，但這要是能夠踩在那裡的人才是贏的，這樣我們就來看，會不會在某個數以後，先手根本就踩不到任何一個點（或是說他沒辦法選擇，若某點是win點，後手必定可以先踩到），只能任後手宰割，於是我就記錄，先手可以踩到的範圍（或說先手可以選擇比後手早踩到的範圍），如果到了後面發現，先手可以踩到的範圍是零，那就代表先手輸定了，但是其實有些情況你會發現，找不到讓他範圍變零，所以我假設這些情況先手會贏，而這種情況只有十種。所以其實我還是用猜的，只是就剛好也AC了XD
http://codepad.org/55dRfIfj
2012年3月29日 星期四
tioj 1403 超車問題 Extreme
這題分成兩個部分
第一部分：線段樹（BIT）
第二部分：堆
第一部分因為 v 的範圍小小的，直接counting 就可以了
第二部分則蠻麻煩的，必需要把兩台車交換，而且比較的時候（不能用double）會overflow一小點點，害我debug de了很久 T T
不太懂的話看code吧，我很辛苦的打了一堆註解XD
http://codepad.org/xjYeIbaS
第一部分：線段樹（BIT）
第二部分：堆
第一部分因為 v 的範圍小小的，直接counting 就可以了
第二部分則蠻麻煩的，必需要把兩台車交換，而且比較的時候（不能用double）會overflow一小點點，害我debug de了很久 T T
不太懂的話看code吧，我很辛苦的打了一堆註解XD
http://codepad.org/xjYeIbaS
2012年3月28日 星期三
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
本來直接用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
想到環就想到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
本來看都看不懂，比賽的時候也沒寫出來
重新翻譯一下題目好了～
給定 N, L, K 代表，要拿的數量，至少要獲得幾個值，初始值
給你 N 個數，代表獲得這數字的機率
再給你 N 個數，代表獲得的數字Ai
問，得到至少 L 個，且 sum( Ai ) 加上 K 不小於零，的機率為多少？
（ N, L, K, Ai <= 200 ）
由於數字小，而且每個數字都要拿
所以可以直接用O( N^3 ) 的DP就可以了
三維的DP，分別為：拿幾個，獲得幾個，目前的數字和
http://codepad.org/V5oSOnzv
訂閱：
文章 (Atom)