题解 P3186 【[HNOI2007]所罗门的咒语】
command_block · · 题解
非常之毒瘤。
这题的几个数据。
首先，第7张图有两种背景色。
第3张图坏了好大一块。
第四张图竟然是D
我建议不要用原来的毒瘤数据，造几个高清数据岂不美哉？
主要思想就是联通块。
首先弄出一个亮度分界线，这是难点。
或者按照亮度的变化程度而定。
我采用前者，我太蒟了。
亮度大于这个数的设为1，其他设为0
然后找出每个联通块，由于地砖会坏，所以要计算联通块平均大小，比这个小很多的就不是咒语。
咒语“1”根据身高和腰围判出来。
所以不讨论1
可以求出左轮廓线和右轮廓线，上半部分大小和下半部分大小。
还有横截面的1的个数，举个例子：
. . . . 1 1 1 1 . . . . . . 1 . .
. . . . . . . . . . 1 1 1 1 1 1 .
. . . . . . . . . 1 1 1 1 1 1 1 .
. . . 1 1 1 1 . . . 1 1 1 1 1 . .
. 1 1 1 1 1 1 1 . . . . . 1 1 . .
. 1 1 . . 1 1 1 . . . . 1 1 . . .
. 1 1 . . . 1 1 . . . 1 1 1 1 1 .
. 1 1 . . . 1 1 . . . . 1 1 1 1 .
. 1 . . . . 1 1 . . . . . 1 1 1 .
. 1 . . . . 1 1 . . . . . . 1 1 .
. 1 . . . . 1 1 . . . . . . 1 1 .
1 1 1 . . 1 1 1 . . . . . . 1 1 .
. 1 1 . . 1 1 1 . . 1 1 . . 1 1 .
1 1 1 . . 1 1 1 . 1 1 1 1 1 1 1 .
1 1 1 . . 1 1 1 . . 1 1 1 1 1 . .
1 1 1 1 1 1 1 . . . 1 1 . . . . .
. 1 1 1 1 1 . . . 1 . . . . . . .
. . 1 1 . . . . . . . . . . . . .样例。
. . . 1 1 1 1 .
. 1 1 1 1 1 1 1
. 1 1 . . 1 1 1
. 1 1 . . . 1 1
. 1 1 . . . 1 1
. 1 . . . . 1 1
. 1 . . . . 1 1
. 1 . . . . 1 1
1 1 1 . . 1 1 1
. 1 1 . . 1 1 1
1 1 1 . . 1 1 1
1 1 1 . . 1 1 1
1 1 1 1 1 1 1 .
. 1 1 1 1 1 . .
. . 1 1 . . . .
0拍扁之后
(向左边掉落)
1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1
1 1 1 1
1 1 1 1
1 1 1
1 1 1
1 1 1
1 1 1 1 1 1
1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1
1 1
可以看到有两座山峰
(向下边掉落)
. . . . . . . .
. . . . . . . .
. 1 . . . . 1 .
. 1 . . . . 1 .
. 1 1 . . . 1 1
. 1 1 . . . 1 1
. 1 1 . . 1 1 1
. 1 1 . . 1 1 1
. 1 1 . . 1 1 1
. 1 1 . . 1 1 1
. 1 1 1 . 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
可以看到有两座山峰
为了避免锯齿可以做高斯模糊，然后根据差分数组判断有几座山。给出一个正常的表(数据不正常)：
| 咒语\ | 向下边掉落：山峰个数\ | 向左边掉落：山峰个数\ |
|---|---|---|
| 0 | 2 | 2 |
| 1 | 不好判断 | 不好判断 |
| 2 | 不好判断 | 2 |
| 3 | 不好判断 | 3 |
| 4 | 1 | 1 |
| 5 | 不好判断 | 3 |
| 6 | 不好判断 | 3 |
| 7 | 不好判断 | 1 |
| 8 | 不好判断 | 不好判断 |
| 9 | 不好判断 | 不好判断 |
| A | 不好判断 | 1 |
| D | 不好判断 | 不好判断 |
| E | 1 | 3 |
| L | 1 | 1 |
| X | 不好判断 | 不好判断 |
根据上下两部分的分布密度也可以辅助判断。比如L和7
下面不讨论L和7。
还有洞的个数
| 咒语\ | 洞的个数\ |
|---|---|
| 0 | 1 |
| 1 | 0 |
| 2 | 0 |
| 3 | 0 |
| 4 | 1 |
| 5 | 0 |
| 6 | 1 |
| 8 | 2 |
| 9 | 1 |
| A | 1 |
| D | 1 |
| E | 0 |
| X | 0 |
| 咒语\ | 向下边掉落：山峰个数\ | 向左边掉落：山峰个数\ | 洞的个数\ |
|---|---|---|---|
| 0 | 2 | 2 | 1 |
| 2 | 不好判断 | 2 | 0 |
| 3 | 不好判断 | 3 | 0 |
| 4 | 1 | 1 | 1 |
| 5 | 不好判断 | 3 | 0 |
| 6 | 不好判断 | 3 | 1 |
| 8 | 不好判断 | 不好判断 | 2 |
| 9 | 不好判断 | 不好判断 | 1 |
| A | 不好判断 | 1 | 1 |
| D | 不好判断 | 不好判断 | 1 |
| E | 1 | 3 | 0 |
| X | 不好判断 | 不好判断 | 0 |
现在，不能判断的有:4,9,A,D,0和3,E,X,5。
我们根据左右两边的密度来判断，可以找出E和3，下面不讨论他们。
我们硬是求一下X向左边掉落的山峰个数，高斯模糊之后怎么也不会有3个，分出了X和5.
剩下4,9,A,D,0
这几个咒语都只有一个洞。
前面的4,9,A有一个共同点。
这样的两束平行光线，会有很大一片两束都照不到的地方而不是洞。
这就区分了4,9,A和D,0
D和0比较像，可以求出他们的左侧轮廓和右侧轮廓，比较曲度，相差大的就是D.
4,9,A的左轮廓线各不相同。
求出左轮廓线差分数组，变化幅度不大的就是A
4和9有点难判，可以利用向下边掉落的山峰轮廓。
如果变化幅度很大就是4，变化幅度小就是9.