题解 P3186 【[HNOI2007]所罗门的咒语】
command_block
2018-08-28 18:57:05
![](https://images0.cnblogs.com/blog/706716/201502/161533112526728.png)
非常之毒瘤。
这题的几个数据。
首先,第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有一个共同点。
![](https://cdn.luogu.com.cn/upload/pic/30950.png)
这样的两束平行光线,会有**很大一片**两束都照不到的地方而不是洞。
这就区分了4,9,A和D,0
D和0比较像,可以求出他们的左侧轮廓和右侧轮廓,比较曲度,相差大的就是D.
4,9,A的左轮廓线各不相同。
求出左轮廓线差分数组,变化幅度不大的就是A
4和9有点难判,可以利用**向下边掉落的山峰轮廓**。
如果变化幅度很大就是4,变化幅度小就是9.
## 程序不贴了,纯属瞎搞.