Google Code Jam 2014 Round 1B

Problem A. The Repeater

Brief description:

略。)

Analysis:

… 中位數。
https://gist.github.com/lychees/3c9cc3c5ef900d6cfb48#file-a-cpp

Problem B. Rural Planning

Brief description:

。。給定 A, B, k。。。問所有 a&b < k 的數對有多少種(滿足 0 <= a < A, 0 <= b < B)。

Analysis:

普通數位 DP。。。。
f(i, b0, b1, b2):
i:當前第 i 位,從高往低。
b0:當前 a1 & a2 的結果是否已經小於 k 、用於討論轉移。
b1、b2:後續對 a1 和 a2 是否已經放鬆位限制。

https://gist.github.com/lychees/3c9cc3c5ef900d6cfb48#file-b-cpp

Problem C. The Bored Traveling Salesman

Brief description:

給定一個有向圖,每個結點一個編號,求不進入任何一個結點兩次(可返回任意多次),遍歷所有結點的字典序最小的方案。

Analysis:

。就是求一顆有向樹。。枚舉根。。貪心每次找當前生成樹集合中。。一個字典序最小的可達點。。。
。。這樣可能會導致某些點重複進入兩次。。。

。於是我們維護一個棧。。表示根到當前結點的路徑。。只有棧中結點和沒有訪問結點在一個聯通塊的時候。。
。。。當前所選結點才是合法的。。。
。。其次如果棧中有多個結點可以到達該結點。。退回到最深的位置。。。以保證棧中結點儘可能多。。
這樣做總是可以找到一個合法訪問結點。。因此實際不需要枚舉根。。。。

實現的時候用一個 dep[] 數組記錄當前每個結點的所在棧中的深度。。
= 0 表示未訪問。。
= INF 表示已經彈出。

https://gist.github.com/lychees/3c9cc3c5ef900d6cfb48#file-c-cpp

External link:

https://code.google.com/codejam/contest/2994486/dashboard#s=p0