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

Posted by xiaodao
Category: Google Code Jam
Tags: 除草