gougou1029

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

1029
2D Nim

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1413

3 2006-07-23 23:27:07 00:00:00 960K C++ glimpse


ZZT的解题报告：

   广度优先分别生成两个图形的每一个子块，找到包含这个子块的最小矩形，存储方式是记录子块每个点在这个矩形中的坐标，注意每个子块的点要排序。设计三种操作，左右镜像，上下镜像，对角镜像。一个子块的各种旋转镜像等变换都可以用这三种操作来实现，将一个图形的各个子块做变换，与另一个图形的各个子块做比较，如果全部都能找到对应的子块则是等价。

----

补充一下，思路是对的，不过“将一个图形的各个子块做变换，与另一个图形的各个子块做比较，如果全部都能找到对应的子块则是等价”，这样复杂度似乎太高了。事实上不需要这么做，只要把每个块都表示成其各种等价表示中最小的，也就是“最小表示”，再对块的数组排序，也就是无序数组的“最小表示“。那么直接判数组完全相等就好了。关键在于利用“最小表示“来降低判重的复杂度。

1029

2D Nim

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1413

3 2006-07-23 23:27:07 00:00:00 960K C++ glimpse

ZZT的解题报告：

广度优先分别生成两个图形的每一个子块，找到包含这个子块的最小矩形，存储方式是记录子块每个点在这个矩形中的坐标，注意每个子块的点要排序。设计三种操作，左右镜像，上下镜像，对角镜像。一个子块的各种旋转镜像等变换都可以用这三种操作来实现，将一个图形的各个子块做变换，与另一个图形的各个子块做比较，如果全部都能找到对应的子块则是等价。

---

补充一下，思路是对的，不过“将一个图形的各个子块做变换，与另一个图形的各个子块做比较，如果全部都能找到对应的子块则是等价”，这样复杂度似乎太高了。事实上不需要这么做，只要把每个块都表示成其各种等价表示中最小的，也就是“最小表示”，再对块的数组排序，也就是无序数组的“最小表示“。那么直接判数组完全相等就好了。关键在于利用“最小表示“来降低判重的复杂度。