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
