题解 P3186 【[HNOI2007]所罗门的咒语】

command_block

2018-08-28 18:57:05

Solution

![](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. ## 程序不贴了,纯属瞎搞.