當遇到 3 2 1 1 2 4 2 1 1 2 3 這樣的情況下
只要把它當成 3 2 1 1 1 1 1 1 1 1 1 1 1 1 2 3
就可以發現我們只要從左右都試一次(z , z-1, z-2, …, 1)就知道z是不是他的層數
我們由最大可能開始向下, 即是 min(v[0], v[n-1]) , 一直試到 1.
如果 sum of a 是單數就一定沒有答案, 因為quote一定是雙數的

重點是在想解法時, 應先用多一點時間去簡化題目
不然我們只想到要證明 3 2 1 1 2 4 2 1 1 2 3 的正確性
而想不到把 3 2 1 1 2 4 2 1 1 2 3 簡化成 3 2 1 1 1 1 1 1 1 1 1 1 1 1 2 3
問題就會解不開

More...

icpc 北京 2015 的題目. 我自己想不出來, 看完別人答案再加一些筆記.

• 第一點是確定答案是可以先用第二種方法,再用第一種方法得出. 想一想覺得正確, 但想不到如何證明.(事實上是對的)
• 而且第二種方法最多只需用六次就可以得出結果
• 第二點是如何儲存第二種方法的使用結果, 他巧妙地用了數位去代表原本數值, 然後用該數位的數值代表了他的改變. 不一定要六進制也可以做到.
• 第三點是如何算出第一種方法要用多少次. 如果是我的話, 我會把字串做出來, 再一個個算吧, 很可能 TLE. 它直接利用了原本字串和目標字串的關係, 直接計算目標字串 某個字 的數量減去 對位並已轉換的 數量

More...

這是別人的解釋

可是看了別人的解釋之後, 我還是花了很多時間才明白, 所以記一下理解的方法.

若果單是第二層的點轉到最頂層是很容易明白的, 可是把第三層的點如何才能轉到最頂層呢?

比較容易理解(想出上面公式的正確性)的方法如下.
就是不停把 X 轉到自己父節點的位置, 直到自己是根節點.

當我們把 X 轉到父節點時, 他的樹結構和原本的樹是差不多的, 不同就是他多(左移/右移)了一步及他的其中一個子樹會移到父節點下面.

而左移/右移的次數對應 dl, dr.

而計算高度時, 我們會用到hl, hr, dl, dr這些狀態, 雖然我們不能直即得出轉到根節點時的狀態值, 但我們知道把 X 轉到父節點時的狀態轉變.
把父節點轉到根節點時的狀態值加上由 X 轉到父節點時的狀態轉變, 就是 X 轉到根節點時的狀態值.

因此我們可以把它反過來, 由根節點不停計算下去, 把子節點轉到父節點的狀態轉變加下去.\

More...

就是 dfs. 由左上到右下. 一行一行地走.
要小心輸出格式, 我把 There are %d solution(s) for layout 那一句在 uDebug 比較了很久, 明明是一樣的句子, 但他就是顯示不同, 最後用他的句子就過了. 可能是多了一些奇怪字元.

More...

我自己用的方法是把所有可能的組合列出來, 再找最接近的那一個.
想起來比較簡單, 不過慢一點.

正確的方法是dp, dp[n] 中放的是最接近 n 的組合的數值.
除了 dp 之外, 他有一個假設, 如果 r 是最接近 n/2 的值, 那會有 n-r 的組合, 而 r 和 n-r 兩者之間一定有一個比 n/2 少. 所以只要由 n/2 向下找. 另外次序一定要由大到小, 不然會出現錯誤, 除非用兩維列陣.

More...

這題最麻煩的是理解題目, 很難明白. 我是看了別人答題才明白那段文字的意思. (code can explain itself)

重點是圖片下面那一段介紹.

That is, if there are disks each of which requires 2^k+1 moves to reach destination, then number of disks each
of which require 2^k moves to reach destination is p−3+kCk (number of combinations of (p−3+k) things
taken k at a time)

如果當前所有 disks 之中有disk要用到 2^(k+1) 的次數去移動.那當中有p−3+kCk 的disk要用 ２^k 的次數去移動. 由此可見當中是有遞進的關係.

設 n(k) = p−3+kCk = disk 的數目

• n(k+1) = n(k)(2^k) + (n(k+1) - n(k))(2^k+1)
• n(k) = n(k-1)(2^k-1) + (n(k) - n(k-1))(2^k)
• …

More...

數學苦手 ||Φ|(|´|Д|`|)|Φ||

More...

本來用 OOP 的方法去寫的, 不過因為不太熟 c++ 的 OOP (平日多用 java, python, nodejs), 所以還是用不美的方法解決了.

不過之後還是有再複習一下 c++ 的 OOP, 再寫一次應該不成問題.

More...

這題有一點要注意, 那就是每個島之間的最短距離可以是 點到點 , 也可以是 點到線 的.

另外, 在列舉島的邊線時記得把 n-1 to 0 的那一條線也加入其中, 而兩邊陸地不用. 我被這點卡了很久, 因為錯處太少, 反而難找出來.

More...

這一題和 uva910 一樣, 只是要多了要判斷能不能走那一路, 以及答案要用 long long, 不然會 overflow.

More...