PUZZLEUP 2015

lastwinner

newkid 发表于 2015-9-2 23:13
#6 CHESS COLORS

You have an 8x8 table on a computer screen with all squares colored to white. In  ...

好古老的智力游戏，个人比较怕这类游戏，随便玩玩的话，简单的还能凑合过，难度稍大就可能半天过不了了

lastwinner

题5的一个例子
A-----B
|       |
C-----D

显然AD和BC之间还各需要一条线，一个走方形内部，一个走方形外部，就可以减少一个交点了

newkid

lastwinner 发表于 2015-9-4 12:30
题5的一个例子
A-----B
|       |

你把D放到三角形ABC内部，就不用曲线了。其实和你那个四边形是拓扑等价的。

newkid

第六题的SQL解法思路：

方块最终颜色由被覆盖次数的奇偶性决定。            
最终布局只和哪些块被选中有关，和选择顺序无关。
一个块最多选中一次，多于一次无意义。         

把每个方块看作二进制的一位，颜色取反即XOR操作。事先算好所有点的XOR掩码。

BITXOR(x,y) = (x + y) - BITAND(x, y) * 2;

〇〇

newkid 发表于 2015-9-5 03:31
第六题的SQL解法思路：

方块最终颜色由被覆盖次数的奇偶性决定。            

最少n*n/2

lastwinner

newkid 发表于 2015-9-5 03:24
你把D放到三角形ABC内部，就不用曲线了。其实和你那个四边形是拓扑等价的。

嗯，这倒是对的
不过对于5个点甚至更多点的时候，也适用？

newkid

lastwinner 发表于 2015-9-5 18:47
嗯，这倒是对的
不过对于5个点甚至更多点的时候，也适用？

当然，140楼已经把5~10个点的情况画出来了，你没看？
但是再多的点是否还能保持直线，就不知道了。

newkid

〇〇 发表于 2015-9-5 07:37
最少n*n/2

我前面已经说了选择所有黑格就行，你是在重复我们已知道的信息，还是有办法证明最小？

lastwinner

newkid 发表于 2015-9-5 20:17
当然，140楼已经把5~10个点的情况画出来了，你没看？
但是再多的点是否还能保持直线，就不知道了。

我看了，但是我没法笃定那就是最优的解法，而且对于多于5个点的情况也一并适用

lugionline

lastwinner 发表于 2015-9-6 00:05
我看了，但是我没法笃定那就是最优的解法，而且对于多于5个点的情况也一并适用

你说的没错，那些图的确不是最优解，我再数了下K8 的点，其实是19个，如果容许画曲线的话应当是18个

140楼只是直线情况下的图