CMU MSIT-SE 2015的青蛙题 FrogPond，求解

stellari 发表于 2015-7-1 22:54
这个算法仅适用于“第K次的落叶位置肯定大于前K-1次落叶的位置”的情况。而这道题的难点在于落叶的位置可 ...

是我疏忽了，青蛙还可以一次跳多步

满城尽带黄金甲 发表于 2015-7-1 22:59
这个倒是问到我了，这种case如果依然要这么搞的话，我的想法的话就是只能放弃primitive的int，弄个class/ ...

是的，一旦你想到point、interval之类的东西，马上就开始复杂了。一开始我也想O(N) dp，后来写着写着就觉得得用并查集了。。

zhuli19901106 发表于 2015-7-1 23:01
是的，一旦你想到point、interval之类的东西，马上就开始复杂了。一开始我也想O(N) dp，后来写着写着就觉 ...

又想了下不用啊……直接该位置+D，然后倒着往回set……碰到true停止

满城尽带黄金甲 发表于 2015-7-1 23:03
又想了下不用啊……直接该位置+D，然后倒着往回set……碰到true停止

我又加了个case，首尾都是true，中间可以存在false的。

满城尽带黄金甲 发表于 2015-7-1 22:49
并不需要O(ND)， 因为碰到下一个是true的话，那后面D个都已经设置了，不需要置位，整个循环下来，最多就 ...

你的意思我理解，但当“需要置位的范围内的第一个位置已经是true”时，这种情况下是不能跳过任何一个元素的，比如，现在咱们的bridge数组已经是

[1 1 1 1 1 0 0 0 0 0 0]
0 1 2 3 4 5 6 7 8 9 10

比如现在要把1~5的范围设为true。现在1已经是true了，能跳过1~5的置位么？不知道，必须要从1一直判断到5，才能发现最后一个数字是需要置位的。确实，总共只有O(N)次置位操作，但是在worst case下会进行O(N^2)次判断，所以总时间复杂度还是O(N^2)
你可能会说：“可以直接跳到需要置位的范围（也就是5）的开头”，但问题是怎么跳？现在你的代码里并没有保存“任意一段1序列末尾的位置”。这种跳跃是做不到的。

也就是说，这种算法至少在
A[0] = 0, A[1] = 1, A[2] = 2, ...，A[ i ] = i
这种情况下会达到最大时间复杂度O(N*D)。

zhuli19901106 发表于 2015-7-1 23:04
我又加了个case，首尾都是true，中间可以存在false的。

那感觉只能用某个数据结构去union了 ：（

满城尽带黄金甲 发表于 2015-7-1 23:11
那感觉只能用某个数据结构去union了 ：（

于是我们殊途同归T-T~

zhuli19901106 发表于 2015-7-1 23:12
于是我们殊途同归T-T~

请问用union find可以吗？
public int solution(){
                for(int i = 0; i < N; i++){
                        isLeaf[A] = true;
                        for(int j = A[i] - D; j <= A[i] + D; j++){
                                if(j < 0 || j > X)
                                        continue;
                                if(isLeaf[j])
                                        union(j,A[i]);
                        }
                        if(connected(0,X))
                                return i;
                }
                return -1;
        }
[/i][/i][/i][i][/i]
[i][i][i]A[/i][/i]的位置都是A【i】[/i]

georgmaster 发表于 2015-7-1 23:37
请问用union find可以吗？
public int solution(){
                for(int i = 0; i < N; i++){

我的解法就是并查集，不过当时思路比较乱，所以代码写的很繁琐。
补充：我发现我代码的一个错误，可以前后跳，我读题读错了以为只能往前跳。

不过并查集的思路是可行的，就是区间由 [A, A + D] 改为[A - D, A + D]，处理方法依然不变。

鉴于智商余额不足，懒得改了。。

zhuli19901106 发表于 2015-7-1 23:40
我的解法就是并查集，不过当时思路比较乱，所以代码写的很繁琐。
补充：我发现我代码的一个错误，可以前 ...

但是好像没有必要往后跳吧