简单DP + BFS
牌子之间两两组合出新牌子， 新产生的牌子只需与原始的号码两两组合即可，即，不用考虑两个新牌子组合的情况，因为两个新牌子组合的结果必然等价与一个新牌子和原始牌子组合的结果， 否则会超时。
很自然的就可以用类似BFS里的队列来做， 我由此引发的思考是， 这种新牌子和原始牌子组合到达新point， 和BFS的思想是十分一致的， 我可以把每一个原始牌子看作一个方向， 牌子号码的每一位是一维空间。 比如 01001 这个原始牌子， 对应了一个五维空间， 这个原始牌子的方向就是 ( 0, 1, 0, 0, 1 ) 。 题目就能抽象为， 给出一个B维的空间和可以走的E个方向， 问你能到达离某个点最近的维度。
Continue reading
好繁的一道题.. 看走眼了 1061才是数论题..才发现 思路:
区域看作一个Vertex, 对每个区域BFS求出能到达所有club的和最小值. 复杂度N2
Edge的构造: 一个region周围的点集按顺时针是 {p1, p2, p3 .. pk} 那么 (p1, p2) (p2, p3) … (p(k-1), pk) (pk, p1) 就是它的所有border, 其中任何一条边 (p[j], p[(j+1)%n]) 与也只与另外一个region’ 共享, 而region’ 做取边操作的时候, 这条共享边是颠倒的, 即 (p[(j+1)%n], p[j]) , 所以构造一个二维数组p[][], 上下三角形是对称的, 一对对称的元素就代表了相连的两个区域
club就存在所有靠着它的region内, 在这些region里面此club的步数都是0
细节:
以后这种繁题把变量名起的明白一点.. 多写点注释, 不然容易糊涂, 不太好写函数(其实可以.. 懒)
110行, 跑47ms, 还不错的样子..
Update: 这题数据比较弱, 用floyd简便很多, 因为为BFS准备比较麻烦, floyd直接开个数组全∞了事.. 复杂度N3
代码点下面 (没有任何可读性可言..)
Continue reading
